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

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[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

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=[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
```

(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.