Rectangle circle intersection

Discussion
1

I looked at different algorithms for finding the intersection and they all looked quite hairy for me, with the need to handle special cases when one shape is completely inside another.

So I had this idea that a rectangle can be thought of as an intersection of four circles with large radii, then the rectangle-circle intersection can be converted into detecting circle-circle intersections, which is pretty fast considering you can compare squared distances.

What do you guys think?

image

interactive fiddle demo (use arrow keys to move the rectangle and ‘q’ and ‘w’ to rotate)

This could be expanded to the intersection of prisms and spheres.

2 Likes
2

this wont quite be precise

3

The radii are small for demonstration purposes, increase them x10 and it will be, almost down to a pixel.

4

I think it’s a neat idea, approximating lines as segments of circles. However, it will not work where accuracy is important.

If you find this problem hard to wrap your head around - consider simplifying it down to line-circle intersection. That is relatively simpler.

Obviously since line has no volume, you’d need to test if the circle is entirely inside rectangle as well, but that’s trivial.

5

Yes, also if the rectangle is entirely inside the circle, so overall number of computations seems to be larger that checking one circle against 4 that make the rectangle.

If will not work well for math applications, but for video games where you visually confirm collision, give or take one pixel of ,say, a fireball with some rectange-ish object, it might be a faster and simpler option.

I wrote this for a game, so I’ll definitely check how it works in reality :wink:

6

Can’t that just be done by testing if the center is in the rect? More involved is if rect is entirely inside of circle?

7

Can’t that just be done by testing if the center is in the rect?

Yes, that would work. It’s a test that’s a bit more board, but it will definitely catch the case of circle being fully inside the rect, and it’s just 4 comparison operations, 2 per dimension.

8

The rectangle can be rotated, so its horizontal/vertical dimensions will have to be calculated.

9

The rectangle can be rotated […]

Ah, yes, that makes it a bit harder. I would suggest transforming the coordinate space back to axis-aligned rectangle. But I guess everyone has their own preferences.

1 Like
10

I’m quite interested in making easy collision detection of rotated boxes in 3D. I don’t need mathematical precision, just visual precision.

I like the idea of approximating rectangle sides with circles. However, the implementation might be lacking something. I made the radii 10 times larger:

this.R = [30 * ratio, 30, 30 * ratio, 30];

and the circles became larger, but intersection accuracy did not improve. The first snapshot shows that the rectangle and the big circle are evaluated as intersecting, but they are not. Even 100 times larger does not improve the result (second snapshot).

10x image 100ximage

It appears that when the big circle crosses two of the rectangle’s circles, this is considered as intersection.

11

Thanks, I’ll have a look, maybe some condition is missing

1 Like