Detección de colisión círculo-rectángulo (intersección)

¿Cómo puedo saber si un círculo y un rectángulo se cruzan en el espacio euclidiano 2D? (es decir, geometría 2D clásica)

Solo hay dos casos cuando el círculo se cruza con el rectángulo:

• O el centro del círculo se encuentra dentro del rectángulo, o
• Uno de los bordes del rectángulo tiene un punto en el círculo.

Tenga en cuenta que esto no requiere que el rectángulo sea paralelo al eje.

(Una forma de ver esto: si ninguno de los bordes tiene un punto en el círculo (si todos los bordes están completamente "fuera" del círculo), entonces la única forma en que el círculo todavía puede intersecar el polígono es si se encuentra completamente dentro del polígono.)

Con ese conocimiento, algo así como el siguiente trabajo, en el que el círculo tiene centro Py el radio R, y el rectángulo tiene vértices A, B, C, Den ese orden (código no completa):

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)))

Si está escribiendo alguna geometría, probablemente ya tenga las funciones anteriores en su biblioteca. De lo contrario, pointInRectangle()se puede implementar de varias maneras; cualquiera de los puntos generales en los métodos de polígono funcionará, pero para un rectángulo puede verificar si esto funciona:

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

Y también intersectCircle()es fácil de implementar: una forma sería verificar si el pie de la perpendicular desde Pla línea está lo suficientemente cerca y entre los puntos finales, y verificar los puntos finales de lo contrario.

Lo bueno es que la misma idea funciona no solo para los rectángulos, sino también para la intersección de un círculo con cualquier polígono simple : ¡ni siquiera tiene que ser convexo!

Así es como lo haría:

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));
}

Así es como funciona:

1. El primer par de líneas calcula los valores absolutos de la diferencia xey entre el centro del círculo y el centro del rectángulo. Esto colapsa los cuatro cuadrantes en uno, de modo que los cálculos no tienen que hacerse cuatro veces. La imagen muestra el área en la que ahora debe estar el centro del círculo. Tenga en cuenta que solo se muestra el cuadrante único. El rectángulo es el área gris, y el borde rojo delinea el área crítica que está exactamente a un radio de los bordes del rectángulo. El centro del círculo debe estar dentro de este borde rojo para que ocurra la intersección.

2. El segundo par de líneas elimina los casos fáciles donde el círculo está lo suficientemente lejos del rectángulo (en cualquier dirección) que no es posible ninguna intersección. Esto corresponde al área verde de la imagen.

3. El tercer par de líneas maneja los casos fáciles donde el círculo está lo suficientemente cerca del rectángulo (en cualquier dirección) que garantiza una intersección. Esto corresponde a las secciones naranja y gris de la imagen. Tenga en cuenta que este paso debe realizarse después del paso 2 para que la lógica tenga sentido.

4. Las líneas restantes calculan el caso difícil en el que el círculo puede intersecar la esquina del rectángulo. Para resolver, calcule la distancia desde el centro del círculo y la esquina, y luego verifique que la distancia no sea mayor que el radio del círculo. Este cálculo devuelve falso para todos los círculos cuyo centro está dentro del área sombreada roja y devuelve verdadero para todos los círculos cuyo centro está dentro del área sombreada blanca.

Aquí hay otra solución que es bastante simple de implementar (y también bastante rápida). Capturará todas las intersecciones, incluso cuando la esfera haya entrado completamente en el rectángulo.

// 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);

Con cualquier biblioteca matemática decente, eso se puede acortar a 3 o 4 líneas.

su esfera y rect se cruzan IIF
la distancia entre el centro del círculo y un vértice de su rect es menor que el radio de su esfera
O
la distancia entre el centro del círculo y un borde de su rect es menor que el radio de su esfera ( [ distancia punto-línea ])
O
el centro del círculo está dentro de la

distancia rect -punto-punto:

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

distancia punto-línea:

L1 = [x1, y1], L2 = [x2, y2] (dos puntos de su línea, es decir, los puntos de vértice)
P1 = [px, py] algún punto

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

centro del círculo dentro del rectángulo:
tome un enfoque de eje separado: si existe una proyección en una línea que separa el rectángulo del punto, no se cruzan

proyecta el punto en líneas paralelas a los lados de su rectángulo y luego puede determinar fácilmente si se cruzan. si no se cruzan en las 4 proyecciones, ellos (el punto y el rectángulo) no pueden cruzarse.

solo necesita el producto interno (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)

su prueba se vería así:

// bordes rectangulares: TL (arriba a la izquierda), TR (arriba a la derecha), BL (abajo a la izquierda), BR (abajo a la derecha)
// punto a probar: POI

separado = falso
para egde en {{TL, TR}, {BL, BR}, {TL, BL}, {TR-BR}}: // los bordes
    D = borde [0] - borde [1]
    innerProd = D * POI
    Interval_min = min (D * edge [0], D * edge [1])
    Interval_max = max (D * edge [0], D * edge [1])
    si no (Interval_min ≤ innerProd ≤ Interval_max) 
           separado = verdadero
           break // final para loop 
    terminara si
fin para
si (separado es cierto)    
      devolver "sin intersección"
más 
      volver "intersección"
terminara si

esto no asume un rectángulo alineado con el eje y es fácilmente extensible para probar intersecciones entre conjuntos convexos.

Esta es la solución más rápida:

public static boolean intersect(Rectangle r, Circle c)
{
    float cx = Math.abs(c.x - r.x - r.halfWidth);
    float xDist = r.halfWidth + c.radius;
    if (cx > xDist)
        return false;
    float cy = Math.abs(c.y - r.y - r.halfHeight);
    float yDist = r.halfHeight + c.radius;
    if (cy > yDist)
        return false;
    if (cx <= r.halfWidth || cy <= r.halfHeight)
        return true;
    float xCornerDist = cx - r.halfWidth;
    float yCornerDist = cy - r.halfHeight;
    float xCornerDistSq = xCornerDist * xCornerDist;
    float yCornerDistSq = yCornerDist * yCornerDist;
    float maxCornerDistSq = c.radius * c.radius;
    return xCornerDistSq + yCornerDistSq <= maxCornerDistSq;
}

Tenga en cuenta el orden de ejecución, y la mitad del ancho / alto se calcula previamente. También la cuadratura se realiza "manualmente" para guardar algunos ciclos de reloj.

La solución más simple que se me ocurrió es bastante sencilla.

Funciona al encontrar el punto en el rectángulo más cercano al círculo y luego comparar la distancia.

Puede hacer todo esto con algunas operaciones e incluso evitar la función sqrt.

public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
   float closestX = (cx < left ? left : (cx > right ? right : cx));
   float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
   float dx = closestX - cx;
   float dy = closestY - cy;

   return ( dx * dx + dy * dy ) <= radius * radius;
}

¡Y eso es! La solución anterior supone un origen en la esquina superior izquierda del mundo con el eje x apuntando hacia abajo.

Si desea una solución para manejar las colisiones entre un círculo en movimiento y un rectángulo, es mucho más complicado y está cubierto por otra respuesta mía.

En realidad, esto es mucho más simple. Solo necesitas dos cosas.

Primero, necesitas encontrar cuatro ortogonales distancias desde el centro del círculo hasta cada línea del rectángulo. Entonces su círculo no se intersecará con el rectángulo si tres de ellos son más grandes que el radio del círculo.

En segundo lugar, debe encontrar la distancia entre el centro del círculo y el centro del rectángulo, luego el círculo no estará dentro del rectángulo si la distancia es mayor que la mitad de la longitud diagonal del rectángulo.

¡Buena suerte!

Aquí está mi código C para resolver una colisión entre una esfera y un cuadro alineado sin eje. Se basa en un par de rutinas de mi propia biblioteca, pero puede resultar útil para algunos. Lo estoy usando en un juego y funciona perfectamente.

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;
}

Para visualizar, toma el teclado numérico de tu teclado. Si la tecla '5' representa su rectángulo, entonces todas las teclas 1-9 representan los 9 cuadrantes de espacio divididos por las líneas que forman su rectángulo (con 5 como el interior).

1) Si el centro del círculo está en el cuadrante 5 (es decir, dentro del rectángulo), las dos formas se cruzan.

Con eso fuera del camino, hay dos casos posibles: a) El círculo se cruza con dos o más bordes vecinos del rectángulo. b) El círculo se cruza con un borde del rectángulo.

El primer caso es simple. Si el círculo se cruza con dos bordes vecinos del rectángulo, debe contener la esquina que conecta esos dos bordes. (Eso, o su centro se encuentra en el cuadrante 5, que ya hemos cubierto. También tenga en cuenta que el caso donde el círculo se cruza con solo dos bordes opuestos del rectángulo también está cubierto).

2) Si alguna de las esquinas A, B, C, D del rectángulo se encuentra dentro del círculo, entonces las dos formas se cruzan.

El segundo caso es más complicado. Debemos tener en cuenta que solo puede ocurrir cuando el centro del círculo se encuentra en uno de los cuadrantes 2, 4, 6 u 8. (De hecho, si el centro está en cualquiera de los cuadrantes 1, 3, 7, 8, el la esquina correspondiente será el punto más cercano a ella).

Ahora tenemos el caso de que el centro del círculo está en uno de los cuadrantes de 'borde', y solo se cruza con el borde correspondiente. Luego, el punto en el borde que está más cerca del centro del círculo debe estar dentro del círculo.

3) Para cada línea AB, BC, CD, DA, construya líneas perpendiculares p (AB, P), p (BC, P), p (CD, P), p (DA, P) a través del centro del círculo P. Para cada línea perpendicular, si la intersección con el borde original se encuentra dentro del círculo, entonces las dos formas se cruzan.

Hay un atajo para este último paso. Si el centro del círculo está en el cuadrante 8 y el borde AB es el borde superior, el punto de intersección tendrá la coordenada y de A y B, y la coordenada x del centro P.

Puede construir las cuatro intersecciones de línea y verificar si se encuentran en sus bordes correspondientes, o averiguar en qué cuadrante P está y verificar la intersección correspondiente. Ambos deberían simplificarse a la misma ecuación booleana. Tenga cuidado de que el paso 2 anterior no descarta que P esté en uno de los cuadrantes de "esquina"; solo buscaba una intersección.

Editar: Resulta que he pasado por alto el simple hecho de que el n. ° 2 es un subcampo del n. ° 3 anterior. Después de todo, las esquinas también son puntos en los bordes. Consulte la respuesta de @ ShreevatsaR a continuación para obtener una gran explicación. Y mientras tanto, olvide el # 2 anterior a menos que desee una verificación rápida pero redundante.

Esta función detecta colisiones (intersecciones) entre Círculo y Rectángulo. Trabaja como el método e.James en su respuesta, pero este detecta colisiones para todos los ángulos de rectángulo (no solo en la esquina superior derecha).

NOTA:

¡aRect.origin.x y aRect.origin.y son coordenadas del ángulo inferior izquierdo del rectángulo!

¡aCircle.x y aCircle.y son coordenadas de Circle Center!

static inline BOOL RectIntersectsCircle(CGRect aRect, Circle aCircle) {

    float testX = aCircle.x;
    float testY = aCircle.y;

    if (testX < aRect.origin.x)
        testX = aRect.origin.x;
    if (testX > (aRect.origin.x + aRect.size.width))
        testX = (aRect.origin.x + aRect.size.width);
    if (testY < aRect.origin.y)
        testY = aRect.origin.y;
    if (testY > (aRect.origin.y + aRect.size.height))
        testY = (aRect.origin.y + aRect.size.height);

    return ((aCircle.x - testX) * (aCircle.x - testX) + (aCircle.y - testY) * (aCircle.y - testY)) < aCircle.radius * aCircle.radius;
}

Tengo un método que evita las costosas pitágoras si no es necesario, es decir. al delimitar cuadros del rectángulo y el círculo no se cruzan.

Y también funcionará para los no euclidianos:

class Circle {
 // create the bounding box of the circle only once
 BBox bbox;

 public boolean intersect(BBox b) {
    // test top intersect
    if (lat > b.maxLat) {
        if (lon < b.minLon)
            return normDist(b.maxLat, b.minLon) <= normedDist;
        if (lon > b.maxLon)
            return normDist(b.maxLat, b.maxLon) <= normedDist;
        return b.maxLat - bbox.minLat > 0;
    }

    // test bottom intersect
    if (lat < b.minLat) {
        if (lon < b.minLon)
            return normDist(b.minLat, b.minLon) <= normedDist;
        if (lon > b.maxLon)
            return normDist(b.minLat, b.maxLon) <= normedDist;
        return bbox.maxLat - b.minLat > 0;
    }

    // test middle intersect
    if (lon < b.minLon)
        return bbox.maxLon - b.minLon > 0;
    if (lon > b.maxLon)
        return b.maxLon - bbox.minLon > 0;
    return true;
  }
}

• minLat, maxLat se puede reemplazar con minY, maxY y lo mismo para minLon, maxLon: reemplácelo con minX, maxX
• normDist es un método un poco más rápido que el cálculo de la distancia completa. Por ejemplo, sin la raíz cuadrada en el espacio euclidiano (o sin un montón de otras cosas para haversine): dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Por supuesto, si usa ese método normDist, tendrá que crear una normedDist = dist*dist;para el círculo

Vea el código completo de BBox y Circle de mi proyecto GraphHopper .

Creé clase para trabajar con formas espero que disfrutes

public class Geomethry {
  public static boolean intersectionCircleAndRectangle(int circleX, int circleY, int circleR, int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;

    float rectCenterX = rectangleX + rectHalfWidth;
    float rectCenterY = rectangleY + rectHalfHeight;

    float deltax = Math.abs(rectCenterX - circleX);
    float deltay = Math.abs(rectCenterY - circleY);

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle
        if(lengthHypotenuseSqure > ((rectHalfWidth+circleR)*(rectHalfWidth+circleR) + (rectHalfHeight+circleR)*(rectHalfHeight+circleR))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle of rectangle and circle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+circleR)*(rectMinHalfSide+circleR))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+circleR)*0.9) && (deltay > (rectHalfHeight+circleR)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
}

public static boolean intersectionRectangleAndRectangle(int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight, int rectangleX2, int rectangleY2, int rectangleWidth2, int rectangleHeight2){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;
    float rectHalfWidth2 = rectangleWidth2/2.0f;
    float rectHalfHeight2 = rectangleHeight2/2.0f;

    float deltax = Math.abs((rectangleX + rectHalfWidth) - (rectangleX2 + rectHalfWidth2));
    float deltay = Math.abs((rectangleY + rectHalfHeight) - (rectangleY2 + rectHalfHeight2));

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle
        if(lengthHypotenuseSqure > ((rectHalfWidth+rectHalfWidth2)*(rectHalfWidth+rectHalfWidth2) + (rectHalfHeight+rectHalfHeight2)*(rectHalfHeight+rectHalfHeight2))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        float rectMinHalfSide2 = Math.min(rectHalfWidth2, rectHalfHeight2);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+rectMinHalfSide2)*(rectMinHalfSide+rectMinHalfSide2))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+rectHalfWidth2)*0.9) && (deltay > (rectHalfHeight+rectHalfHeight2)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
  } 
}

Aquí está el código modificado 100% funcionando:

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

Aquí hay una prueba rápida de una línea para esto:

if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
  // They intersect.
}

Este es el caso alineado con el eje donde rect_halveshay un vector positivo que apunta desde el rectángulo en el medio a una esquina. La expresión dentro length()es un vector delta desde centerun punto más cercano en el rectángulo. Esto funciona en cualquier dimensión.

• Primero verifique si el rectángulo y la tangente cuadrada con el círculo se superponen (fácil). Si no se superponen, no chocan.
• Comprueba si el centro del círculo está dentro del rectángulo (fácil). Si está adentro, chocan.
• Calcule la distancia mínima al cuadrado desde los lados del rectángulo hasta el centro del círculo (poco duro). Si es menor que el radio al cuadrado, entonces chocan, de lo contrario no lo hacen.

Es eficiente porque:

• Primero verifica el escenario más común con un algoritmo barato y cuando está seguro de que no colisionan, termina.
• Luego verifica el siguiente escenario más común con un algoritmo barato (no calcule la raíz cuadrada, use los valores al cuadrado) y cuando esté seguro de que colisionan, termina.
• Luego ejecuta el algoritmo más costoso para verificar la colisión con los bordes del rectángulo.

funcionó para mí (solo funciona cuando el ángulo del rectángulo es 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;
}

Mejorando un poco la respuesta de 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);

Esto resta rect.w / 2y rect.h / 2una vez en lugar de hasta tres veces.

Para aquellos que tienen que calcular la colisión de Círculo / Rectángulo en Coordenadas Geográficas con SQL,
esta es mi implementación en el oráculo 11 del algoritmo sugerido por e.James .

En la entrada requiere coordenadas circulares, radio circular en km y dos coordenadas de vértices del rectángulo:

CREATE OR REPLACE FUNCTION "DETECT_CIRC_RECT_COLLISION"
(
    circleCenterLat     IN NUMBER,      -- circle Center Latitude
    circleCenterLon     IN NUMBER,      -- circle Center Longitude
    circleRadius        IN NUMBER,      -- circle Radius in KM
    rectSWLat           IN NUMBER,      -- rectangle South West Latitude
    rectSWLon           IN NUMBER,      -- rectangle South West Longitude
    rectNELat           IN NUMBER,      -- rectangle North Est Latitude
    rectNELon           IN NUMBER       -- rectangle North Est Longitude
)
RETURN NUMBER
AS
    -- converts km to degrees (use 69 if miles)
    kmToDegreeConst     NUMBER := 111.045;

    -- Remaining rectangle vertices 
    rectNWLat   NUMBER;
    rectNWLon   NUMBER;
    rectSELat   NUMBER;
    rectSELon   NUMBER;

    rectHeight  NUMBER;
    rectWIdth   NUMBER;

    circleDistanceLat   NUMBER;
    circleDistanceLon   NUMBER;
    cornerDistanceSQ    NUMBER;

BEGIN
    -- Initialization of remaining rectangle vertices  
    rectNWLat := rectNELat;
    rectNWLon := rectSWLon;
    rectSELat := rectSWLat;
    rectSELon := rectNELon;

    -- Rectangle sides length calculation
    rectHeight := calc_distance(rectSWLat, rectSWLon, rectNWLat, rectNWLon);
    rectWidth := calc_distance(rectSWLat, rectSWLon, rectSELat, rectSELon);

    circleDistanceLat := abs( (circleCenterLat * kmToDegreeConst) - ((rectSWLat * kmToDegreeConst) + (rectHeight/2)) );
    circleDistanceLon := abs( (circleCenterLon * kmToDegreeConst) - ((rectSWLon * kmToDegreeConst) + (rectWidth/2)) );

    IF circleDistanceLon > ((rectWidth/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat > ((rectHeight/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLon <= (rectWidth/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat <= (rectHeight/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;


    cornerDistanceSQ := POWER(circleDistanceLon - (rectWidth/2), 2) + POWER(circleDistanceLat - (rectHeight/2), 2);

    IF cornerDistanceSQ <=  POWER(circleRadius, 2) THEN
        RETURN 0;  --  -1 => NO Collision ; 0 => Collision Detected
    ELSE
        RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
END;    

Funciona, lo descubrí hace una semana, y ahora me puse a probarlo.

double theta = Math.atan2(cir.getX()-sqr.getX()*1.0,
                          cir.getY()-sqr.getY()*1.0); //radians of the angle
double dBox; //distance from box to edge of box in direction of the circle

if((theta >  Math.PI/4 && theta <  3*Math.PI / 4) ||
   (theta < -Math.PI/4 && theta > -3*Math.PI / 4)) {
    dBox = sqr.getS() / (2*Math.sin(theta));
} else {
    dBox = sqr.getS() / (2*Math.cos(theta));
}
boolean touching = (Math.abs(dBox) >=
                    Math.sqrt(Math.pow(sqr.getX()-cir.getX(), 2) +
                              Math.pow(sqr.getY()-cir.getY(), 2)));

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

Suponiendo que tiene los cuatro bordes del rectángulo, verifique la distancia desde los bordes hasta el centro del círculo, si es menor que el radio, entonces las formas se cruzan.

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

Si el rectángulo se cruza con el círculo, uno o más puntos de esquina del rectángulo deben estar dentro del círculo. Supongamos que los cuatro puntos de un rectángulo son A, B, C, D. al menos uno de ellos debe cruzar el círculo. entonces, si la distancia desde un punto al centro del círculo es menor que el radio del círculo, debe intersecar el círculo. Para obtener la distancia puedes usar el teorema de Pitágoras,

H^2 = A^2 + B^2

Esta técnica tiene algunos límites. Pero funcionará mejor para los desarrolladores de juegos. especialmente detección de colisiones

Es una buena actualización del algoritmo de Arvo.