¿Intersección entre un rectángulo y un círculo?

Question

Tengo un conocimiento deficiente de matemáticas. Me gustaría calcular la detección de colisiones entre un círculo 2D y un rectángulo 2D para un juego simple de Pong.

Se me ocurrió dividir el rectángulo 2D en 4 líneas separadas, cada una con su propia ecuación, y luego igualar cada ecuación de línea con la ecuación del círculo para verificar los puntos de intersección. Una búsqueda en Math StackExchange arrojó esta publicación: solución #1.

(También: Me preguntaba por qué la diferencia en enfoque entre la solución #1 y esta solución #2? (EDICIÓN: La diferencia es que la solución #2 resuelve la intersección de un segmento de línea con un círculo mientras que la primera solución resuelve la intersección de una línea con un círculo.) ¿Por qué alguien usaría uno sobre el otro? Parece que la primera solución es más simple: resolver dos ecuaciones (¡hey puedo hacer eso!), mientras que la segunda solución involucra ecuaciones paramétricas (que no entiendo)).

Sin embargo, estoy curioso por una solución diferente. La solución anterior verifica una intersección entre la ecuación de una línea y la ecuación de un círculo (creo). ¿Qué tal verificar la intersección entre la ecuación de un rectángulo y un círculo? ¿Es lo mismo que decir la intersección entre un plano y un círculo (¿es un rectángulo un plano)? Pensé que los planos estaban definidos por 3 puntos ... mi rectángulo está definido por cuatro. Realmente no estoy seguro de lo que estoy diciendo ahora.

Preguntas:

1. ¿Es válida alguna de las soluciones #1 o #2 en la detección de colisiones?
2. ¿Qué solución (#1 o #2) es más preferible y por qué?
3. ¿Cómo puedo calcular la intersección entre un rectángulo 2D y un círculo 2D (sin dividir el rectángulo en cuatro líneas separadas)? Por favor elija la solución más directa ya que ya me resulta difícil seguir el concepto de ecuaciones paramétricas. ¿Podría también explicar la solución con cierto nivel de detalle? Estoy curioso de cómo funciona la matemática.

Answer 1

Respuestas a muchas preguntas

¿es un rectángulo un plano?

No, no lo es. Un plano es infinito en dos dimensiones, un rectángulo tiene un tamaño finito.

Pensé que los planos estaban definidos por 3 puntos

Eso es correcto, pero no es útil para tu aplicación.

mi rectángulo está definido por cuatro.

Dado que afirmas que tu rectángulo está alineado con las direcciones horizontal y vertical, dos puntos son suficientes. Para un rectángulo general, se necesitaría un tercer punto, o de hecho la mitad de un tercer punto (5 grados de libertad reales en total). Pero esto también es irrelevante para tu pregunta.

la ecuación de un rectángulo

No hay una ecuación para un rectángulo, solo un conjunto de desigualdades. Lo cual no se integra bien en el conjunto de tratar con múltiples ecuaciones.

¿es válido uno u otro de los resultados #1 o #2 en la detección de colisiones?

Cada uno funcionará para un caso de uso particular.

¿Qué solución (#1 o #2) es más preferible y por qué?

Dado que tu rectángulo está formado por cuatro segmentos de línea, la solución #2 es la indicada, como tu edición en respuesta al comentario de jshin47 ya indica.

La pregunta central

¿Cómo puedo calcular la intersección entre un rectángulo 2D y un círculo 2D (sin dividir el rectángulo en cuatro líneas separadas)?

Para el caso general de un círculo arbitrario y un rectángulo, optaría por las intersecciones entre el círculo y los segmentos de línea. Evitar esto solo complicará las cosas.

La Solución #2 parece ser un buen punto de partida. No es muy difícil: si el segmento de línea comienza en $(x_1,y_1)$ y termina en $(x_2,y_2)$ y tu círculo está centrado en $(x_C, y_C)$ y tiene un radio $r$, entonces tienes la única ecuación no lineal

$$((1-t)\cdot x_1 + t\cdot x_2 - x_C)^2 + ((1-t)\cdot y_1 + t\cdot y_2 - y_C)^2 = r^2$$

Resolviendo esta ecuación para $t$, podrías encontrar hasta dos soluciones. Si estas satisfacen $0\le t\le1$ entonces hay una intersección a lo largo del segmento de línea. Haz esto para los cuatro segmentos de línea, y si alguno interseca el círculo, entonces el rectángulo interseca el círculo.

La ecuación anterior se originó a partir de la ecuación del círculo, con un punto genérico en la línea (segmento) sustituido por $x$ y $y$.

$$\begin{align*} x &= (1-t)\cdot x_1 + t\cdot x_2 \\ y &= (1-t)\cdot y_1 + t\cdot y_2 \\ r^2 &= (x-x_C)^2 + (y-y_C)^2 \end{align*}$$

A diferencia de esta solución, uso $t=0$ para representar el punto inicial percibido $(x_1,y_1)$ de la línea, y $t=1$ para el punto final $(x_2,y_2)$. Esta elección no tiene impacto en tu problema, ya que la dirección de tus segmentos de línea es irrelevante. Pero es más útil o común en otras aplicaciones.

Si tienes problemas para entender estas ecuaciones paramétricas para $x$ e $y$, te sugiero que simplemente elijas puntos finales con coordenadas simples, y sustituyas algunos valores de $t$, tanto desde dentro como fuera del rango especificado. Verás cómo todos estos puntos se encuentran en la línea conectada, y el rango $0\le t\le 1$ corresponde al segmento de línea.

Nota que todo lo anterior no manejará el escenario donde el círculo está completamente contenido dentro del rectángulo, o viceversa. Así que tal vez quieras verificar si el centro del círculo está dentro del rectángulo, o si alguna esquina del rectángulo está dentro del círculo.

Rectángulo alineado

Si tu rectángulo está alineado con los ejes horizontal y vertical, puedes simplificar un poco las verificaciones de intersección. Aún examinaría cada borde por separado, pero utilizando un proceso de toma de decisiones más simple.

Como ejemplo, tomemos un borde horizontal, de $(x_1, y)$ a $(x_2, y)$. El círculo todavía está centrado en $(x_C, y_C)$ con radio $r$.

• Si $x_1 \le x_C \le x_2$, entonces el círculo intersecta la línea si $\lvert y - y_C\rvert \le r$. Esto significa que el centro del círculo y la línea no están a más de $r$ de distancia.
• De lo contrario, intersectan si $(x_1-x_C)^2+(y-y_C)^2\le r^2$ o $(x_2-x_C)^2+(y-y_C)^2\le r^2$. Esto significa que cualquiera de los extremos debe estar dentro del círculo.