Check if two polygons overlap
Self-explanatory: given two polygons (as a list of their vertices), check whether they overlap.
You are encouraged to solve this task according to the task description, using any language you may know.
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
Phix
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]} end for return axes end function function projectOntoAxis(sequence poly,axis) atom {ax,ay} = axis, mn, mx for i,pi in poly do atom {px,py} = pi, p = ax*px+ay*py if i=1 then mn = p mx = p elsif p<mn then mn = p elsif p>mx then mx = p end if end for return {mn,mx} end function function projectionsOverlap(sequence proj1, proj2) return proj1[2] >= proj2[1] and proj2[2] >= proj1[1] 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
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