Check if two polygons overlap: Difference between revisions
Content added Content deleted
(added Raku programming solution) |
|||
Line 551: | Line 551: | ||
sub projectionsOverlap ( \proj1, \proj2 ) { |
sub projectionsOverlap ( \proj1, \proj2 ) { |
||
return |
return ! ( proj1.max < proj2.min or proj2.max < proj1.min ) |
||
return True |
|||
} |
} |
||
Line 577: | Line 576: | ||
say "poly1 and poly3 overlap? ", polygonsOverlap(poly1, poly3); |
say "poly1 and poly3 overlap? ", polygonsOverlap(poly1, poly3); |
||
say "poly2 and poly3 overlap? ", polygonsOverlap(poly2, poly3);</syntaxhighlight> |
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!] |
|||
You may [https://ato.pxeger.com/run?1=jVXNbptAED5W4ilGkQ-4xQjWbtQY21UuvaaHqpc4imhY27QEEOAEZPlJesmhfak-TWd2lh9j1w0HdnZ2vpnZ-Wbg56_M_7F9efm9LVajD3_eBA-Rn-fwVT4USSZgBxs_BxMGdmnhq4KhZwDAoyw2SQBBUuDZMik2MoMhGucyWtklvAWlQukdq6pGVcHe2HtgGBznc5Z8x1BhEndCPYYxBXv0S3S69wwj336DtSyuS0kGyzSJKgpHmWSy2GYxkMr201TGgUnyrXM3tLME72CK-WLkDtFbOoXRAszlk8wKWbqWFoT2RNeqAJV0cxfmdQ3sWD5PoYT5AjQSnVtQdRXunXfkQpxxIfouRM-FDNaS5NMuVIZY3ZGWBbGj0WeeqouuOuiqDj24PxlxROnYlc5YbUpCIJVMTso03sRFcl2GDUkWLH3a6gpzbei6DobRNHntCYV1zlTN6VfNqauG-AG1C5dM7cIYJYpuY5dO9VUdZb1KMhWd2kEndKIFziTSz6ND3jp8kvFRXGzu5w3qsb4zzm1Xp4iq_X-5q8ELvuaOFw3eMxXtMLRDxZmrQAsV0AIFZD899tA-v8ELRX6qCESta_EqeuP2yY9yCeEK7ZSZmtWZkgWNL1CFedMcuOqAvx_azZdsK5skkJB1m4HuIJUArqLTQyY2lcxxfmnB6Z3OwWRbZalHfdd8MahIDe8mY0FjqQNIrPknE7Xng7A5gDo2l4Wr8u_Y_YEY3FuqKZgnfg5quY0jid_DYypMzYMOqOFHnNelpP5VCWF33MLMAWdh0SJocWFCi-CdwDPAxq0hgiEThkzY6D1DLnl32YOMGeIyxD2AXPHuSkOM3K_gok7twlKEu16rFq1adNTjVj1WanPodX35ccAYSLhgH2vzbjfpXmKSTuLHr8WPhwdJvx4vGjz_bPU_t_73_gU Attempt This Online!] |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
Revision as of 16:32, 10 August 2023
Check if two polygons overlap
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Self-explanatory: given two polygons (as a list of their vertices), check whether they overlap.
- Related tasks
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;
}
- Output:
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
Go
package main
import "fmt"
type Vector2 struct {
x, y float64
}
type Projection struct {
min, max 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 polygonsOverlap(poly1, poly2 [][2]float64) bool {
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() {
poly1 := [][2]float64{{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}
poly2 := [][2]float64{{4, 0}, {4, 2}, {5, 4}, {6, 2}, {6, 0}}
poly3 := [][2]float64{{1, 0}, {1, 2}, {5, 4}, {9, 2}, {9, 0}}
fmt.Println("poly1 = ", poly1)
fmt.Println("poly2 = ", poly2)
fmt.Println("poly3 = ", poly3)
fmt.Println()
fmt.Println("poly1 and poly2 overlap?", polygonsOverlap(poly1, poly2))
fmt.Println("poly1 and poly3 overlap?", polygonsOverlap(poly1, poly3))
fmt.Println("poly2 and poly3 overlap?", polygonsOverlap(poly2, poly3))
}
- Output:
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
jq
Adapted from Wren (2D convex polygons)
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}
# 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
- Output:
As for #Wren
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)
- Output:
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.
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)
- Output:
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
Phix
-- demo\rosetta\Polygons_overlap.exw with javascript_semantics function getAxes(sequence poly) integer l = length(poly) sequence axes = repeat(0,l) for i=1 to l do sequence p = poly[i], n = poly[iff(i=l?1:i+1)] axes[i] = {n[2]-p[2],p[1]-n[1]} -- ie {-y,x} end for return axes end function function projectOntoAxis(sequence poly,axis) atom {ax,ay} = axis sequence p = repeat(0,length(poly)) for i,pi in poly do atom {px,py} = pi p[i] = ax*px+ay*py end for return {min(p),max(p)} end function function projectionsOverlap(sequence proj1, proj2) atom {min1,max1} = proj1, {min2,max2} = proj2 return max1>=min2 and max2>=min1 end function function polygonsOverlap(sequence poly1, poly2) sequence axes1 = getAxes(poly1), axes2 = getAxes(poly2) for axes in {axes1, axes2} do for axis in axes do sequence proj1 = projectOntoAxis(poly1, axis), proj2 = projectOntoAxis(poly2, axis) if not projectionsOverlap(proj1, proj2) then return false end if end for end for return true end function constant 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}}, fmt = """ poly1 = %v poly2 = %v poly3 = %v poly1 and poly2 overlap? %t poly1 and poly3 overlap? %t poly2 and poly3 overlap? %t """ printf(1,fmt,{poly1,poly2,poly3,polygonsOverlap(poly1, poly2), polygonsOverlap(poly1, poly3), polygonsOverlap(poly2, poly3)})
- Output:
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
Raku
# 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);
You may Attempt This Online!
Wren
The task description doesn't say whether the polygons are 2D or 3D and whether they're convex or not. So for now, I've assumed the simplest case of 2D convex polygons though a non-convex polygon can always be decomposed into a combination of convex polygons.
The approach here is based on the Separating Axis theorem ("SAT"). See here for a simple explanation of this with pseudo-code.
import "./vector" for Vector2
import "./dynamic" for Tuple
var Projection = Tuple.create("Projection", ["min", "max"])
/* In the following a polygon is represented as a list of vertices
and a vertex by a pair of x, y coordinates in the plane. */
var getAxes = Fn.new { |poly|
var axes = List.filled(poly.count, null)
for (i in 0...poly.count) {
var vertex1 = poly[i]
var vertex2 = poly[(i+1 == poly.count) ? 0 : i+1]
var vector1 = Vector2.new(vertex1[0], vertex1[1])
var vector2 = Vector2.new(vertex2[0], vertex2[1])
var edge = vector1 - vector2
axes[i] = edge.perp
}
return axes
}
var projectOntoAxis = Fn.new { |poly, axis|
var vertex0 = poly[0]
var vector0 = Vector2.new(vertex0[0], vertex0[1])
var min = axis.dot(vector0)
var max = min
for (i in 1...poly.count) {
var vertex = poly[i]
var vector = Vector2.new(vertex[0], vertex[1])
var p = axis.dot(vector)
if (p < min) {
min = p
} else if (p > max) {
max = p
}
}
return Projection.new(min, max)
}
var projectionsOverlap = Fn.new { |proj1, proj2|
if (proj1.max < proj2.min) return false
if (proj2.max < proj1.min) return false
return true
}
var polygonsOverlap = Fn.new { |poly1, poly2|
var axes1 = getAxes.call(poly1)
var axes2 = getAxes.call(poly2)
for (axes in [axes1, axes2]) {
for (axis in axes) {
var proj1 = projectOntoAxis.call(poly1, axis)
var proj2 = projectOntoAxis.call(poly2, axis)
if (!projectionsOverlap.call(proj1, proj2)) return false
}
}
return true
}
var poly1 = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]]
var poly2 = [[4, 0], [4, 2], [5, 4], [6, 2], [6, 0]]
var poly3 = [[1, 0], [1, 2], [5, 4], [9, 2], [9, 0]]
System.print("poly1 = %(poly1)")
System.print("poly2 = %(poly2)")
System.print("poly3 = %(poly3)")
System.print()
System.print("poly1 and poly2 overlap? %(polygonsOverlap.call(poly1, poly2))")
System.print("poly1 and poly3 overlap? %(polygonsOverlap.call(poly1, poly3))")
System.print("poly2 and poly3 overlap? %(polygonsOverlap.call(poly2, poly3))")
- Output:
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