Intersection of two rotated rectangles?

Specific Domains Visualization
1

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
2

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[1], r[2]
    x2, y2 = x1 + r[3], y1 + r[4]
    T = recenter(RotMatrix(deg2rad(r[5])), (x1,y1))
    [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)[1] 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
4

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
5

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=[2]
	)) || any(mapslices(
		parallelogram_contains(corners2),
		corners1;
		dims=[2]
	))
		return true
	end
	lines1, lines2 = lines(corners1), lines(corners2)
	return any(GeometryBasics.intersects(l1, l2)[1] 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[1] * v[2] - u[2] * v[1]
	if L < 0
		L = -L 
		u[1] = -u[1]
		v[2] = -v[2]
	else
		u[2] = -u[2]
		v[1] = -v[1]
	end 

	function inside((x,y))
		test1 = (x - o[1])*v[2] + (y - o[2])*v[1]
		if ! (0 < test1 < L)
		    return false
		end
		test2 = (x - o[1])*u[2] + (y - o[2])*u[1]
		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
6

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

7

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
8

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.