Check if two polygons overlap: Difference between revisions
Added FreeBASIC
(Added Go) |
(Added FreeBASIC) |
||
| (25 intermediate revisions by 11 users not shown) | |||
Line 1:
{{task}}Self-explanatory: given two polygons (as a list of their vertices), check whether they overlap.
;Related tasks
* [[Determine_if_two_triangles_overlap|Determine if two triangles overlap]]
* [[Check_if_a_polygon_overlaps_with_a_rectangle|Check if a polygon overlaps with a rectangle]]
<br><br>
=={{header|ALGOL 68}}==
{{Trans|Go|but using operators instead of functions and representing a polygon as a row of points instead of a [][]REAL}}
<syntaxhighlight lang="algol68">
BEGIN # test for overlapping 2D polygons #
# - 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 #
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 ppolygons 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 # ;
# test cases #
POLYGON poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) )
, poly2 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )
, poly3 = ( ( 1, 0 ), ( 1, 2 ), ( 5, 4 ), ( 9, 2 ), ( 9, 0 ) )
;
print( ( "poly1 = ", TOSTRING poly1, newline ) );
print( ( "poly2 = ", TOSTRING poly2, newline ) );
print( ( "poly3 = ", TOSTRING poly3, newline ) );
print( ( newline ) );
print( ( "poly1 and poly2 overlap? ", IF poly1 OVERLAPS poly2 THEN "yes" ELSE "no" FI, newline ) );
print( ( "poly1 and poly3 overlap? ", IF poly1 OVERLAPS poly3 THEN "yes" ELSE "no" FI, newline ) );
print( ( "poly2 and poly3 overlap? ", IF poly2 OVERLAPS poly3 THEN "yes" ELSE "no" FI, newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
poly1 = ( ( 0, 0 ), ( 0, 2 ), ( 1, 4 ), ( 2, 2 ), ( 2, 0 ) )
poly2 = ( ( 4, 0 ), ( 4, 2 ), ( 5, 4 ), ( 6, 2 ), ( 6, 0 ) )
poly3 = ( ( 1, 0 ), ( 1, 2 ), ( 5, 4 ), ( 9, 2 ), ( 9, 0 ) )
poly1 and poly2 overlap? no
poly1 and poly3 overlap? yes
poly2 and poly3 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;
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;
}
bool polygonsOverlap(double poly1[][2], double poly2[][2], size_t len1, size_t len2) {
int i;
Vector2 axis, axes1[len1], axes2[len2];
Projection proj1, proj2;
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 poly1[][2] = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} };
double poly2[][2] = { {4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0} };
double poly3[][2] = { {1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0} };
printf("poly1 = ");
printPoly(poly1, 5);
printf("poly2 = ");
printPoly(poly2, 5);
printf("poly3 = ");
printPoly(poly3, 5);
printf("\n");
printf("poly1 and poly2 overlap? %s\n", polygonsOverlap(poly1, poly2, 5, 5) ? "true" : "false");
printf("poly1 and poly3 overlap? %s\n", polygonsOverlap(poly1, poly3, 5, 5) ? "true" : "false");
printf("poly2 and poly3 overlap? %s\n", polygonsOverlap(poly2, poly3, 5, 5) ? "true" : "false");
return 0;
}</syntaxhighlight>
{{out}}
<pre>
poly1 = { {0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0} }
poly2 = { {4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0} }
poly3 = { {1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0} }
poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>
=={{header|C++}}==
An implementation of the Separating Axis Theorem algorithm for convex polygons.
<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;
};
int main() {
Polygon polygon1(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) } );
Polygon polygon2(std::vector<Point> { Point(4.0, 0.0), Point(4.0, 2.0), Point(5.0, 4.0),
Point(6.0, 2.0), Point(6.0, 0.0) } );
Polygon polygon3(std::vector<Point> { Point(1.0, 0.0), Point(1.0, 2.0), Point(5.0, 4.0),
Point(9.0, 2.0), Point(9.0, 0.0) } );
std::cout << "polygon1: " << polygon1.to_string() << std::endl;
std::cout << "polygon2: " << polygon2.to_string() << std::endl;
std::cout << "polygon3: " << polygon3.to_string() << std::endl;
std::cout << std::boolalpha << std::endl;
std::cout << "polygon1 and polygon2 overlap? " << polygon1.overlaps(polygon2) << std::endl;
std::cout << "polygon1 and polygon3 overlap? " << polygon1.overlaps(polygon3) << std::endl;
std::cout << "polygon2 and polygon3 overlap? " << polygon2.overlaps(polygon3) << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
polygon1: [ (0.000000, 0.000000) (0.000000, 2.000000) (1.000000, 4.000000) (2.000000, 2.000000) (2.000000, 0.000000) ]
polygon2: [ (4.000000, 0.000000) (4.000000, 2.000000) (5.000000, 4.000000) (6.000000, 2.000000) (6.000000, 0.000000) ]
polygon3: [ (1.000000, 0.000000) (1.000000, 2.000000) (5.000000, 4.000000) (9.000000, 2.000000) (9.000000, 0.000000) ]
polygon1 and polygon2 overlap? false
polygon1 and polygon3 overlap? true
polygon2 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
.
poly1[][] = [ [ 0 0 ] [ 0 2 ] [ 1 4 ] [ 2 2 ] [ 2 0 ] ]
poly2[][] = [ [ 4 0 ] [ 4 2 ] [ 5 4 ] [ 6 2 ] [ 6 0 ] ]
poly3[][] = [ [ 1 0 ] [ 1 2 ] [ 5 4 ] [ 9 2 ] [ 9 0 ] ]
#
polyDraw 900 poly1[][]
polyDraw 090 poly2[][]
polyDraw 009 poly3[][]
#
polyOverlap poly1[][] poly2[][] r ; print r
polyOverlap poly1[][] poly3[][] r ; print r
polyOverlap poly2[][] 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
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
Function polygonsOverlap(poly1() As Vector2, poly2() As Vector2) As Boolean
Dim As Integer i
Dim As Vector2 axis
Dim As Projection proj1, proj2
Dim As Vector2 axes1(Ubound(poly1)), axes2(Ubound(poly2))
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 poly1(4)
poly1(0).x = 0: poly1(0).y = 0
poly1(1).x = 0: poly1(1).y = 2
poly1(2).x = 1: poly1(2).y = 4
poly1(3).x = 2: poly1(3).y = 2
poly1(4).x = 2: poly1(4).y = 0
Dim As Vector2 poly2(4)
poly2(0).x = 4: poly2(0).y = 0
poly2(1).x = 4: poly2(1).y = 2
poly2(2).x = 5: poly2(2).y = 4
poly2(3).x = 6: poly2(3).y = 2
poly2(4).x = 6: poly2(4).y = 0
Dim As Vector2 poly3(4)
poly3(0).x = 1: poly3(0).y = 0
poly3(1).x = 1: poly3(1).y = 2
poly3(2).x = 5: poly3(2).y = 4
poly3(3).x = 9: poly3(3).y = 2
poly3(4).x = 9: poly3(4).y = 0
Print "poly1 = ";
printPoly(poly1())
Print "poly2 = ";
printPoly(poly2())
Print "poly3 = ";
printPoly(poly3())
Print
Print "poly1 and poly2 overlap? "; Iif(polygonsOverlap(poly1(), poly2()), "true", "false")
Print "poly1 and poly3 overlap? "; Iif(polygonsOverlap(poly1(), poly3()), "true", "false")
Print "poly2 and poly3 overlap? "; Iif(polygonsOverlap(poly2(), poly3()), "true", "false")
Sleep</syntaxhighlight>
{{out}}
<pre>poly1 = {{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}
poly2 = {{4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0}}
poly3 = {{1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0}}
poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true</pre>
=={{header|Go}}==
Line 114 ⟶ 694:
poly2 = [[4 0] [4 2] [5 4] [6 2] [6 0]]
poly3 = [[1 0] [1 2] [5 4] [9 2] [9 0]]
poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>
=={{header|Java}}==
An implementation of the Separating Axis Theorem algorithm for convex polygons.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
public final class CheckIfTwoPolygonsOverlap {
public static void main(String[] args) {
Polygon polygon1 = 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) ));
Polygon polygon2 = new Polygon(List.of( new Point(4.0, 0.0), new Point(4.0, 2.0), new Point(5.0, 4.0),
new Point(6.0, 2.0), new Point(6.0, 0.0) ));
Polygon polygon3 = new Polygon(List.of( new Point(1.0, 0.0), new Point(1.0, 2.0), new Point(5.0, 4.0),
new Point(9.0, 2.0), new Point(9.0, 0.0) ));
System.out.println("polygon1 = " + polygon1);
System.out.println("polygon2 = " + polygon2);
System.out.println("polygon3 = " + polygon3);
System.out.println();
System.out.println("polygon1 and polygon2 overlap? " + polygon1.overlaps(polygon2));
System.out.println("polygon1 and polygon3 overlap? " + polygon1.overlaps(polygon3));
System.out.println("polygon2 and polygon3 overlap? " + polygon2.overlaps(polygon3));
}
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>
polygon1 = [ (0.0, 0.0) (0.0, 2.0) (1.0, 4.0) (2.0, 2.0) (2.0, 0.0) ]
polygon2 = [ (4.0, 0.0) (4.0, 2.0) (5.0, 4.0) (6.0, 2.0) (6.0, 0.0) ]
polygon3 = [ (1.0, 0.0) (1.0, 2.0) (5.0, 4.0) (9.0, 2.0) (9.0, 0.0) ]
polygon1 and polygon2 overlap? false
polygon1 and polygon3 overlap? true
polygon2 and polygon3 overlap? true
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]''' (2D convex polygons)
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
In the following:
* a vertex is represented by a pair of x, y coordinates in the plane;
* a polygon is represented as a list of vertices;
* a projection is represented by a JSON object {min, max}
<syntaxhighlight lang="jq">
# Input: [$A, $B] where $A and $B are points
# Output: the vector $B - $A
def AB:
. as [$A, $B]
| [ $B[0] - $A[0], $B[1] - $A[1]];
# Input: a vector
# Output: perpendicular
def perp: [- .[1], .[0]];
# dot product of this and $v, assumed to be of the same dimension
def dot($v):
. as $this
| reduce range(0; $this|length) as $i (0; . + ($this[$i] * $v[$i] ));
def getAxes:
. as $poly
| reduce range(0; $poly|length) as $i ([];
$poly[$i] as $vertex1
| $poly[if $i+1 == ($poly|length) then 0 else $i+1 end] as $vertex2
| . + [ [$vertex1, $vertex2] | AB | perp] );
# emit {min, max}
def projectOntoAxis($axis):
. as $poly
| { max: - infinite, min: infinite }
| reduce range(0; $poly|length) as $i (.;
($axis | dot( $poly[$i] )) as $p
| if $p < .min then .min = $p else . end
| if $p > .max then .max = $p else . end ) ;
def projectionsOverlap($proj1; $proj2):
if $proj1.max < $proj2.min then false
elif $proj2.max < $proj1.min then false
else true
end;
# If there's an axis for which the projections do not overlap, then false; else true
def polygonsOverlap($poly1; $poly2):
any( $poly1, $poly2 | getAxes[];
. as $axis
| ($poly1 | projectOntoAxis($axis)) as $proj1
| ($poly2 | projectOntoAxis($axis)) as $proj2
| projectionsOverlap($proj1; $proj2) | not)
| not;
def poly1: [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]];
def poly2: [[4, 0], [4, 2], [5, 4], [6, 2], [6, 0]];
def poly3: [[1, 0], [1, 2], [5, 4], [9, 2], [9, 0]];
def task:
"poly1 = \(poly1)",
"poly2 = \(poly2)",
"poly3 = \(poly3)",
"",
"poly1 and poly2 overlap? \(polygonsOverlap(poly1; poly2))",
"poly1 and poly3 overlap? \(polygonsOverlap(poly1; poly3))",
"poly2 and poly3 overlap? \(polygonsOverlap(poly2; poly3))"
;
task
</syntaxhighlight>
{{output}}
As for [[#Wren]]
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Plots
using Polyhedra
using GLPK
lib = DefaultLibrary{Float64}(GLPK.Optimizer)
const poly1 = polyhedron(vrep([
0 0
0 2
1 4
2 2
2 0
]), lib)
const poly2 = polyhedron(vrep([
4 0
4 2
5 4
6 2
6 0
]), lib)
const poly3 = polyhedron(vrep([
1 0
1 2
5 4
9 2
9 0
]), lib)
println("Polygons poly1 and poly2 intersect at ", npoints(intersect(poly1, poly2)), " points.")
println("Polygons poly1 and poly3 intersect at ", npoints(intersect(poly1, poly3)), " points.")
println("Polygons poly2 and poly3 intersect at ", npoints(intersect(poly2, poly3)), " points.")
const P1 = polyhedron(vrep([
-1.9 -1.7
-1.8 0.5
1.7 0.7
1.9 -0.3
0.9 -1.1
]), lib)
const P2 = polyhedron(vrep([
-2.5 -1.1
-0.8 0.8
0.1 0.9
1.8 -1.2
1.3 0.1
]), lib)
Pint = intersect(P1, P2)
println("Polygons P1 and P2 intersect at ", npoints(Pint), " points.")
plot(P1, color="blue", alpha=0.2)
plot!(P2, color="red", alpha=0.2)
plot!(Pint, color="yellow", alpha=0.6)
</syntaxhighlight>{{out}}
<pre>
Polygons poly1 and poly2 intersect at 0 points.
Polygons poly1 and poly3 intersect at 5 points.
Polygons poly2 and poly3 intersect at 5 points.
Polygons P1 and P2 intersect at 8 points.
</pre>
[[File:Poly intersect.svg|thumb|center]]
=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="Kotlin">
import kotlin.math.*
data class Vector2(val x: Double, val y: Double) {
fun dot(other: Vector2): Double = this.x * other.x + this.y * other.y
}
class Projection(var min: Double = Double.POSITIVE_INFINITY, var max: Double = Double.NEGATIVE_INFINITY) {
fun overlaps(proj2: Projection): Boolean = !(this.max < proj2.min || proj2.max < this.min)
}
class Polygon(vertices: List<Pair<Double, Double>>) {
private val vertices: List<Vector2> = vertices.map { Vector2(it.first, it.second) }
private val axes: List<Vector2> = getAxes()
public fun getVertices(): List<Vector2> { return vertices}
private fun getAxes(): List<Vector2> {
val axes = mutableListOf<Vector2>()
for (i in vertices.indices) {
val vertex1 = vertices[i]
val vertex2 = if (i + 1 == vertices.size) vertices[0] else vertices[i + 1]
val edge = Vector2(vertex1.x - vertex2.x, vertex1.y - vertex2.y)
axes.add(Vector2(-edge.y, edge.x))
}
return axes
}
fun projectionOnAxis(axis: Vector2): Projection {
return Projection().apply {
vertices.forEach { vertex ->
val p = axis.dot(vertex)
if (p < min) min = p
if (p > max) max = p
}
}
}
fun overlaps(other: Polygon): Boolean {
(this.axes + other.axes).forEach { axis ->
val proj1 = this.projectionOnAxis(axis)
val proj2 = other.projectionOnAxis(axis)
if (!proj1.overlaps(proj2)) return false
}
return true
}
}
fun main() {
val poly1 = Polygon(listOf(0.0 to 0.0, 0.0 to 2.0, 1.0 to 4.0, 2.0 to 2.0, 2.0 to 0.0))
val poly2 = Polygon(listOf(4.0 to 0.0, 4.0 to 2.0, 5.0 to 4.0, 6.0 to 2.0, 6.0 to 0.0))
val poly3 = Polygon(listOf(1.0 to 0.0, 1.0 to 2.0, 5.0 to 4.0, 9.0 to 2.0, 9.0 to 0.0))
val polygons = listOf(poly1, poly2, poly3)
polygons.forEachIndexed { index, polygon ->
println("poly${index + 1} = ${polygon.getVertices()}")
}
println("poly1 and poly2 overlap? ${polygons[0].overlaps(polygons[1])}")
println("poly1 and poly3 overlap? ${polygons[0].overlaps(polygons[2])}")
println("poly2 and poly3 overlap? ${polygons[1].overlaps(polygons[2])}")
}
</syntaxhighlight>
{{out}}
<pre>
poly1 = [Vector2(x=0.0, y=0.0), Vector2(x=0.0, y=2.0), Vector2(x=1.0, y=4.0), Vector2(x=2.0, y=2.0), Vector2(x=2.0, y=0.0)]
poly2 = [Vector2(x=4.0, y=0.0), Vector2(x=4.0, y=2.0), Vector2(x=5.0, y=4.0), Vector2(x=6.0, y=2.0), Vector2(x=6.0, y=0.0)]
poly3 = [Vector2(x=1.0, y=0.0), Vector2(x=1.0, y=2.0), Vector2(x=5.0, y=4.0), Vector2(x=9.0, y=2.0), Vector2(x=9.0, y=0.0)]
poly1 and poly2 overlap? false
poly1 and poly3 overlap? true
poly2 and poly3 overlap? true
</pre>
=={{header|Nim}}==
{{trans|Wren}}
{{trans|Go}}
<syntaxhighlight lang="Nim">type
Vector2 = (float, float)
Projection = tuple[min, max: float]
Polygon = seq[Vector2]
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 polygonsOverlap(poly1, poly2: Polygon): bool =
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 poly1 = @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
let poly2 = @[(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)]
let poly3 = @[(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)]
echo "poly1 = ", poly1
echo "poly2 = ", poly2
echo "poly3 = ", poly3
echo()
echo "poly1 and poly2 overlap? ", polygonsOverlap(poly1, poly2)
echo "poly1 and poly3 overlap? ", polygonsOverlap(poly1, poly3)
echo "poly2 and poly3 overlap? ", polygonsOverlap(poly2, poly3)
</syntaxhighlight>
{{out}}
<pre>poly1 = @[(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
poly2 = @[(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)]
poly3 = @[(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)]
poly1 and poly2 overlap? false
Line 123 ⟶ 1,122:
{{trans|Wren}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Polygons_overlap.exw</span>
<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>
Line 129 ⟶ 1,129:
<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>
Line 135 ⟶ 1,135:
<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 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 style="color: #000000;">p</span><span style="color:
<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;">
<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: #
<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>
Line 194 ⟶ 1,189:
poly2 and poly3 overlap? true
</pre>
=={{header|Python}}==
{{trans|Nim}}
<syntaxhighlight lang="python3">
# overlaying_polygons.py by xing216
from math import inf
class Vector2:
def __init__(self, x: float, y: float) -> None:
self.x = x
self.y = y
def dot(self, other: 'Vector2') -> float:
return self.x * other.x + self.y * other.y
def __repr__(self) -> str:
return f'({self.x}, {self.y})'
class Projection:
min: float
max: float
def overlaps(self, proj2: 'Projection') -> bool:
if self.max < proj2.min or proj2.max < self.min: return False
return True
class Polygon:
def __init__(self, vertices: list[tuple[float, float]]) -> None:
self.vertices = [Vector2(*vertex) for vertex in vertices]
self.axes = self.get_axes()
def get_axes(self) -> list[Vector2]:
axes = []
for i, vertex1 in enumerate(self.vertices):
if i + 1 == len(self.vertices): vertex2 = self.vertices[0]
else: vertex2 = self.vertices[i + 1]
edge = (vertex1.x - vertex2.x, vertex1.y - vertex2.y)
axes.append(Vector2(-edge[1], edge[0]))
return axes
def projection_on_axis(self, axis: Vector2) -> Projection:
projection = Projection()
projection.min = inf
projection.max = -inf
for vertex in self.vertices:
p = axis.dot(vertex)
if p < projection.min:
projection.min = p
if p > projection.max:
projection.max = p
return projection
def overlaps(self, other: 'Polygon') -> bool:
for axes in [self.axes, other.axes]:
for axis in axes:
proj1 = self.projection_on_axis(axis)
proj2 = other.projection_on_axis(axis)
if not proj1.overlaps(proj2): return False
return True
poly1 = Polygon([(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)])
poly2 = Polygon([(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)])
poly3 = Polygon([(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.0)])
polygons = (poly1, poly2, poly3)
for i, polygon in enumerate(polygons):
print(f'poly{i+1} = {polygon.vertices}')
print(f'poly1 and poly2 overlap? {polygons[0].overlaps(polygons[1])}')
print(f'poly1 and poly3 overlap? {polygons[0].overlaps(polygons[2])}')
print(f'poly2 and poly3 overlap? {polygons[1].overlaps(polygons[2])}')
</syntaxhighlight>
{{out}}
<pre>
poly1 = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
poly2 = [(4.0, 0.0), (4.0, 2.0), (5.0, 4.0), (6.0, 2.0), (6.0, 0.0)]
poly3 = [(1.0, 0.0), (1.0, 2.0), (5.0, 4.0), (9.0, 2.0), (9.0, 0.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 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 polygonsOverlap( \poly1, \poly2 ) {
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 \poly1 = [ <0 0>, <0 2>, <1 4>, <2 2>, <2 0> ];
my \poly2 = [ <4 0>, <4 2>, <5 4>, <6 2>, <6 0> ];
my \poly3 = [ <1 0>, <1 2>, <5 4>, <9 2>, <9 0> ];
say "poly1 = ", poly1;
say "poly2 = ", poly2;
say "poly3 = ", poly3;
say();
say "poly1 and poly2 overlap? ", polygonsOverlap(poly1, poly2);
say "poly1 and poly3 overlap? ", polygonsOverlap(poly1, poly3);
say "poly2 and poly3 overlap? ", polygonsOverlap(poly2, poly3);</syntaxhighlight>
You may [https://ato.pxeger.com/run?1=jVXNbtpAED5W8lNMIw52ayx7oVGDwVUuvVXpoeolRJEbFnBLbOSfxBbiSXrJoX2pPk1ndtY_MZSGA7s7O998M_PNws9fafijeHr6XeTL4fs_rz7dbcIsg6_yLk9SATtYhxmYMHBKG78qsHwDAO5lvk4WsEhyvJsn-VqmYKFzJjdLp4Q3oEy4e8umqjFVsDf2PhgG83xOk-9IFSVxh-o-ionsPiwx6N43jKz4BiuZX5aSHObbZFMRHWWSyrxIYyCTE263Ml6YtL92bywnTbAGU8yCoWdhtO0EhgGY8weZ5rL0bL0ROhKVVQEaqXIPZnUPnFg-TqCEWQAaicFtqLoG78Y_CCFOhBD9EKIXQi5WkvbHQ6gMsbtDvRekjkaf-FRddNVBVzX14PYo45DScSqdsTqUhEApWZwty3gV58llGTUi2TAP6ag7zL2hcl2k0TL57Q3Ruie65va75tZdQ_yAxoVbpk5RjDtid3BKJ7pUV3kvk1Sx0zjohI6MwIlE-nl0xFtFDzI-4MXhflyjHfs75dx2dYpo2v9XuxoccJk7XjR4z1K0j6F9VJy5IgoUoQ0KyHF66qF_doUFbcKtEhCtns2r6D231-ig7tUjnaq9oHcL1Fo-NBeeurAaNuz8qqXSo6KYcBWdYTFxemSGD5UWfKaTGZjsqzz1m941Pw3UjUZgk7GgsSQ1bWuhyUWd-SJqLqDm5vq5_H9z9yd_cGsr9VkQ_uimfQw3mYQi3kj84Tvsuakbrgk1_EDcL2khqZU0qCohHINrmLrgBjYtghYPxrQIPgm8A5zQGiIYMmbImJ3eMeScT-c9yIghHkO8Z5ALPl1oiJGFFZzVqZ3ZSnDPb82iNYuOedSaR8psWn43VhgvGAMJN-xD7d6dJj1LLNJR_Oil-JH1LOmX40WD539V_eda_8n-BQ Attempt This Online!]
=={{header|Wren}}==
Line 201 ⟶ 1,325:
The approach here is based on the Separating Axis theorem ("SAT"). See [https://dyn4j.org/2010/01/sat/ here] for a simple explanation of this with pseudo-code.
<syntaxhighlight lang="
import "./dynamic" for Tuple
| |||