Check if a polygon overlaps with a rectangle: Difference between revisions
Check if a polygon overlaps with a rectangle (view source)
Revision as of 06:00, 23 October 2023
, 7 months agojulia example
m (→{{header|ALGOL 68}}: notes) |
(julia example) |
||
Line 467:
poly1 and r1 overlap? false
poly1 and r2 overlap? true
=={{header|Julia}}==
{{trans|Nim}}
<syntaxhighlight lang="julia">import LinearAlgebra: dot
const Vector2 = Tuple{Float64, Float64}
const Projection = Vector2
const Polygon = Vector{Vector2}
const Rectangle = NamedTuple{(:x, :y, :w, :h), NTuple{4, Float64}}
function axes(poly::Polygon)
plen = length(poly)
result = [(0.0, 0.0) for _ in 1:plen]
for (i, vertex1) in enumerate(poly)
vertex2 = i == plen ? first(poly) : poly[i+1] # wraps around
edge = (vertex1[1] - vertex2[1], vertex1[2] - vertex2[2])
result[i] = (-edge[2], edge[1])
end
return result
end
function projectiononaxis(poly::Polygon, axis::Vector2)
resultmin = Inf
resultmax = -Inf
for vertex in poly
p = dot(axis, vertex)
if p < resultmin
resultmin = p
elseif p > resultmax
resultmax = p
end
end
return (resultmin, resultmax)
end
projectionoverlaps(p1::Projection, p2::Projection) = p1[2] <= p2[1] && p2[2] >= p1[1]
function Polygon(r::Rectangle)
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)]
end
function polygonoverlapsrect(poly1::Polygon, rect::Rectangle)
poly2 = Polygon(rect)
for a in [axes(poly1), axes(poly2)]
isnothing(a) && continue
for axis in a
if projectionoverlaps(projectiononaxis(poly1, axis), projectiononaxis(poly2, axis))
return true
end
end
end
return false
end
let
poly = [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
rect1 = Rectangle((4.0, 0.0, 2.0, 2.0))
rect2 = Rectangle((1.0, 0.0, 8.0, 2.0))
println("poly = a polygon with vertices: ", poly)
println("rect1 = Rectangle with ", rect1)
println("rect2 = Rectangle with ", rect2)
println("\npoly and rect1 overlap? ", polygonoverlapsrect(poly, rect1))
println("poly and rect2 overlap? ", polygonoverlapsrect(poly, rect2))
end
</syntaxhighlight>{{out}}
<pre>
poly = a polygon with vertices: [(0.0, 0.0), (0.0, 2.0), (1.0, 4.0), (2.0, 2.0), (2.0, 0.0)]
rect1 = Rectangle with (x = 4.0, y = 0.0, w = 2.0, h = 2.0)
rect2 = Rectangle with (x = 1.0, y = 0.0, w = 8.0, h = 2.0)
poly and rect1 overlap? true
poly and rect2 overlap? false
</pre>
</pre>
| |||