Circle-Rectangle collision detection (intersection)

Question

Here is how I would do it:

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

    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:

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 handle 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 and grey sections in the image. Note that this step must be done after step 2 for the logic to make sense.

4. The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle. To solve, 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 returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area.

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 has a point in the circle.

Note that this does not require the rectangle to be axis-parallel.

(One way to see this: if none of the edges has a point in the circle (if all the edges are completely "outside" the circle), then the only way the circle can still intersect the polygon is if it lies completely inside the polygon.)

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 this works:

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

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!

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.Top, rectangle.Bottom);

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

your sphere and rect intersect IIF
the distance between the circle-center and one vertex of your rect is smaller than the radius of your sphere
OR
the distance between the circle-center and one edge of your rect is smaller than the radius of your sphere ([point-line distance ])
OR
the circle center is inside the rect

point-point distance:

P1 = [x1,y1]
P2 = [x2,y2]
Distance = sqrt(abs(x1 - x2)+abs(y1-y2))

point-line distance:

L1 = [x1,y1],L2 = [x2,y2] (two points of your line, ie the vertex points)
P1 = [px,py] some point

Distance d =  abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)

circle center inside rect:
take an seperating axis aproach: if there exists a projection onto a line that seperates the rectangle from the point, they do not intersect

you project the point on lines parallel to the sides of your rect and can then easily determine if they intersect. if they intersect not on all 4 projections, they (the point and the rectangle) can not intersect.

you just need the inner-product ( x= [x1,x2] , y = [y1,y2] , x*y = x1*y1 + x2*y2 )

your test would look like that:

//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right)
//point to test: POI

seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // the edges
    D = edge[0] - edge[1]
    innerProd =  D * POI
    Interval_min = min(D*edge[0],D*edge[1])
    Interval_max = max(D*edge[0],D*edge[1])
    if not (  Interval_min ≤ innerProd ≤  Interval_max ) 
           seperated = true
           break  // end for loop 
    end if
end for
if (seperated is true)    
      return "no intersection"
else 
      return "intersection"
end if

this does not assume an axis-aligned rectangle and is easily extendable for testing intersections between convex sets.