# Intersection of two rotated rectangles?

Is there a julia implemented version of deciding whether two rects intersect?
rects are rotated about their top left corner, specified as `[x, y, width, height, angle]`

so for example:

``````> collision([0,0,100,100,0], [40,40,10,10,45])
true
``````
1 Like

I don’t know of anything for intersection of rects, but there’s line-line intersection in `GeometryBasics` and point-in-polygon in `PolygonOps`, which should be enough:

``````using GeometryBasics, PolygonOps, Rotations, CoordinateTransformations, IterTools

function vertices(r)
x1, y1 = r, r
x2, y2 = x1 + r, y1 + r
[T(Point2(x,y)) for (x,y) in zip((x1, x1, x2, x2, x1), (y1, y2, y2, y1, y1))]
end
lines(v) = [Line(v1,v2) for (v1,v2) in IterTools.partition(v,2,1)]

function collision(rect1, rect2)
v1, v2 = vertices(rect1), vertices(rect2)
l1, l2 = lines(v1), lines(v2)
any(inpolygon(p,v2) != 0 for p in v1) ||
any(inpolygon(p,v1) != 0 for p in v2) ||
any(intersects(l1, l2) for l1 in l1, l2 in l2)
end
``````

This assumes a that “top left corner” means (x,y) (“image coordinates”, with y axis pointing down), so you may need to adapt that and/or the sign of the angle to your coordinate system.

3 Likes

Probably quicker to rotate the second rectangle’s corners into the axes of the first. That way you only need `sincos` of the difference of the angles.

1 Like

I couldn’t quite understand the solution with the `recenter(RotMatrix(...))` (i’m guessing that’s supposed to calculate the corners of each rectangle), so I sort of rolled my own by breaking the problem down into pieces. I’m leaving it here in case anyone else struggles to understand how the rotation matrix is working…
It’s the same approach though - check all 8 corners and 16 edge combinations.

It ended up taking a bit more code than expected so here it is:

``````import GeometryBasics

line(a::GeometryBasics.Point2,b::GeometryBasics.Point2) = GeometryBasics.Line(a,b)
line(a::AbstractVector, b::AbstractVector) = line(point(a...), point(b...))
line(a::Tuple{Number, Number}, b::Tuple{Number, Number}) = line(point(a...), point(b...))
point(x::Number, y::Number) = GeometryBasics.Point2(float(x), float(y))

lines(v) = [line((x1,y1),(x2,y2)) for (x1,y1,x2,y2) in IterTools.partition(v',4,2)]

function collision(corners1::Matrix, corners2::Matrix)
if corners1 == corners2
return true
end
if any(mapslices(
parallelogram_contains(corners1),
corners2;
dims=
)) || any(mapslices(
parallelogram_contains(corners2),
corners1;
dims=
))
return true
end
lines1, lines2 = lines(corners1), lines(corners2)
return any(GeometryBasics.intersects(l1, l2) for l1 in lines1 for l2 in lines2)
end

collision(rect1::Vector, rect2::Vector) =
collision(corners(rect1), corners(rect2))

"""
taken from here: https://math.stackexchange.com/questions/1805724/detect-if-point-is-within-rotated-rectangles-bounds
"""
function parallelogram_contains(corners1::Matrix)
o = corners1[1,:]
w = corners1[2,:]
h = corners1[4,:]

u = w - o
v = h - o
# some kind of determinant
L = u * v - u * v
if L < 0
L = -L
u = -u
v = -v
else
u = -u
v = -v
end

function inside((x,y))
test1 = (x - o)*v + (y - o)*v
if ! (0 < test1 < L)
return false
end
test2 = (x - o)*u + (y - o)*u
return (0 < test2 < L)
end
end

function corners(x, y, w, h, a)
[
x y;
x + w*cosd(-a) y + w*sind(-a);
x + w*cosd(-a) - h*sind(-a) y + w*sind(-a) + h*cosd(-a);
x - h*sind(-a) y + h*cosd(-a)
]
end

``````

(You’re allocating lots of little matrices and vectors here, so your code is going to be fairly slow.)

Intersection of any two polygons is implemented in Meshes.jl, and I highly recommend getting used to their types instead:

``````using Meshes

rect1 = Quadrangle((0.0,0.0), (1.0,0.0), (1.0,1.0), (0.0,1.0))
rect2 = Quadrangle((0.5,0.5), (1.5,0.5), (1.5,1.5), (0.5,1.0))

hasintersect(rect1, rect2)
``````

We implemented the beautiful GJK algorithm:

This means that you can identify intersections between polygons, balls, or any geometry with well-defined support functions.

The case with rectangles could probably be optimized, and that is why we are always happy to review PRs from the community.

For anyone reading this thread in the future: most features of the packages used in the marked solution have been reimplemented in Meshes.jl. I do not recommend using these low-level packages unless you already have a large codebase built with them. You will end up reinventing the wheel all the time. Meshes.jl provides everything out of the box with cleaner (and sometimes faster) code.

4 Likes

Oh good, I was hoping there was a package for this.
There’s no way to mark two solutions, is there? Let me make this the solution.