Check if two polygons overlap: Difference between revisions
Added FreeBASIC
m (→{{header|Wren}}: Changed to Wren S/H) |
(Added FreeBASIC) |
||
| (8 intermediate revisions by 4 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>
Line 513 ⟶ 974:
[[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}}==
Line 648 ⟶ 1,188:
poly1 and poly3 overlap? true
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>
| |||