Check if two polygons overlap: Difference between revisions
Added FreeBASIC
(New post.) |
(Added FreeBASIC) |
||
| (3 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 404 ⟶ 399:
{{ out }}
<pre>
polygon1
polygon2
polygon3
polygon1 and polygon2 overlap? false
Line 412 ⟶ 407:
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 521 ⟶ 703:
An implementation of the Separating Axis Theorem algorithm for convex polygons.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
Line 550 ⟶ 731:
public Polygon(List<Point> points) {
vertices = points.stream().map( point -> new Vector(point.x, point.y) ).toList();
}
Line 558 ⟶ 739:
for ( Vector axis : allAxes ) {
Projection projection1 = projectionOnAxis(axis);
Projection projection2 = other.projectionOnAxis(axis);
if ( ! projection1.overlaps(projection2) ) {
Line 595 ⟶ 776:
}
private
for ( int i = 0; i < vertices.size(); i++ ) {
Vector vertex1 = vertices.get(i);
Line 603 ⟶ 784:
axes.addLast(edge.perpendicular());
}
}
| |||