views:

10799

answers:

8

How can I tell whether a circle and a rectangle intersect in 2D Euclidean space? (i.e. classic 2D geometry)

A: 

Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle, if its less then the radius, then the shapes are intersecting.

if sqrt( (rectangleRight.x - circleCenter.x)^2 + (rectangleBottom.y - circleCenter.y)^2) < radius then they intersect

if sqrt( (rectangleRight.x - circleCenter.x)^2 + (rectangleTop.y - circleCenter.y)^2) < radius then they intersect

if sqrt( (rectangleLeft.x - circleCenter.x)^2 + (rectangleTop.y - circleCenter.y)^2) < radius then they intersect

if sqrt( (rectangleLeft.x - circleCenter.x)^2 + (rectangleBottom.y - circleCenter.y)^2) < radius then they intersect

ForYourOwnGood
What about the case where a small circle is entirely enclosed by a large rectangle? Surely that's an intersection, and would fail the test in this answer.
Ken Paul
Ah yes, I didn't think of that. You could just add more checks like if sqrt( (rectangleRight.x/2 - circleCenter.x)^2 + (rectangleBottom.y/2 - circleCenter.y)^2) < radius then they intersectThis will be long and slow, but off the top of my head thats the best I can come up with.
ForYourOwnGood
They can intersect on any [single one] point on any of the edges. You should find the edge-center distances as well. (Oh, and call your corners "corners" :)
aib
A: 

To visualise, take your keyboard's numpad. If the key '5' represents your rectangle, then all the keys 1-9 represent the 9 quadrants of space divided by the lines that make up your rectangle (with 5 being the inside.)

1) If the circle's center is in quadrant 5 (i.e. inside the rectangle) then the two shapes intersect.

With that out of the way, there are two possible cases: a) The circle intersects with two or more neighboring edges of the rectangle. b) The circle intersects with one edge of the rectangle.

The first case is simple. If the circle intersects with two neighboring edges of the rectangle, it must contain the corner connecting those two edges. (That, or its center lies in quadrant 5, which we have already covered. Also note that the case where the circle intersects with only two opposing edges of the rectangle is covered as well.)

2) If any of the corners A, B, C, D of the rectangle lie inside the circle, then the two shapes intersect.

The second case is trickier. We should make note of that it may only happen when the circle's center lies in one of the quadrants 2, 4, 6 or 8. (In fact, if the center is on any of the quadrants 1, 3, 7, 8, the corresponding corner will be the closest point to it.)

Now we have the case that the circle's center is in one of the 'edge' quadrants, and it only intersects with the corresponding edge. Then, the point on the edge that is closest to the circle's center, must lie inside the circle.

3) For each line AB, BC, CD, DA, construct perpendicular lines p(AB,P), p(BC,P), p(CD,P), p(DA,P) through the circle's center P. For each perpendicular line, if the intersection with the original edge lies inside the circle, then the two shapes intersect.

There is a shortcut for this last step. If the circle's center is in quadrant 8 and the edge AB is the top edge, the point of intersection will have the y-coordinate of A and B, and the x-coordinate of center P.

You can construct the four line intersections and check if they lie on their corresponding edges, or find out which quadrant P is in and check the corresponding intersection. Both should simplify to the same boolean equation. Be wary of that the step 2 above did not rule out P being in one of the 'corner' quadrants; it just looked for an intersection.

Edit: As it turns out, I have overlooked the simple fact that #2 is a subcase of #3 above. After all, corners too are points on the edges. See @ShreevatsaR's answer below for a great explanation. And in the meanwhile, forget #2 above unless you want a quick but redundant check.

aib
+17  A: 

Here is how I would do it:

bool intersects(CircleType circle, RectType rect)
{
    circleDistance.x = abs(circle.x - rect.x - rect.width/2);
    circleDistance.y = abs(circle.y - rect.y - rect.height/2);

    if (circleDistance.x > (rect.width/2 + circle.r)) { return false; }
    if (circleDistance.y > (rect.height/2 + circle.r)) { return false; }

    if (circleDistance.x <= (rect.width/2)) { return true; } 
    if (circleDistance.y <= (rect.height/2)) { return true; }

    cornerDistance_sq = (circleDistance.x - rect.width/2)^2 +
                         (circleDistance.y - rect.height/2)^2;

    return (cornerDistance_sq <= (circle.r^2));
}

Here's how it works:

alt text

  1. The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle. This collapses the four quadrants down into one, so that the calculations do not have to be done four times. The image shows the area in which the center of the circle must now lie. Note that only the single quadrant is shown. The rectangle is the grey area, and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle. The center of the circle has to be within this red border for the intersection to occur.

  2. The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle (in either direction) that no intersection is possible. This corresponds to the green area in the image.

  3. The third pair of lines eliminates the easy cases where the circle is close enough to the rectangle (in either direction) that an intersection is guaranteed. This corresponds to the orange sections in the image, as well as the grey interior of the rectangle itself. Note that this step must be done after step 2 for the logic to make sense.

  4. The final three lines calculate the difficult case where the circle may intersect the corner of the rectangle. To solve, I compute the distance from the center of the circle and the corner, and then verify that the distance is not more than the radius of the circle. This calculation eliminates all circles whose center is within the red shaded area in the image.

e.James
+1. Nice idea, great explanation! How did you draw the figure, BTW?
ShreevatsaR
Thank you, ShreevatsaR. I drew it with Photoshop because that was the only tool I had available on short notice :)
e.James
Very nice! Notes: apparently here, rect.x/y is at the upper right corner of the rectangle.Also you can eliminate the expensive square root, by instead comparing against the square of the radius.
luqui
Oh no, my bad. rect.x/y is at the lower left of the rectangle. I would have written:circleDistance.x = abs(circle.x - (rect.x + rect.width/2));
luqui
Great point about the square root. I made the change.
e.James
+6  A: 

Your insight is good, but it can be simplified. There are only two cases when the circle intersects with the rectangle:

  • Either the circle's centre lies inside the rectangle, or
  • One of the edges of the rectangle intersects the circle.

Note that this does not require the rectangle to be axis-parallel. With that insight, something like the following will work, where the circle has centre P and radius R, and the rectangle has vertices A, B, C, D in that order (not complete code):

def intersect(circle(P, R), rectangle(A, B, C, D)):
    S = circle(P,R)
    return pointInRectangle(P, rectangle(A,B,C,D) or
           intersectCircle(S, (A,B)) or
           intersectCircle(S, (B,C)) or
           intersectCircle(S, (C,D)) or
           intersectCircle(S, (D,A))

If you're writing any geometry you probably have the above functions in your library already. Otherwise, pointInRectangle can be implemented in several ways; any of the general point in polygon methods will work, but for a rectangle you can just check whether

0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD

for example. And intersectCircle is easy to implement too: one way would be to check if the foot of the perpendicular from P to the line is close enough and between the endpoints, and check the endpoints otherwise.

The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon -- doesn't even have to be convex!

ShreevatsaR
Hmm, true. I started out with the simple (corner in circle) check and moved on to other cases from there. I did not see the simplification resulting from the fact that corners ARE points on the edges.
aib
+1  A: 
Not sure why this was downvoted. The logic is sound. +1
e.James
+4  A: 

Here is another solution that's pretty simple to implement (and pretty fast, too). It will catch all intersections, including when the sphere has fully entered the rectangle.

// clamp(value, min, max) - limits value to the range min..max

// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Left, rectangle.Right);

// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;

// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);

With any decent math library, that can be shortened to 3 or 4 lines.

Cygon
You have a bug in there, you search for closestY with Left and Right, not Top and Bottom, otherwise lovely solution.
manveru
Ah, darn, that happens when you fix up code on-the-fly in Firefox :)Good find!
Cygon
+1  A: 

Here's my C code for resolving a collision between a sphere and a non-axis aligned box. It relies on a couple of my own library routines, but it may prove useful to some. I'm using it in a game and it works perfectly.

float physicsProcessCollisionBetweenSelfAndActorRect(SPhysics *self, SPhysics *actor)
{
    float diff = 99999;

    SVector relative_position_of_circle = getDifference2DBetweenVectors(&self->worldPosition, &actor->worldPosition);
    rotateVector2DBy(&relative_position_of_circle, -actor->axis.angleZ); // This aligns the coord system so the rect becomes an AABB

    float x_clamped_within_rectangle = relative_position_of_circle.x;
    float y_clamped_within_rectangle = relative_position_of_circle.y;
    LIMIT(x_clamped_within_rectangle, actor->physicsRect.l, actor->physicsRect.r);
    LIMIT(y_clamped_within_rectangle, actor->physicsRect.b, actor->physicsRect.t);

    // Calculate the distance between the circle's center and this closest point
    float distance_to_nearest_edge_x = relative_position_of_circle.x - x_clamped_within_rectangle;
    float distance_to_nearest_edge_y = relative_position_of_circle.y - y_clamped_within_rectangle;

    // If the distance is less than the circle's radius, an intersection occurs
    float distance_sq_x = SQUARE(distance_to_nearest_edge_x);
    float distance_sq_y = SQUARE(distance_to_nearest_edge_y);
    float radius_sq = SQUARE(self->physicsRadius);
    if(distance_sq_x + distance_sq_y < radius_sq)   
    {
        float half_rect_w = (actor->physicsRect.r - actor->physicsRect.l) * 0.5f;
        float half_rect_h = (actor->physicsRect.t - actor->physicsRect.b) * 0.5f;

        CREATE_VECTOR(push_vector);         

        // If we're at one of the corners of this object, treat this as a circular/circular collision
        if(fabs(relative_position_of_circle.x) > half_rect_w && fabs(relative_position_of_circle.y) > half_rect_h)
        {
            SVector edges;
            if(relative_position_of_circle.x > 0) edges.x = half_rect_w; else edges.x = -half_rect_w;
            if(relative_position_of_circle.y > 0) edges.y = half_rect_h; else edges.y = -half_rect_h;   

            push_vector = relative_position_of_circle;
            moveVectorByInverseVector2D(&push_vector, &edges);

            // We now have the vector from the corner of the rect to the point.
            float delta_length = getVector2DMagnitude(&push_vector);
            float diff = self->physicsRadius - delta_length; // Find out how far away we are from our ideal distance

            // Normalise the vector
            push_vector.x /= delta_length;
            push_vector.y /= delta_length;
            scaleVector2DBy(&push_vector, diff); // Now multiply it by the difference
            push_vector.z = 0;
        }
        else // Nope - just bouncing against one of the edges
        {
            if(relative_position_of_circle.x > 0) // Ball is to the right
                push_vector.x = (half_rect_w + self->physicsRadius) - relative_position_of_circle.x;
            else
                push_vector.x = -((half_rect_w + self->physicsRadius) + relative_position_of_circle.x);

            if(relative_position_of_circle.y > 0) // Ball is above
                push_vector.y = (half_rect_h + self->physicsRadius) - relative_position_of_circle.y;
            else
                push_vector.y = -((half_rect_h + self->physicsRadius) + relative_position_of_circle.y);

            if(fabs(push_vector.x) < fabs(push_vector.y))
                push_vector.y = 0;
            else
                push_vector.x = 0;
        }

        diff = 0; // Cheat, since we don't do anything with the value anyway
        rotateVector2DBy(&push_vector, actor->axis.angleZ);
        SVector *from = &self->worldPosition;       
        moveVectorBy2D(from, push_vector.x, push_vector.y);
    }   
    return diff;
}
Madrayken
ooh, object-oriented C code :)
aib
A: 

Here is the modfied code 100% working:

public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle) {

        var rectangleCenter = new PointF((rectangle.X +  rectangle.Width / 2),
                                         (rectangle.Y + rectangle.Height / 2));

        var w = rectangle.Width  / 2;
        var h = rectangle.Height / 2;

        var dx = Math.Abs(circle.X - rectangleCenter.X);
        var dy = Math.Abs(circle.Y - rectangleCenter.Y);

        if (dx > (radius + w) || dy > (radius + h)) return false;


        var circleDistance = new PointF
                                 {
                                     X = Math.Abs(circle.X - rectangle.X - w),
                                     Y = Math.Abs(circle.Y - rectangle.Y - h)
                                 };


        if (circleDistance.X <= (w))
        {
            return true;
        }

        if (circleDistance.Y <= (h))
        {
            return true;
        }

        var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) + 
                    Math.Pow(circleDistance.Y - h, 2);

        return (cornerDistanceSq <= (Math.Pow(radius, 2)));
    }

Bassam Alugili

Bassam Alugili