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
(Added Wren) |
(Added Python) |
||
| (21 intermediate revisions by 10 users not shown) | |||
Line 1:
{{task}}Self-explanatory: given a polygon (as an array/vector/list of its vertices) and a rectangle (in x, y, width, height format), check if they intersect.
;Related tasks
* [[Determine_if_two_triangles_overlap|Determine if two triangles overlap]]
* [[Check_if_two_polygons_overlap|Check if two polygons overlap]]
<br><br>
=={{header|ALGOL 68}}==
Basically the same as the Algol 68 sample for the [[Check if two polygons overlap]] task, with added rectangle handling (as in the Go, Wren, etc. samples) and using the same test cases as the Wren and other samples.
The Algol 68 Check if two polygons overlap sample was based on that task's Go sample.
<syntaxhighlight lang="algol68">
BEGIN # test whether a 2D polygon overlaps a rectangle #
# - based on a translation Go which is a translation of Wren #
# In the following a polygon is represented as a row of vertices #
# and a vertex ( POINT ) by a pair of x, y coordinates in the plane #
# most of this is verbatim from the check if two polygons overlap task #
MODE POINT = STRUCT( REAL x, y );
MODE PROJECTION = STRUCT( REAL min, max );
MODE POLYGON = FLEX[ 1 : 0 ]POINT;
PRIO DOT = 3;
OP DOT = ( POINT v, other )REAL:
( x OF v * x OF other ) + ( y OF v * y OF other );
# returns the axes of the polygon defined by poly #
OP AXES = ( POLYGON poly )[]POINT:
BEGIN
[ LWB poly : UPB poly ]POINT result;
FOR i FROM LWB poly TO UPB poly DO
INT j = IF i = UPB poly THEN LWB poly ELSE i + 1 FI;
POINT vertex1 = poly[ i ];
POINT vertex2 = poly[ j ];
POINT edge = ( x OF vertex1 - x OF vertex2, y OF vertex1 - y OF vertex2 );
result[ i ] := ( - y OF edge, x OF edge )
OD;
result
END # AXES # ;
# returns the projection of poly onto axis #
PRIO PROJECTONTO = 3;
OP PROJECTONTO = ( POLYGON poly, POINT axis )PROJECTION:
BEGIN
REAL min := axis DOT poly[ LWB poly ];
REAL max := min;
FOR i FROM LWB poly + 1 TO UPB poly DO
REAL p = axis DOT poly[ i ];
IF p < min THEN
min := p
ELIF p > max THEN
max := p
FI
OD;
PROJECTION( min, max )
END # PROJECTONTO # ;
PRIO OVERLAPS = 5;
# returns TRUE if the projections proj1 and proj2 overlap, #
# FALSE otherrwise #
OP OVERLAPS = ( PROJECTION proj1, proj2 )BOOL:
IF max OF proj1 < min OF proj2 THEN FALSE
ELIF max OF proj2 < min OF proj1 THEN FALSE
ELSE TRUE
FI # OVERLAPS # ;
# returns TRUE if the polygons poly1 and poly2 overlap, #
# FALSE otherrwise #
OP OVERLAPS = ( POLYGON poly1, poly2 )BOOL:
BEGIN
[]POINT axes1 = AXES poly1, axes2 = AXES poly2;
BOOL does overlap := TRUE;
FOR a FROM LWB axes1 TO UPB axes1 WHILE does overlap DO
does overlap := ( poly1 PROJECTONTO axes1[ a ] )
OVERLAPS ( poly2 PROJECTONTO axes1[ a ] )
OD;
FOR a FROM LWB axes2 TO UPB axes2 WHILE does overlap DO
does overlap := ( poly1 PROJECTONTO axes2[ a ] )
OVERLAPS ( poly2 PROJECTONTO axes2[ a ] )
OD;
does overlap
END # OVERLAPS # ;
# returns x as a string without trailing 0 decoimals #
OP TOSTRING = ( REAL x )STRING:
BEGIN
STRING v := fixed( x, -14, 11 );
INT end pos := UPB v;
WHILE IF end pos < LWB v THEN FALSE ELSE v[ end pos ] = "0" FI DO
end pos -:= 1
OD;
IF end pos >= LWB v THEN
IF v[ end pos ] = "." THEN end pos -:= 1 FI
FI;
INT start pos := LWB v;
WHILE IF start pos > end pos THEN FALSE ELSE v[ start pos ] = " " FI DO
start pos +:= 1
OD;
IF end pos < start pos THEN "0" ELSE v[ start pos : end pos ] FI
END # TOSTRING # ;
# returns a string representation of the POINT p #
OP TOSTRING = ( POINT p )STRING: "( " + TOSTRING x OF p + ", " + TOSTRING y OF p + " )";
# returns a string representation of the points of p #
OP TOSTRING = ( POLYGON p )STRING:
BEGIN
STRING result := "(", separator := "";
FOR i FROM LWB p TO UPB p DO
result +:= separator + " " + TOSTRING p[ i ];
separator := ","
OD;
result + " )"
END # TOSTRING # ;
# begin additional code for this task #
# a rectangle is represented by its lower left corner, width and height #
MODE RECTANGLE = STRUCT( POINT corner, REAL width, height );
# returns a POLYGON equivalent to the RECTANGLE r #
OP TOPOLYGON = ( RECTANGLE r )POLYGON:
( corner OF r
, ( x OF corner OF r, y OF corner OF r + height OF r )
, ( x OF corner OF r + width OF r, y OF corner OF r + height OF r )
, ( x OF corner OF r + width OF r, y OF corner OF r )
);
# returns TRUE if the POLYGON poly and RECTANGLE rect overlap, #
# FALSE otherrwise #
OP OVERLAPS = ( POLYGON poly, RECTANGLE rect )BOOL: poly OVERLAPS TOPOLYGON rect;
# returns a string representation of the rectangle r #
OP TOSTRING = ( RECTANGLE r )STRING:
"( " + TOSTRING corner OF r + ", " + TOSTRING width OF r + ", " + TOSTRING height OF r + " )";
# end additional code for this task #
# test cases #
POLYGON poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) );
RECTANGLE rect1 = ( ( 4, 0 ), 2, 2), rect2 = ( ( 1, 0 ), 8, 2);
print( ( "poly1 = ", TOSTRING poly1, newline ) );
print( ( "rect1 = ", TOSTRING rect1, " => ", TOSTRING TOPOLYGON rect1, newline ) );
print( ( "rect2 = ", TOSTRING rect2, " => ", TOSTRING TOPOLYGON rect2, newline ) );
print( ( newline ) );
print( ( "poly1 and rect1 overlap? ", IF poly1 OVERLAPS rect1 THEN "yes" ELSE "no" FI, newline ) );
print( ( "poly1 and rect2 overlap? ", IF poly1 OVERLAPS rect2 THEN "yes" ELSE "no" FI, newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
poly1 = ( ( 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 ) )
poly1 and rect1 overlap? no
poly1 and rect2 overlap? yes
</pre>
=={{header|C}}==
{{trans|Wren}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdbool.h>
typedef struct {
double x;
double y;
} Vector2;
typedef struct {
double min;
double max;
} Projection;
typedef struct {
double x;
double y;
double w;
double h;
} Rectangle;
double dot(Vector2 v1, Vector2 v2) {
return v1.x * v2.x + v1.y * v2.y;
}
/* In the following a polygon is represented as an array of vertices
and a vertex by a pair of x, y coordinates in the plane. */
void getAxes(double poly[][2], size_t len, Vector2 axes[len]) {
int i, j;
Vector2 vector1, vector2, edge;
for (i = 0; i < len; ++i) {
vector1 = (Vector2){poly[i][0], poly[i][1]};
j = (i + 1 == len) ? 0 : i + 1;
vector2 = (Vector2){poly[j][0], poly[j][1]};
edge = (Vector2){vector1.x - vector2.x, vector1.y - vector2.y};
axes[i].x = -edge.y;
axes[i].y = edge.x;
}
}
Projection projectOntoAxis(double poly[][2], size_t len, Vector2 axis) {
int i;
Vector2 vector0, vector;
double min, max, p;
vector0 = (Vector2){poly[0][0], poly[0][1]};
min = dot(axis, vector0);
max = min;
for (i = 1; i < len; ++i) {
vector = (Vector2){poly[i][0], poly[i][1]};
p = dot(axis, vector);
if (p < min) {
min = p;
} else if (p > max) {
max = p;
}
}
return (Projection){min, max};
}
bool projectionsOverlap(Projection proj1, Projection proj2) {
if (proj1.max < proj2.min) return false;
if (proj2.max < proj1.min) return false;
return true;
}
void rectToPolygon(Rectangle r, double poly[4][2]) {
poly[0][0] = r.x; poly[0][1] = r.y;
poly[1][0] = r.x; poly[1][1] = r.y + r.h;
poly[2][0] = r.x + r.w; poly[2][1] = r.y + r.h;
poly[3][0] = r.x + r.w; poly[3][1] = r.y;
}
bool polygonOverlapsRect(double poly1[][2], size_t len1, Rectangle rect) {
int i;
size_t len2 = 4;
Vector2 axis, axes1[len1], axes2[len2];
Projection proj1, proj2;
/* Convert 'rect' struct into polygon form. */
double poly2[len2][2];
rectToPolygon(rect, poly2);
getAxes(poly1, len1, axes1);
getAxes(poly2, len2, axes2);
for (i = 0; i < len1; ++i) {
axis = axes1[i];
proj1 = projectOntoAxis(poly1, len1, axis);
proj2 = projectOntoAxis(poly2, len2, axis);
if (!projectionsOverlap(proj1, proj2)) return false;
}
for (i = 0; i < len2; ++i) {
axis = axes2[i];
proj1 = projectOntoAxis(poly1, len1, axis);
proj2 = projectOntoAxis(poly2, len2, axis);
if (!projectionsOverlap(proj1, proj2)) return false;
}
return true;
}
void printPoly(double poly[][2], size_t len) {
int i, j;
printf("{ ");
for (i = 0; i < len; ++i) {
printf("{");
for (j = 0; j < 2; ++j) {
printf("%g", poly[i][j]);
if (j == 0) printf(", ");
}
printf("}");
if (i < len-1) printf(", ");
}
printf(" }\n");
}
int main() {
double poly[][2] = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} };
double poly2[4][2];
Rectangle rect1 = {4, 0, 2, 2};
Rectangle rect2 = {1, 0, 8, 2};
printf("poly = ");
printPoly(poly, 5);
printf("rect1 = {%g, %g, %g, %g} => ", rect1.x, rect1.y, rect1.w, rect1.h);
rectToPolygon(rect1, poly2);
printPoly(poly2, 4);
printf("rect2 = {%g, %g, %g, %g} => ", rect2.x, rect2.y, rect2.w, rect2.h);
rectToPolygon(rect2, poly2);
printPoly(poly2, 4);
printf("\n");
printf("poly and rect1 overlap? %s\n", polygonOverlapsRect(poly, 5, rect1) ? "true" : "false");
printf("poly and rect2 overlap? %s\n", polygonOverlapsRect(poly, 5, rect2) ? "true" : "false");
return 0;
}</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|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}}==
{{trans|Wren}}
<syntaxhighlight lang="go">package main
import "fmt"
type Vector2 struct {
x, y float64
}
type Projection struct {
min, max float64
}
type Rectangle struct {
x, y, w, h float64
}
func (v Vector2) dot(other Vector2) float64 {
return v.x*other.x + v.y*other.y
}
/* In the following a polygon is represented as a slice of vertices
and a vertex by a pair of x, y coordinates in the plane. */
func getAxes(poly [][2]float64) []Vector2 {
axes := make([]Vector2, len(poly))
for i := 0; i < len(poly); i++ {
vertex1 := poly[i]
j := i + 1
if i+1 == len(poly) {
j = 0
}
vertex2 := poly[j]
vector1 := Vector2{vertex1[0], vertex1[1]}
vector2 := Vector2{vertex2[0], vertex2[1]}
edge := Vector2{vector1.x - vector2.x, vector1.y - vector2.y}
axes[i] = Vector2{-edge.y, edge.x}
}
return axes
}
func projectOntoAxis(poly [][2]float64, axis Vector2) Projection {
vertex0 := poly[0]
vector0 := Vector2{vertex0[0], vertex0[1]}
min := axis.dot(vector0)
max := min
for i := 1; i < len(poly); i++ {
vertex := poly[i]
vector := Vector2{vertex[0], vertex[1]}
p := axis.dot(vector)
if p < min {
min = p
} else if p > max {
max = p
}
}
return Projection{min, max}
}
func projectionsOverlap(proj1, proj2 Projection) bool {
if proj1.max < proj2.min {
return false
}
if proj2.max < proj1.min {
return false
}
return true
}
func rectToPolygon(r Rectangle) [][2]float64 {
return [][2]float64{{r.x, r.y}, {r.x, r.y + r.h}, {r.x + r.w, r.y + r.h}, {r.x + r.w, r.y}}
}
func polygonOverlapsRect(poly1 [][2]float64, rect Rectangle) bool {
// Convert 'rect' struct into polygon form.
poly2 := rectToPolygon(rect)
axes1 := getAxes(poly1)
axes2 := getAxes(poly2)
for _, axes := range [][]Vector2{axes1, axes2} {
for _, axis := range axes {
proj1 := projectOntoAxis(poly1, axis)
proj2 := projectOntoAxis(poly2, axis)
if !projectionsOverlap(proj1, proj2) {
return false
}
}
}
return true
}
func main() {
poly := [][2]float64{{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}
rect1 := Rectangle{4, 0, 2, 2}
rect2 := Rectangle{1, 0, 8, 2}
fmt.Println("poly = ", poly)
fmt.Println("rect1 = ", rect1, " => ", rectToPolygon(rect1))
fmt.Println("rect2 = ", rect2, " => ", rectToPolygon(rect2))
fmt.Println()
fmt.Println("poly and rect1 overlap?", polygonOverlapsRect(poly, rect1))
fmt.Println("poly and rect2 overlap?", polygonOverlapsRect(poly, rect2))
}</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|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>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
This entry uses the same strategy and the same functions as in [[Check_if_two_polygons_overlap#jq]],
and so the code is not repeated here.
The twist here is that we provide a function that allows rectangles to be specified by three vertices.
<syntaxhighlight lang="jq">
def addVector($B): [ .[0] + $B[0], .[1] + $B[1]];
def isPerpTo($other): dot($other) == 0;
# Input should be three points [A,B,C] where AB is perpendicular to BC
def rectangleToPolygon:
. as [$A, $B, $C]
# check perpendicularity
| if ([$A,$B] | AB | isPerpTo( [$B,$C] | AB)) then .
else "rectangleToPolygon: AB is not perpendicular to BC" | error
end
| . + [$A | addVector( [$B,$C]|AB ) ] ;
def poly1: [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]];
def rect1: [ [4, 0], [4, 2], [6, 2] ];
def rect2: [ [1, 0], [1, 2], [9, 2] ];
def task:
([rect1, rect2] | map(rectangleToPolygon)) as [$r1, $r2]
| "poly1 = \(poly1)",
"r1 = \($r1)",
"r2 = \($r2)",
"",
"poly1 and r1 overlap? \(polygonsOverlap(poly1; $r1))",
"poly1 and r2 overlap? \(polygonsOverlap(poly1; $r2))"
;
task
</syntaxhighlight>
{{output}}
<pre>
poly1 = [[0,0],[0,2],[1,4],[2,2],[2,0]]
r1 = [[4,0],[4,2],[6,2],[6,0]]
r2 = [[1,0],[1,2],[9,2],[9,0]]
poly1 and r1 overlap? false
poly1 and r2 overlap? true
</pre>
=={{header|Julia}}==
{{trans|Nim}}
<syntaxhighlight lang="julia">import LinearAlgebra: dot
const Vector2 = Tuple{Float64, Float64}
const Projection = NamedTuple{(:min, :max), NTuple{2, Float64}}
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)
vertex2 = i == lastindex(poly) ? first(poly) : poly[i+1] # wraps around
edge = (first(vertex1) - first(vertex2), last(vertex1) - last(vertex2))
result[i] = (-last(edge), first(edge))
end
return result
end
function projectiononaxis(poly::Polygon, axis::Vector2)::Projection
resultmin, resultmax = Inf, -Inf
for vertex in poly
p = dot(axis, vertex)
p < resultmin && (resultmin = p)
p > resultmax && (resultmax = p)
end
return Projection((resultmin, resultmax))
end
projectionoverlaps(p1::Projection, p2::Projection) = p1[2] <= p2[1] && p2[2] >= p1[1]
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))
for a in [axes(p1), axes(p2)] for axis in a)
end
const poly = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
const rect1 = Rectangle((4.0, 0.0, 2.0, 2.0))
const rect2 = Rectangle((1.0, 0.0, 8.0, 2.0))
println("poly = a polygon with vertices: ", poly)
println("rect1 = Rectangle with ", rect1)
println("rect2 = Rectangle with ", rect2)
println("\npoly and rect1 overlap? ", polygonoverlapsrect(poly, rect1))
println("poly and rect2 overlap? ", polygonoverlapsrect(poly, rect2))
</syntaxhighlight>{{out}}
<pre>
poly = a polygon with vertices: [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
rect1 = Rectangle with (x = 4.0, y = 0.0, w = 2.0, h = 2.0)
rect2 = Rectangle with (x = 1.0, y = 0.0, w = 8.0, h = 2.0)
poly and rect1 overlap? false
poly and rect2 overlap? true
</pre>
=={{header|Nim}}==
{{trans|Wren}}
{{trans|Go}}
<syntaxhighlight lang="Nim">type
Vector2 = (float, float)
Projection = tuple[min, max: float]
Polygon = seq[Vector2]
Rectangle = tuple[x, y, w, h: float]
func dot(v1, v2: Vector2): float =
v1[0] * v2[0] + v1[1] * v2[1]
func axes(poly: Polygon): seq[Vector2] =
result.setLen(poly.len)
for i, vertex1 in poly:
let vertex2 = poly[if i + 1 == poly.len: 0 else: i + 1]
let edge = (vertex1[0] - vertex2[0], vertex1[1] - vertex2[1])
result[i] = (-edge[1], edge[0])
func projectionOnAxis(poly: Polygon; axis: Vector2): Projection =
result.min = Inf
result.max = -Inf
for vertex in poly:
let p = axis.dot(vertex)
if p < result.min:
result.min = p
if p > result.max:
result.max = p
func projectionOverlaps(proj1, proj2: Projection): bool =
if proj1.max < proj2.min: return false
if proj2.max < proj1.min: return false
result = true
func toPolygon(r: Rectangle): Polygon =
@[(r.x, r.y), (r.x, r.y + r.h), (r.x + r.w, r.y + r.h), (r.x + r.w, r.y)]
func polygonOverlapsRect(poly1: Polygon; rect: Rectangle): bool =
let poly2 = rect.toPolygon
for axes in [poly1.axes, poly2.axes]:
for axis in axes:
let proj1 = poly1.projectionOnAxis(axis)
let proj2 = poly2.projectionOnAxis(axis)
if not projectionOverlaps(proj1, proj2):
return false
result = true
let poly = @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
let rect1 = (4.0, 0.0, 2.0, 2.0)
let rect2 = (1.0, 0.0, 8.0, 2.0)
echo "poly n= ", poly
echo "rect1 = ", rect1, " → ", rect1.toPolygon
echo "rect2 = ", rect2, " → ", rect2.toPolygon
echo()
echo "poly and rect1 overlap? ", polygonOverlapsRect(poly, rect1)
echo "poly and rect2 overlap? ", polygonOverlapsRect(poly, rect2)
</syntaxhighlight>
{{out}}
<pre>poly n= @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
rect1 = (4.0, 0.0, 2.0, 2.0) → @[(4.0, 0.0), (4.0, 2.0), (6.0, 2.0), (6.0, 0.0)]
rect2 = (1.0, 0.0, 8.0, 2.0) → @[(1.0, 0.0), (1.0, 2.0), (9.0, 2.0), (9.0, 0.0)]
poly and rect1 overlap? false
poly and rect2 overlap? true
</pre>
=={{header|Phix}}==
{{trans|Wren}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">axes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)]</span>
<span style="color: #000000;">axes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span> <span style="color: #000080;font-style:italic;">-- ie {-y,x}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">axes</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">axis</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ay</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">axis</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pi</span> <span style="color: #008080;">in</span> <span style="color: #000000;">poly</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">px</span><span style="color: #0000FF;">,</span><span style="color: #000000;">py</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span>
<span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ax</span><span style="color: #0000FF;">*</span><span style="color: #000000;">px</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ay</span><span style="color: #0000FF;">*</span><span style="color: #000000;">py</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">projectionsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">min1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">max1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">min2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">max2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">proj2</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">max1</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">min2</span> <span style="color: #008080;">and</span> <span style="color: #000000;">max2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">min1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">polygonOverlapsRect</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rect</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">poly2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rect</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">axes1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">axes2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">axes</span> <span style="color: #008080;">in</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">axes1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axes2</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">axis</span> <span style="color: #008080;">in</span> <span style="color: #000000;">axes</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">proj1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">proj2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">projectionsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">poly</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">rect1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">rect2</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
poly = %v
rect2 = %v => %v
rect3 = %v => %v
poly and rect1 overlap? %t
poly and rect2 overlap? %t
"""</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rect1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rect1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">rect2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rect2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">polygonOverlapsRect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rect1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">polygonOverlapsRect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rect2</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
poly = {{0,0},{0,2},{1,4},{2,2},{2,0}}
rect2 = {4,0,2,2} => {{4,0},{4,2},{6,2},{6,0}}
rect3 = {1,0,8,2} => {{1,0},{1,2},{9,2},{9,0}}
poly and rect1 overlap? false
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}}==
{{trans|Go}}
<syntaxhighlight lang="raku" line># 20230810 Raku programming solution
class Vector2 { has ( $.x, $.y );
method dot ( \other ) { self.x * other.x + self.y * other.y }
};
class Rectangle { has ( $.x, $.y, $.w, $.h ) }
class Projection { has ( $.min, $.max ) };
sub getAxes(\poly) {
return poly.append(poly[0]).rotor(2=>-1).map: -> (\vertex1,\vertex2) {
my \vector1 = Vector2.new: x => vertex1[0], y => vertex1[1];
my \vector2 = Vector2.new: x => vertex2[0], y => vertex2[1];
my \edge = Vector2.new: x => vector1.x - vector2.x,
y => vector1.y - vector2.y;
$_ = Vector2.new: x => -edge.y, y => edge.x
}
}
sub projectOntoAxis(\poly, \axis) {
my \vertex0 = poly[0];
my \vector0 = Vector2.new: x => vertex0[0], y => vertex0[1];
my $max = my $min = axis.dot: vector0;
for poly -> \vertex {
my \vector = Vector2.new: x => vertex[0], y => vertex[1];
given axis.dot: vector { when $_ < $min { $min = $_ }
when $_ > $max { $max = $_ } }
}
return Projection.new: min => $min, max => $max
}
sub projectionsOverlap(\proj1, \proj2) {
return ! ( proj1.max < proj2.min or proj2.max < proj1.min )
}
sub rectToPolygon( \r ) {
return [(r.x, r.y), (r.x, r.y+r.h), (r.x+r.w, r.y+r.h), (r.x+r.w, r.y)]
}
sub polygonOverlapsRect(\poly1, \rect) {
my \poly2 = rectToPolygon rect;
my (\axes1,\axes2) := (poly1,poly2).map: { getAxes $_ };
for (axes1, axes2) -> \axes {
for axes -> \axis {
my (\proj1,\proj2) := (poly1,poly2).map: { projectOntoAxis $_, axis }
return False unless projectionsOverlap(proj1, proj2)
}
}
return True
}
my \poly = [ <0 0>, <0 2>, <1 4>, <2 2>, <2 0> ];
my \rect1 = Rectangle.new: :4x, :0y, :2h, :2w;
my \rect2 = Rectangle.new: :1x, :0y, :8h, :2w;
say "poly = ", poly;
say "rect1 = ", rectToPolygon(rect1);
say "rect2 = ", rectToPolygon(rect2);
say();
say "poly and rect1 overlap? ", polygonOverlapsRect(poly, rect1);
say "poly and rect2 overlap? ", polygonOverlapsRect(poly, rect2);</syntaxhighlight>
You may [https://ato.pxeger.com/run?1=lVXNbtswDD4OyFNwRQ_26hi20EPhNBl62bXFUOzSBIPXKHE21w5kp7ER5El26aF7qO1pRoqS6zg_w3ywJIrkR32kqJ-vKv6xenn5tSpn_as_734_pnFRwBf5WOZKwAaSuAAHzv3Kw18N7qAHAE-yTPIpTPMS98Z5mUgFLioXMp35FXwALcLZBYvqRlTDtrcdQK_HOJ8RJ87mqdxDot-afgl63lr9O5V_R5NFnrUMnhYZKT7FFakOer1i9Q3msrypZOGMl3laY2wUtpLlSmVAEj9eLmU2dWj-EExcX-V4YEcMR_3QRVfLCPojcMbPUpWyCj0zEcYTcVADCommEIaWMD-T6wgqGI7AWKJzD-q2IJwM9lyIEy5E14XouJDTuaT5YRc6QkxF38wFEWysT3x127puWdcW-vzrQcQ-hUP50x70oiILzDtnZsk5vM3K_KZamAx5MI5xYehlYuisAWKYHA3edggzOEFZ0KUssJSh_TkVCvOlV4sMZwTuYz1H5pyB1p7lSqNTLZiADuT_RCDdOFqZmy-eZbaHi2W9TlCO5F5zbBsbIoq2_0ycNR7xMTc8GOMt5-HtJrxdJ45cA400oAfakP10Uof6xS0eKI2XmD2UhZg-GsXuRXuP11Nv67t5reeCrisQr7xoNkK94VoohTj3-R2SP88zbDK6wejTG-cPjqJKxpbietDML5SfmDVO10dl7qQ5E0OY8xTUkbgk6VAURasmSUxXdSc4vbLF5WAZywL7BQ1IRzQEh51pW9NaNrY96bw0peawLRhbKjqa2pIjFb3mjUWzARabc2FTcQy7cwExBk_XIZcGf4bkT3FaSFhlqcTmeyD7JvkG0Jjvldm9Wkmi21KIDD7AdQDByKNB0BDCJQ2CVwL3YILvBJkQv9Rjm8eCizW6xJRHAbaOSCT0Ww8adXFAPWzUr6x6EddwpiNC_TNP14KRWlCU7pai3nBbWuKYlmAtx20DxdkU2HfOHH60wN0i5La4A7fjQfyHBwyFX3jz0NsH_y8 Attempt This Online!]
=={{header|Wren}}==
Line 17 ⟶ 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
| |||