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)
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:
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 no es necesario realizar los cálculos cuatro veces. La imagen muestra el área en la que ahora debe estar el centro del círculo. Tenga en cuenta que sólo 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 distancia de los bordes del rectángulo. El centro del círculo tiene que estar dentro de este borde rojo para que se produzca la intersección.
El segundo par de líneas elimina los casos fáciles en los que el círculo está lo suficientemente lejos del rectángulo (en cualquier dirección) como para que no sea posible ninguna intersección. Esto corresponde al área verde de la imagen.
El tercer par de líneas maneja los casos fáciles en los que el círculo está lo suficientemente cerca del rectángulo (en cualquier dirección) como para garantizar 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.
Las líneas restantes calculan el caso difícil en el que el círculo puede cruzar la esquina del rectángulo. Para resolver, calcula la distancia desde el centro del círculo y la esquina, y luego verifica 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 en rojo y devuelve verdadero para todos los círculos cuyo centro está dentro del área sombreada en blanco.
Solo hay dos casos en los que 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 ninguna de las aristas tiene un punto en el círculo (si todas las aristas están completamente "fuera" del círculo), entonces la única forma en que el círculo aún puede cruzar el polígono es si se encuentra completamente dentro del círculo. polígono.)
Con esa idea, funcionará algo como lo siguiente, donde el círculo tiene centro Py radio , Ry el rectángulo tiene vértices A,,,, en ese orden (no es código completo) B:CD
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 de los métodos de polígonos funcionará, pero para un rectángulo puedes comprobar si esto funciona:
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
Y intersectCircle()también 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 en caso contrario.
Lo bueno es que la misma idea funciona no sólo para rectángulos sino también para la intersección de un círculo con cualquier polígono simple : ¡ni siquiera tiene que ser convexo!
