# Intersection of two rotated rectangles?

**URL:** <https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312>\
**Category:** Visualization\
**Tags:** geometry\
**Created:** [April 10, 2022, 6:25pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312 "2022-04-10T18:25:44Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![vshesh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vshesh/32/20362_2.png) [@vshesh](https://discourse.julialang.org/u/vshesh)\
**Post date:** [April 10, 2022, 6:25pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/1 "2022-04-10T18:25:44Z")

</div>

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:

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

```

---

<div class="post-metadata">

**Author:** ![yha](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yha/32/3502_2.png) [@yha](https://discourse.julialang.org/u/yha)\
**Post date:** [April 10, 2022, 9:52pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/2 "2022-04-10T21:52:17Z")

</div>

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:

```julia
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.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 11, 2022, 1:15pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/4 "2022-04-11T13:15:34Z")

</div>

> [@rafael.guerra](#):
>
> `sθ1, cθ1, sθ2, cθ2 = sincosd(θ1)..., sincosd(θ2)...`

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.

---

<div class="post-metadata">

**Author:** ![vshesh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vshesh/32/20362_2.png) [@vshesh](https://discourse.julialang.org/u/vshesh)\
**Post date:** [April 11, 2022, 9:14pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/5 "2022-04-11T21:14:40Z")

</div>

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:

```julia
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

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [April 11, 2022, 10:08pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/6 "2022-04-11T22:08:26Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [April 11, 2022, 10:41pm UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/7 "2022-04-11T22:41:11Z")

</div>

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

```julia
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:

[![](https://global.discourse-cdn.com/julialang/original/3X/0/1/01eac2bd1839be1c727c297ec48f47efd2df3412.jpeg "A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)") ](https://www.youtube.com/watch?v=ajv46BSqcK4)

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.

---

<div class="post-metadata">

**Author:** ![vshesh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vshesh/32/20362_2.png) [@vshesh](https://discourse.julialang.org/u/vshesh)\
**Post date:** [April 12, 2022, 12:20am UTC](https://discourse.julialang.org/t/intersection-of-two-rotated-rectangles/79312/8 "2022-04-12T00:20:26Z")

</div>

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.