Check if a polygon overlaps with a rectangle: Difference between revisions
Check if a polygon overlaps with a rectangle (view source)
Revision as of 22:50, 20 April 2024
, 1 month agoAdded Python
m (→{{header|Julia}}: cleanup) |
(Added Python) |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 5:
* [[Check_if_two_polygons_overlap|Check if two polygons overlap]]
<br><br>
Line 306 ⟶ 303:
poly and rect2 overlap? true
</pre>
=={{header|C++}}==
This is just a special case of the [[Check if two polygons overlap]] task where one of the polygons is a rectangle.
This example shows the standard method of dealing with such a special case. The rectangle is converted to a polygon
and then the existing code for checking if two polygons overlap is invoked. A similar process can be used for
determining if two rectangles overlap, or two triangles overlap,or a triangle and rectangle overlap, etc.
<syntaxhighlight lang="c++">
#include <iostream>
#include <limits>
#include <string>
#include <vector>
class Point {
public:
float x;
float y;
};
class Projection {
public:
float min;
float max;
const bool overlaps(const Projection& other) {
return ! ( max < other.min || other.max < min );
}
};
class Vector {
public:
float x;
float y;
const float scalarProduct(const Vector& other) {
return x * other.x + y * other.y;
}
const Vector edgeWith(const Vector& other) {
return Vector(x - other.x, y - other.y);
}
const Vector perpendicular() {
return Vector(-y, x);
}
const std::string to_string() {
return "(" + std::to_string(x) + ", " + std::to_string(y) + ") ";
}
};
class Polygon {
public:
Polygon(const std::vector<Point>& points) {
computeVertices(points);
computeAxes();
}
const bool overlaps(Polygon& other) {
std::vector<Vector> allAxes = axes;
allAxes.insert(allAxes.end(), other.axes.begin(), other.axes.end());
for ( Vector& axis : allAxes ) {
Projection projection1 = projectionOnAxis(axis);
Projection projection2 = other.projectionOnAxis(axis);
if ( ! projection1.overlaps(projection2) ) {
return false;
}
}
return true;
}
const Projection projectionOnAxis(Vector& axis) {
float min = std::numeric_limits<float>::infinity();
float max = -std::numeric_limits<float>::infinity();
for ( const Vector& vertex : vertices ) {
double p = axis.scalarProduct(vertex);
if ( p < min ) {
min = p;
}
if ( p > max ) {
max = p;
}
}
return Projection(min, max);
}
const std::string to_string() {
std::string result = "[ ";
for ( Vector& vertex : vertices ) {
result += vertex.to_string();
}
result += "]";
return result;
}
private:
void computeVertices(const std::vector<Point>& points) {
for ( const Point& point : points ) {
vertices.emplace_back(Vector(point.x, point.y));
}
}
void computeAxes() {
for ( size_t i = 0; i < vertices.size(); i++ ) {
Vector vertex1 = vertices[i];
Vector vertex2 = vertices[( i + 1 ) % vertices.size()];
Vector edge = vertex1.edgeWith(vertex2);
axes.emplace_back(edge.perpendicular());
}
}
std::vector<Vector> vertices;
std::vector<Vector> axes;
};
class Rectangle {
public:
float x;
float y;
float width;
float height;
};
Polygon rectangleToPolygon(const Rectangle& rectangle) {
return Polygon(std::vector<Point> { Point(rectangle.x, rectangle.y),
Point(rectangle.x + rectangle.width, rectangle.y),
Point(rectangle.x + rectangle.width, rectangle.y + rectangle.height),
Point(rectangle.x, rectangle.y + rectangle.height) });
}
int main() {
Polygon polygon(std::vector<Point> { Point(0.0, 0.0), Point(0.0, 2.0), Point(1.0, 4.0),
Point(2.0, 2.0), Point(2.0, 0.0) } );
Rectangle rectangle1(4.0, 0.0, 2.0, 2.0);
Rectangle rectangle2(1.0, 0.0, 8.0, 2.0);
Polygon polygon1 = rectangleToPolygon(rectangle1);
Polygon polygon2 = rectangleToPolygon(rectangle2);
std::cout << "polygon: " << polygon.to_string() << std::endl;
std::cout << "rectangle1: " << polygon1.to_string() << std::endl;
std::cout << "rectangle2: " << polygon2.to_string() << std::endl;
std::cout << std::boolalpha << std::endl;
std::cout << "polygon and polygon2 overlap? " << polygon.overlaps(polygon1) << std::endl;
std::cout << "polygon and polygon3 overlap? " << polygon.overlaps(polygon2) << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
polygon: [ (0.000000, 0.000000) (0.000000, 2.000000) (1.000000, 4.000000) (2.000000, 2.000000) (2.000000, 0.000000) ]
rectangle1: [ (4.000000, 0.000000) (6.000000, 0.000000) (6.000000, 2.000000) (4.000000, 2.000000) ]
rectangle2: [ (1.000000, 0.000000) (9.000000, 0.000000) (9.000000, 2.000000) (1.000000, 2.000000) ]
polygon and polygon2 overlap? false
polygon and polygon3 overlap? true
</pre>
=={{header|EasyLang}}==
{{trans|Go}}
<syntaxhighlight>
func dot a[] b[] .
return a[1] * b[1] + a[2] * b[2]
.
proc addAxes . poly[][] r[][] .
for i to len poly[][]
v1[] = poly[i][]
j = (i + 1) mod1 len poly[][]
v2[] = poly[j][]
r[][] &= [ -(v1[2] - v2[2]) v1[1] - v2[1] ]
.
.
proc projectAxis . poly[][] axis[] min max .
min = 1 / 0
max = -1 / 0
for i to len poly[][]
p = dot axis[] poly[i][]
min = lower min p
max = higher max p
.
.
proc polyOverlap . poly1[][] poly2[][] r .
axes[][] = [ ]
addAxes poly1[][] axes[][]
addAxes poly2[][] axes[][]
for i to len axes[][]
axis[] = axes[i][]
projectAxis poly1[][] axis[] min1 max1
projectAxis poly2[][] axis[] min2 max2
if max1 < min2 or max2 < min1
r = 0
return
.
.
r = 1
.
proc polyDraw col . poly[][] .
color col
linewidth 0.5
for i to len poly[][]
line poly[i][1] * 9 + 5 poly[i][2] * 9 + 5
.
line poly[1][1] * 9 + 5 poly[1][2] * 9 + 5
.
proc rectToPoly . r[] p[][] .
p[][] = [ [ r[1] r[2] ] [ r[1] + r[3] r[2] ] [ r[1] + r[3] r[2] + r[4] ] [ r[1] r[2] + r[4] ] ]
.
poly1[][] = [ [ 0 0 ] [ 0 2 ] [ 1 4 ] [ 2 2 ] [ 2 0 ] ]
rect1[] = [ 4 0 2 2 ]
rect2[] = [ 1 0 8 2 ]
rectToPoly rect1[] poly2[][]
rectToPoly rect2[] poly3[][]
#
polyDraw 900 poly1[][]
polyDraw 090 poly2[][]
polyDraw 009 poly3[][]
#
polyOverlap poly1[][] poly2[][] r ; print r
polyOverlap poly1[][] poly3[][] r ; print r
</syntaxhighlight>
=={{header|FreeBASIC}}==
{{trans|C}}
<syntaxhighlight lang="vbnet">Type Vector2
x As Double
y As Double
End Type
Type Projection
min As Double
max As Double
End Type
Type Rectangle
x As Double
y As Double
w As Double
h As Double
End Type
Function dot(v1 As Vector2, v2 As Vector2) As Double
Return v1.x * v2.x + v1.y * v2.y
End Function
Sub getAxes(poly() As Vector2, axes() As Vector2)
Dim As Integer i, j
Dim As Vector2 vector1, vector2, edge
For i = 0 To Ubound(poly)
vector1 = poly(i)
j = Iif((i + 1 = Ubound(poly)+1), 0, i + 1)
vector2 = poly(j)
edge.x = vector1.x - vector2.x
edge.y = vector1.y - vector2.y
axes(i).x = -edge.y
axes(i).y = edge.x
Next i
End Sub
Function projectOntoAxis(poly() As Vector2, axis As Vector2) As Projection
Dim As Vector2 vector
Dim As Double min, max, p
vector = poly(0)
min = dot(axis, vector)
max = min
For i As Integer = 1 To Ubound(poly)
vector = poly(i)
p = dot(axis, vector)
If p < min Then
min = p
Elseif p > max Then
max = p
End If
Next i
Return Type<Projection>(min, max)
End Function
Function projectionsOverlap(proj1 As Projection, proj2 As Projection) As Boolean
If proj1.max < proj2.min Then Return False
If proj2.max < proj1.min Then Return False
Return True
End Function
Sub rectToPolygon(r As Rectangle, poly() As Vector2)
poly(0).x = r.x: poly(0).y = r.y
poly(1).x = r.x: poly(1).y = r.y + r.h
poly(2).x = r.x + r.w: poly(2).y = r.y + r.h
poly(3).x = r.x + r.w: poly(3).y = r.y
End Sub
Function polygonOverlapsRect(poly1() As Vector2, rect As Rectangle) As Boolean
Dim As Integer i
Dim As Vector2 axis
Dim As Projection proj1, proj2
Dim As Vector2 poly2(3)
rectToPolygon(rect, poly2())
Dim As Vector2 axes1(Ubound(poly1)), axes2(3)
getAxes(poly1(), axes1())
getAxes(poly2(), axes2())
For i = 0 To Ubound(poly1)
axis = axes1(i)
proj1 = projectOntoAxis(poly1(), axis)
proj2 = projectOntoAxis(poly2(), axis)
If projectionsOverlap(proj1, proj2) = 0 Then Return False
Next i
For i = 0 To Ubound(poly2)
axis = axes2(i)
proj1 = projectOntoAxis(poly1(), axis)
proj2 = projectOntoAxis(poly2(), axis)
If projectionsOverlap(proj1, proj2) = 0 Then Return False
Next i
Return True
End Function
Sub printPoly(poly() As Vector2)
Print "{";
For i As Integer = 0 To Ubound(poly)
Print "{" & poly(i).x & ", " & poly(i).y & "}";
If i < Ubound(poly) Then Print ", ";
Next i
Print "}"
End Sub
Dim As Vector2 poly(4) = {Type<Vector2>(0, 0), Type<Vector2>(0, 2), Type<Vector2>(1, 4), Type<Vector2>(2, 2), Type<Vector2>(2, 0)}
Dim As Vector2 poly2(3)
Dim As Rectangle rect1 = Type<Rectangle>(4, 0, 2, 2)
Dim As Rectangle rect2 = Type<Rectangle>(1, 0, 8, 2)
Print "poly = ";
printPoly(poly())
Print "rect1 = {" & rect1.x & ", " & rect1.y & ", " & rect1.w & ", " & rect1.h & "} => ";
rectToPolygon(rect1, poly2())
printPoly(poly2())
Print "rect2 = {" & rect2.x & ", " & rect2.y & ", " & rect2.w & ", " & rect2.h & "} => ";
rectToPolygon(rect2, poly2())
printPoly(poly2())
Print
Print "poly and rect1 overlap? "; Iif(polygonOverlapsRect(poly(), rect1), "true", "false")
Print "poly and rect2 overlap? "; Iif(polygonOverlapsRect(poly(), rect2), "true", "false")
Sleep</syntaxhighlight>
{{out}}
<pre>poly = {{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}
rect1 = {4, 0, 2, 2} => {{4, 0}, {4, 2}, {6, 2}, {6, 0}}
rect2 = {1, 0, 8, 2} => {{1, 0}, {1, 2}, {9, 2}, {9, 0}}
poly and rect1 overlap? false
poly and rect2 overlap? true</pre>
=={{header|Go}}==
Line 418 ⟶ 770:
poly and rect1 overlap? false
poly and rect2 overlap? true
</pre>
=={{header|Java}}==
This is just a special case of the [[Check if two polygons overlap]] task where one of the polygons is a rectangle.
This example shows the standard method of dealing with such a special case. The rectangle is converted to a polygon
and then the existing code for checking if two polygons overlap is invoked. A similar process can be used for
determining if two rectangles overlap, or two triangles overlap,or a triangle and rectangle overlap, etc.
<syntaxhighlight lang="java">
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.List;
public final class CheckIfARectangleOverlapsWithAPolygon {
public static void main(String[] args) {
Polygon polygon = new Polygon(List.of( new Point(0.0, 0.0), new Point(0.0, 2.0), new Point(1.0, 4.0),
new Point(2.0, 2.0), new Point(2.0, 0.0) ));
Rectangle2D.Double rectangle1 = new Rectangle2D.Double(4.0, 0.0, 2.0, 2.0);
Rectangle2D.Double rectangle2 = new Rectangle2D.Double(1.0, 0.0, 8.0, 2.0);
Polygon polygon1 = rectangleToPolygon(rectangle1);
Polygon polygon2 = rectangleToPolygon(rectangle2);
System.out.println("polygon = " + polygon);
System.out.println("rectangle1 = " + polygon1);
System.out.println("rectangle2 = " + polygon2);
System.out.println();
System.out.println("polygon and rectangle1 overlap? " + polygon.overlaps(polygon1));
System.out.println("polygon and rectangle2 overlap? " + polygon.overlaps(polygon2));
}
private static Polygon rectangleToPolygon(Rectangle2D.Double rectangle) {
return new Polygon(List.of( new Point(rectangle.x, rectangle.y),
new Point(rectangle.x + rectangle.width, rectangle.y),
new Point(rectangle.x + rectangle.width, rectangle.y + rectangle.height),
new Point(rectangle.x, rectangle.y + rectangle.height) ));
}
private static class Polygon {
public Polygon(List<Point> points) {
vertices = points.stream().map( point -> new Vector(point.x, point.y) ).toList();
computeAxes();
}
public boolean overlaps(Polygon other) {
List<Vector> allAxes = new ArrayList<Vector>(axes);
allAxes.addAll(other.axes);
for ( Vector axis : allAxes ) {
Projection projection1 = projectionOnAxis(axis);
Projection projection2 = other.projectionOnAxis(axis);
if ( ! projection1.overlaps(projection2) ) {
return false;
}
}
return true;
}
public Projection projectionOnAxis(Vector axis) {
double min = Double.POSITIVE_INFINITY;
double max = Double.NEGATIVE_INFINITY;
for ( Vector vertex : vertices ) {
double p = axis.scalarProduct(vertex);
if ( p < min ) {
min = p;
}
if ( p > max ) {
max = p;
}
}
return new Projection(min, max);
}
public String toString() {
StringBuilder result = new StringBuilder("[ ");
for ( Vector vertex : vertices ) {
result.append(vertex);
}
result.append("]");
return result.toString();
}
private void computeAxes() {
axes = new ArrayList<Vector>();
for ( int i = 0; i < vertices.size(); i++ ) {
Vector vertex1 = vertices.get(i);
Vector vertex2 = vertices.get(( i + 1 ) % vertices.size());
Vector edge = vertex1.edgeWith(vertex2);
axes.addLast(edge.perpendicular());
}
}
private List<Vector> vertices;
private List<Vector> axes;
}
final record Vector(double x, double y) {
public double scalarProduct(Vector other) {
return x * other.x + y * other.y;
}
public Vector edgeWith(Vector other) {
return new Vector(x - other.x, y - other.y);
}
public Vector perpendicular() {
return new Vector(-y, x);
}
public String toString() {
return "(" + x + ", " + y + ") ";
}
}
final record Projection(double min, double max) {
public boolean overlaps(Projection other) {
return ! ( max < other.min || other.max < min );
}
}
final record Point(double x, double y) { }
}
</syntaxhighlight>
{{ out }}
<pre>
polygon = [ (0.0, 0.0) (0.0, 2.0) (1.0, 4.0) (2.0, 2.0) (2.0, 0.0) ]
rectangle1 = [ (4.0, 0.0) (6.0, 0.0) (6.0, 2.0) (4.0, 2.0) ]
rectangle2 = [ (1.0, 0.0) (9.0, 0.0) (9.0, 2.0) (1.0, 2.0) ]
polygon and rectangle1 overlap? false
polygon and rectangle2 overlap? true
</pre>
Line 474 ⟶ 970:
const Vector2 = Tuple{Float64, Float64}
const Projection =
const Polygon = Vector{Vector2}
const Rectangle = NamedTuple{(:x, :y, :w, :h), NTuple{4, Float64}}
function axes(poly::Polygon)::Polygon
result = [(0.0, 0.0) for _ in eachindex(poly)]
for (i, vertex1) in enumerate(poly)
Line 488 ⟶ 984:
end
function projectiononaxis(poly::Polygon, axis::Vector2)::Projection
resultmin, resultmax = Inf, -Inf
for vertex in poly
Line 495 ⟶ 991:
p > resultmax && (resultmax = p)
end
return Projection((resultmin, resultmax))
end
Line 502 ⟶ 998:
Polygon(r::Rectangle) = [(r.x, r.y), (r.x, r.y + r.h), (r.x + r.w, r.y + r.h), (r.x + r.w, r.y)]
function polygonoverlapsrect(p1::Polygon, rect::Rectangle)::Bool
p2 = Polygon(rect)
return !any(projectionoverlaps(projectiononaxis(p1, axis), projectiononaxis(p2, axis))
Line 668 ⟶ 1,164:
poly and rect2 overlap? true
</pre>
=={{header|Python}}==
{{works with|Python|3.x}}
{{trans|C}}
<syntaxhighlight lang="python">#!/usr/bin/python3
class Vector2:
def __init__(self, x, y):
self.x = x
self.y = y
class Projection:
def __init__(self, min, max):
self.min = min
self.max = max
def dot(v1, v2):
return v1.x * v2.x + v1.y * v2.y
def get_axes(poly):
axes = []
for i in range(len(poly)):
vector1 = poly[i]
j = 0 if i + 1 == len(poly) else i + 1
vector2 = poly[j]
edge = Vector2(vector1.x - vector2.x, vector1.y - vector2.y)
axes.append(Vector2(-edge.y, edge.x))
return axes
def project_onto_axis(poly, axis):
vector = poly[0]
min = dot(axis, vector)
max = min
for i in range(1, len(poly)):
vector = poly[i]
p = dot(axis, vector)
if p < min:
min = p
elif p > max:
max = p
return Projection(min, max)
def projections_overlap(proj1, proj2):
return not (proj1.max < proj2.min or proj2.max < proj1.min)
def polygons_overlap(poly1, poly2):
for axis in get_axes(poly1) + get_axes(poly2):
proj1 = project_onto_axis(poly1, axis)
proj2 = project_onto_axis(poly2, axis)
if not projections_overlap(proj1, proj2):
return False
return True
def print_poly(poly):
print([{'x': p.x, 'y': p.y} for p in poly])
if __name__ == "__main__":
poly1 = [
Vector2(0, 0),
Vector2(0, 2),
Vector2(1, 4),
Vector2(2, 2),
Vector2(2, 0)
]
poly2 = [
Vector2(4, 0),
Vector2(4, 2),
Vector2(5, 4),
Vector2(6, 2),
Vector2(6, 0)
]
poly3 = [
Vector2(1, 0),
Vector2(1, 2),
Vector2(5, 4),
Vector2(9, 2),
Vector2(9, 0)
]
print('poly1 = ', end='')
print_poly(poly1)
print('poly2 = ', end='')
print_poly(poly2)
print('poly3 = ', end='')
print_poly(poly3)
print()
print('poly1 and poly2 overlap? ', polygons_overlap(poly1, poly2))
print('poly1 and poly3 overlap? ', polygons_overlap(poly1, poly3))
print('poly2 and poly3 overlap? ', polygons_overlap(poly2, poly3))</syntaxhighlight>
{{out}}
<pre>poly1 = [{'x': 0, 'y': 0}, {'x': 0, 'y': 2}, {'x': 1, 'y': 4}, {'x': 2, 'y': 2}, {'x': 2, 'y': 0}]
poly2 = [{'x': 4, 'y': 0}, {'x': 4, 'y': 2}, {'x': 5, 'y': 4}, {'x': 6, 'y': 2}, {'x': 6, 'y': 0}]
poly3 = [{'x': 1, 'y': 0}, {'x': 1, 'y': 2}, {'x': 5, 'y': 4}, {'x': 9, 'y': 2}, {'x': 9, 'y': 0}]
poly1 and poly2 overlap? False
poly1 and poly3 overlap? True
poly2 and poly3 overlap? True</pre>
=={{header|Raku}}==
Line 738 ⟶ 1,330:
{{libheader|Wren-dynamic}}
This is just a special case of the [[Check if two polygons overlap]] task where one of the polygons is a rectangle though, for convenience, the common code is repeated here.
<syntaxhighlight lang="
import "./dynamic" for Tuple
| |||