Check if a polygon overlaps with a rectangle: Difference between revisions
Content added Content deleted
(Added Wren) |
|||
Line 12:
=={{header|Phix}}==
{{trans|Wren}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">axes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">?</span><span style="color: #000000;">1</span><span style="color: #0000FF;">:</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)]</span>
<span style="color: #000000;">axes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">axes</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">axis</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">ax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ay</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pi</span> <span style="color: #008080;">in</span> <span style="color: #000000;">poly</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">px</span><span style="color: #0000FF;">,</span><span style="color: #000000;">py</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ax</span><span style="color: #0000FF;">*</span><span style="color: #000000;">px</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ay</span><span style="color: #0000FF;">*</span><span style="color: #000000;">py</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mn</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">></span><span style="color: #000000;">mx</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">projectionsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">proj1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">h</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">polygonOverlapsRect</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rect</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">poly2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rect</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">axes1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">axes2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">getAxes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">axes</span> <span style="color: #008080;">in</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">axes1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axes2</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">axis</span> <span style="color: #008080;">in</span> <span style="color: #000000;">axes</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">proj1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">proj2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">projectOntoAxis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">axis</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">projectionsOverlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">proj1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">proj2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">poly</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">rect1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">rect2</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
poly = %v
rect2 = %v => %v
rect3 = %v => %v
poly and rect1 overlap? %t
poly and rect2 overlap? %t
"""</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rect1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rect1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">rect2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rectToPolygon</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rect2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">polygonOverlapsRect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rect1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">polygonOverlapsRect</span><span style="color: #0000FF;">(</span><span style="color: #000000;">poly</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rect2</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
|
Revision as of 15:43, 30 July 2023
![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.
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