Check if a polygon overlaps with a rectangle: Difference between revisions
Content added Content deleted
m (→{{header|ALGOL 68}}: notes) |
(julia example) |
||
Line 467: | Line 467: | ||
poly1 and r1 overlap? false |
poly1 and r1 overlap? false |
||
poly1 and r2 overlap? true |
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> |
</pre> |
||