Check if two polygons overlap: Difference between revisions
Added FreeBASIC
(Add Kotlin implementation) |
(Added FreeBASIC) |
||
| (5 intermediate revisions by 2 users not shown) | |||
Line 5:
* [[Check_if_a_polygon_overlaps_with_a_rectangle|Check if a polygon overlaps with a rectangle]]
<br><br>
Line 267 ⟶ 262:
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 371 ⟶ 698:
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>
| |||