Check if a polygon overlaps with a rectangle
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Self-explanatory: given a polygon (as an array/vector/list of its vertices) and a rectangle (in x, y, width, height format), check if they intersect.
- Related tasks
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 rectToPolygon(sequence r) atom {x,y,w,h} = r return {{x, y}, {x, y+h}, {x+w, y+h}, {x+w, y}} end function function polygonOverlapsRect(sequence poly1, rect) sequence poly2 = rectToPolygon(rect), 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 poly = {{0, 0}, {0, 2}, {1, 4}, {2, 2}, {2, 0}}, rect1 = {4, 0, 2, 2}, rect2 = {1, 0, 8, 2}, fmt = """ poly = %v rect2 = %v => %v rect3 = %v => %v poly and rect1 overlap? %t poly and rect2 overlap? %t """ printf(1,fmt,{poly,rect1,rectToPolygon(rect1), rect2,rectToPolygon(rect2), polygonOverlapsRect(poly, rect1), polygonOverlapsRect(poly, rect2)})
- Output:
poly = {{0,0},{0,2},{1,4},{2,2},{2,0}} rect2 = {4,0,2,2} => {{4,0},{4,2},{6,2},{6,0}} rect3 = {1,0,8,2} => {{1,0},{1,2},{9,2},{9,0}} poly and rect1 overlap? false poly and rect2 overlap? true
Wren
This is just a special case of the Check if two polygons overlap task where one of the polygons is a rectangle though, for convenience, the common code is repeated here.
import "./vector" for Vector2
import "./dynamic" for Tuple
var Projection = Tuple.create("Projection", ["min", "max"])
var Rectangle = Tuple.create("Rectangle", ["x", "y", "w", "h"])
/* 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 rectToPolygon = Fn.new { |r|
return [[r.x, r.y], [r.x, r.y + r.h], [r.x + r.w, r.y + r.h], [r.x + r.w, r.y]]
}
var polygonOverlapsRect = Fn.new { |poly1, rect|
// Convert 'rect' object into polygon form.
var poly2 = rectToPolygon.call(rect)
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 poly = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]]
var rect1 = Rectangle.new(4, 0, 2, 2)
var rect2 = Rectangle.new(1, 0, 8, 2)
System.print("poly = %(poly)")
System.print("rect1 = %(rect1) => %(rectToPolygon.call(rect1))")
System.print("rect2 = %(rect2) => %(rectToPolygon.call(rect2))")
System.print()
System.print("poly and rect1 overlap? %(polygonOverlapsRect.call(poly, rect1))")
System.print("poly and rect2 overlap? %(polygonOverlapsRect.call(poly, rect2))")
- Output:
poly = [[0, 0], [0, 2], [1, 4], [2, 2], [2, 0]] rect1 = (4, 0, 2, 2) => [[4, 0], [4, 2], [6, 2], [6, 0]] rect2 = (1, 0, 8, 2) => [[1, 0], [1, 2], [9, 2], [9, 0]] poly and rect1 overlap? false poly and rect2 overlap? true