Circle-Rectangle collision detection (intersection)

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!

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.

If you are interested in a more graphical solution which even works on (in plane) rotated rectangles..

Demo: https://jsfiddle.net/exodus4d/94mxLvqh/2691/

The idea is:

1. Translate the scenary to the origin [0,0]
   • In case the rect is not in plane, the rotation center should be at [0, 0]
2. Rotate the scenary back into plane
3. Calculate intersection

const hasIntersection = ({x: cx, y: cy, r: cr}, {x, y, width, height}) => {
  const distX = Math.abs(cx - x - width / 2);
  const distY = Math.abs(cy - y - height / 2);

  if (distX > (width / 2 + cr)) {
    return false;
  }
  if (distY > (height / 2 + cr)) {
    return false;
  }

  if (distX <= (width / 2)) {
    return true;
  }
  if (distY <= (height / 2)) {
    return true;
  }

  const Δx = distX - width / 2;
  const Δy = distY - height / 2;
  return Δx * Δx + Δy * Δy <= cr * cr;
};

const rect = new DOMRect(50, 20, 100, 50);
const circ1 = new DOMPoint(160, 80);
circ1.r = 20;

const circ2 = new DOMPoint(80, 95);
circ2.r = 20;

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

ctx.strokeRect(rect.x, rect.y, rect.width, rect.height);

ctx.beginPath();
ctx.strokeStyle = hasIntersection(circ1, rect) ? 'red' : 'green';
ctx.arc(circ1.x, circ1.y, circ1.r, 0, 2 * Math.PI);
ctx.stroke();

ctx.beginPath();
ctx.strokeStyle = hasIntersection(circ2, rect) ? 'red' : 'green';
ctx.arc(circ2.x, circ2.y, circ2.r, 0, 2 * Math.PI);
ctx.stroke();

<canvas id="canvas"></canvas>

Tip: Instead of rotating the rect (4 points). You can rotate the circle (1 point) in opposite direction.

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.

Improving a little bit the answer of e.James:

double dx = abs(circle.x - rect.x) - rect.w / 2,
       dy = abs(circle.y - rect.y) - rect.h / 2;

if (dx > circle.r || dy > circle.r) { return false; }
if (dx <= 0 || dy <= 0) { return true; }

return (dx * dx + dy * dy <= circle.r * circle.r);

This subtracts rect.w / 2 and rect.h / 2 once instead of up to three times.

worked for me (only work when angle of rectangle is 180)

function intersects(circle, rect) {
  let left = rect.x + rect.width > circle.x - circle.radius;
  let right = rect.x < circle.x + circle.radius;
  let top = rect.y < circle.y + circle.radius;
  let bottom = rect.y + rect.height > circle.y - circle.radius;
  return left && right && bottom && top;
}

def colision(rect, circle):
dx = rect.x - circle.x
dy = rect.y - circle.y
distance = (dy**2 + dx**2)**0.5
angle_to = (rect.angle + math.atan2(dx, dy)/3.1415*180.0) % 360
if((angle_to>135 and angle_to<225) or (angle_to>0 and angle_to<45) or (angle_to>315 and angle_to<360)):
    if distance <= circle.rad/2.+((rect.height/2.0)*(1.+0.5*abs(math.sin(angle_to*math.pi/180.)))):
        return True
else:
    if distance <= circle.rad/2.+((rect.width/2.0)*(1.+0.5*abs(math.cos(angle_to*math.pi/180.)))):
        return True
return False

I developed this algorithm while making this game: https://mshwf.github.io/mates/

If the circle touches the square, then the distance between the centerline of the circle and the centerline of the square should equal (diameter+side)/2. So, let's have a variable named touching that holds that distance. The problem was: which centerline should I consider: the horizontal or the vertical? Consider this frame:

Each centerline gives different distances, and only one is a correct indication to a no-collision, but using our human intuition is a start to understand how the natural algorithm works.

They are not touching, which means that the distance between the two centerlines should be greater than touching, which means that the natural algorithm picks the horizontal centerlines (the vertical centerlines says there's a collision!). By noticing multiple circles, you can tell: if the circle intersects with the vertical extension of the square, then we pick the vertical distance (between the horizontal centerlines), and if the circle intersects with the horizontal extension, we pick the horizontal distance:

Another example, circle number 4: it intersects with the horizontal extension of the square, then we consider the horizontal distance which is equal to touching.

Ok, the tough part is demystified, now we know how the algorithm will work, but how we know with which extension the circle intersects? It's easy actually: we calculate the distance between the most right x and the most left x (of both the circle and the square), and the same for the y-axis, the one with greater value is the axis with the extension that intersects with the circle (if it's greater than diameter+side then the circle is outside the two square extensions, like circle #7). The code looks like:

right = Math.max(square.x+square.side, circle.x+circle.rad);
left = Math.min(square.x, circle.x-circle.rad);

bottom = Math.max(square.y+square.side, circle.y+circle.rad);
top = Math.min(square.y, circle.y-circle.rad);

if (right - left > down - top) {
 //compare with horizontal distance
}
else {
 //compare with vertical distance
}

/*These equations assume that the reference point of the square is at its top left corner, and the reference point of the circle is at its center*/

1. do a pre-check whether a circle fully encapsulating the rectangle collides with the circle.
2. check for rectangle corners within the circle.
3. For each edge, see if there is a line intersection with the circle. Project the center point C onto the line AB to get a point D. If the length of CD is less than radius, there was a collision.

    projectionScalar=dot(AC,AB)/(mag(AC)*mag(AB));
    if(projectionScalar>=0 && projectionScalar<=1) {
        D=A+AB*projectionScalar;
        CD=D-C;
        if(mag(CD)<circle.radius){
            // there was a collision
        }
    }

There is an incredibly simple way to do this, you have to clamp a point in x and y, but inside the square, while the center of the circle is between the two square border points in one of the perpendicular axis you need to clamp those coordinates to the parallel axis, just make sure the clamped coordinates do not exeed the limits of the square. Then just get the distance between the center of the circle and the clamped coordinates and check if the distance is less than the radius of the circle.

Here is how I did it (First 4 points are the square coordinates, the rest are circle points):

bool DoesCircleImpactBox(float x, float y, float x1, float y1, float xc, float yc, float radius){
    float ClampedX=0;
    float ClampedY=0;
    
    if(xc>=x and xc<=x1){
    ClampedX=xc;
    }
    
    if(yc>=y and yc<=y1){
    ClampedY=yc;
    }
    
    radius = radius+1;
    
    if(xc<x) ClampedX=x;
    if(xc>x1) ClampedX=x1-1;
    if(yc<y) ClampedY=y;
    if(yc>y1) ClampedY=y1-1;
    
    float XDif=ClampedX-xc;
    XDif=XDif*XDif;
    float YDif=ClampedY-yc;
    YDif=YDif*YDif;
    
    if(XDif+YDif<=radius*radius) return true;
    
    return false;
}

My method:

1. Calculate closest_point from the circle on/in OBB / rectangle (Closest point will lie on an edge/corner or inside)
2. Calculate squared_distance from the closest_point to the centre of the circle (Squared distance avoids a square root)
3. Return squared_distance <= circle radius squared

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