Collision Detection: Circle to Rectangle

[Serethos]

I need a fine collision detection method for a circle against a rectangle.
i read the tutorial from HarveyCartel http://www.harveycartel.org/metanet/tutorials/tutorialA.html

But i dont understand it, especially the point how to know which corner of the rectangle to take
for testing. some explanation or another method would make me happy ...

[anarchotron]

Are your rectangles axis-aligned?

If so, just check the distance of the circle from the center of the rect.

CC = circle center
CR = circle radius

RC = rect center
RH = rect height
RW = rect width

if abs(CC.x - RC.x) <= (RW/2 + CR)  then collision
if abs(CC.y - RC.y) <= (RH/2 + CR) then collision

If the rect is not axis aligned, you can transform the circle's center into a space centered and aligned with the rectangle, and then do the above.

[Alan_W]

  Are you sure about that.  Draw a square.  Now draw a circle just not touching the bottom left corner of the square at the 45 degree angle from the top.   See what I mean.  What you've got there is a rectangle against square collision detector.

Alan

Edit:  Here's an idea.  I'm going to describe it graphically, rather than programmatically.  I am assuming the rectangle is aligned with the x & y axes.  If not, then a rotation is required first.

1) Draw two lines parallel with the x and y axes, through the centre of the circle, splitting it into four quadrants.  The lines extend beyond the circle.
2) Determine which quadrant each corner of the rectangle lies in.
3) i) If 3 or 4 quadrants have at least one corner, then there is a collision
3 ii) If 2 quadrants have at least one corner then check if the square bounding box of the circle intersects the rectangle.  If so then there is a collision
3 iii) If all rectangle points fall in the same quadrant, then calculate the square of the distance of each rectangle corner from the centre of the circle.  If any of these are less than the square of the circle radius then there is a collision.

It's just an idea,  may be a better way;)

Games published by our own members! Check 'em out!

[anarchotron]

Doh!  You're right.

Hehehe

[Jeff]

Hmm./ just off the top of my head, thre may be a better way...

Aumming axis alingment...

(1) Do pt v. circle for all 4 corners of the rect.  Thats cehap and will get you everything but the case where the circle is wholly
enclosed in the rect.

(2) Do circle center v. rectangle tofind that one case.

As I loo kat this, It *might* be slightly  faster to reverse the tests above, but im not sure it matters much.

There is also probably a heuristic possible here doing distance of center to center to eliminate most cases. Again not sure if the distance calc is woth it.  (Might be if you did it in distance-squared space to avoid the sqrt...)

[tom]

Hmm./ just off the top of my head, thre may be a better way...

Aumming axis alingment...

(1) Do pt v. circle for all 4 corners of the rect.  Thats cehap and will get you everything but the case where the circle is wholly
enclosed in the rect.

(2) Do circle center v. rectangle tofind that one case.

As I loo kat this, It *might* be slightly  faster to reverse the tests above, but im not sure it matters much.

There is also probably a heuristic possible here doing distance of center to center to eliminate most cases. Again not sure if the distance calc is woth it.  (Might be if you did it in distance-squared space to avoid the sqrt...)

It's not enough to only check the points of the rectangle against the circle. The circle can still intersects one of the sides of the rectangle. A slow and easy way would be to check if any of the four linesegments intersects the sircle.

[oNyx]

java.awt.geom.Ellipse2D has a good/fast intersects method.

[Alan_W]

It's not enough to only check the points of the rectangle against the circle. The circle can still intersects one of the sides of the rectangle. A slow and easy way would be to check if any of the four linesegments intersects the sircle.

I did line segment against circle for something at work.  It works fine, but requires solving a quadratic for the general case (arbitrary line).  You need to solve in x or solve in y according to the line gradient to avoid divide by zero. There's also some additional testing (using dot products) to see if any potential intersection occurs beyond the endpoints of the line.  Hopefully this would simplify a bit for lines which are only vertical or horizontal.

For the case of rectangle against circle, there is also the case where the rectangle completely surrounds the circle (or vice versa), although it may not be necessary to test for this, depending on the application.

Alan 

Edit.  After a bit more thought, I think that the method I outlined earlier will be a fair bit quicker then doing 4 line to circle checks:

Something like this untested code.  (Only the two diagonally opposite corners of the rectangle are stored)

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50

private boolean[][] quadrant = new boolean[2][2]; public boolean collision(Rectangle rectangle, Circle circle) {   // Clear quadrant flags   for (int x=0; x++; x<2)     for(int y=0; y++; y<2)       quadrant[x][y] = false;   // Determine quadrant of each corner   for (int x=0; x++; x<2)  {     int quadX = ?(rectangle.x[x]>=circle.x)0:1;     for(int y=0; y++; y<2) {       int quadY = ?(rectangle.y[y]>=circle.y)0:1;       quadrant[quadX][quadY] = true;     }   }   // Count the number of quadrants with at least one corner   int quadrants = 0;   for (int x=0; x++; x<2)     for(int y=0; y++; y<2)       if (quadrant[x][y])         quadrants++;   // Detect Collisions   boolean collision = false;   switch (quadrants) {     case 1: // Check each rectangle corner against circle radius       float radiusSquared = circle.radius*circle.radius;       for (int x=0; x++; x<2) {         float dx = rectangle.x[x] - circle.x;         for(int y=0; y++; y<2) {           float dy = rectangle.y[y] - circle.y;           if (dx*dx+dy*dy <= radiusSquared)             collision = true;         }       }          break;     case 2: // Check for intersection between rectangle and bounding box of the circle       boolean intersectX = !(rectangle.x[1] < circle.x-circle.radius || rectangle.x[0] > circle.x+circle.radius);       boolean intersectY = !(rectangle.y[1] < circle.x-circle.radius || rectangle.y[0] > circle.x+circle.radius);       if (intersectX && intersectY)         collision = true;       break;     default: // Anything else is a collision       collision = true;   }   return collision; }

   
/Edit - Corrected an error in the rectangle arrays

[Jeff]

I should mention that, when Im faced with any geometric problem like this in my code,I generally reach for my set of Graphics Gems volumes.

Books no serious graphics programmer should be without.

[Serethos]

I would love to buy the whole XXX Gems series, but i never know, which one to take (no. 1-798)
and they're quite expensive. i have here two game programming books - with a serious lack on
collision detection - and a java reference. these books alone shot a hole in my pocket.
but can you suggest one special book of the series? amazon shows at least three of them ..

Games published by our own members! Check 'em out!

[Orangy Tang]

Eberly's "3d game engine design" is very good for collision detection routines. Covers practically all intersection cases with both equations and code. Very maths heavy though, and lots of formal maths notation.

[Jeff]

I would love to buy the whole XXX Gems series, but i never know, which one to take (no. 1-798)
and they're quite expensive. i have here two game programming books - with a serious lack on
collision detection - and a java reference. these books alone shot a hole in my pocket.
but can you suggest one special book of the series? amazon shows at least three of them ..

Graphics Gems is where it all started.  For fundemental fast geometric tricks Id say the first 3 or so volumes are what i find msyelf referring back to a lot when writing geometric code.  You at lesat used to be able to buy most of the set on a single CD.  I dont find that as useful as I really like paper for my refernces, but I think it was significantly cheaper then buying all the books.