Colisión entre círculo y triángulo 2d

[Loover]

[editando]

[senior wapo]

Esto es correcto pero incompleto. Por ejemplo que pasa si la distancia es negativa y en valor absoluto menor que el radio. ¿Hay invasion? Puede que si y puede que no.

Si se cumple para las 3 rectas necesariamente hay invasión. Hay que comprobar siempre y en todo caso las 3 rectas a menos que en una ya esté lo bastante alejado.

Loover pide que la respuesta sea un booleano indicando si hay invasión de algún tipo o no, luego no es necesario calcular donde ni como.

@Loover: Viendo el código de Pogacha me he dado cuenta que en mi explicación he usado directamente el vector del segmento y no su normal, aunque luego en el texto me refiera a la normal.

La normal la calculas girando 90 grados el vector a un lado u a otro, lo que se traduce en ajustar signos (X o Y según sentido de giro) e intercambiar X e Y. Es en la parte en donde pone tangente (técnicamente el nombre correcto).

@Pogacha: Bonito código, está bastante limpio y estructurado. Deberías ver el spaguetti que yo hago a veces.

[nostromo]

Sobre la idea del triangulo ampliado:



El circulo de abajo a la derecha tiene el centro dentro pero esta fuera del triangulo original. (Según he estado dándole vueltas siempre cerca de los vértices están los casos especiales no triviales)

[nostromo]

Si se cumple para las 3 rectas necesariamente hay invasión. Hay que comprobar siempre y en todo caso las 3 rectas a menos que en una ya esté lo bastante alejado.

Si. Pero si se cumple(distancia negativa y absoluta menor que el radio) solo en dos rectas ¿hay invasión siempre? no siempre
No tengo tiempo ahora de pintar un ejemplo... más tarde a ver si puedo...

Lo de decir donde esta el circulo en mi solución solo es para aclarar los casos de prueba que es necesario hacer.

Un saludo
Nostromo

[Loover]

Jo que rápidos sois:

El circulo de abajo a la derecha tiene el centro dentro pero esta fuera del triangulo original. (Según he estado dándole vueltas siempre cerca de los vértices están los casos especiales no triviales)

Me dí cuenta también justo después de postear. Le estoy dando vueltas aquí sobre papel y en los casos de las esquinas la envolvente mayor no sería un triángulo... sino una curva (hecha con el radio). Pero en estos casos se podría ver si el vértice está dentro del círculo y ya se sabría así si hay colisión...

[Pogacha]

Ok, mi algoritmo falla.

Me olvide el segundo de los casos y que cuando se proyecta se debe verificar la distancia:

- COLISION SI el triangulo esta dentro del circulo. (Implementación: Test facil con los vertices y el radio)
- COLISION SI el circulo esta completamente dentro del triangulo
PARA TODOS los segmentos del triangulo la distancia(por el lado hacia dentro del triangulo) al centro del circulo es mayor o igual a su radio.
(Implementación: Test utilizando el pseudocodigo de senior wapo, distancia punto a recta)
- COLISION SI existen 2 o más puntos de intersección de la circunferencia con los segmentos del triangulo, contando las intersecciones con todos los segmentos. (Implementación: Test de intersección de segmento con circunferencia para todos los segmentos)

Yo lo escribiria así:

- NO COLISION si para algun segmento el producto punto de la tangente al segmento por el circulo menos el dezplazamiento al origen del segmento es mayor al radio.

- COLISION si el centro del circulo esta dentro del triangulo

- COLISION si la proyeccion del centro del circulo contra un segmento esta dentro del segmento y la distancia del centro del circulo a ese segmento es menor o igual al radio.

- COLISION si la distancia a un vertice del centro del circulo, es menor o igual al radio.

- NO COLISION si llego hasta aqui.

[nostromo]

Sobre el caso especial que le comentaba a senior wapo : 2 rectas con distancia negativa(hacia afuera) y absoluta menor que el radio.



Como vemos el circulo puede estar solapado o fuera... por eso decía que no es trivial... hay que verlo por casos


Saludos
Nostromo

[Loover]

¿Funcionaría esto?



Creamos un triángulo más grande que el original, desde cada cara ampliamos la cara la distancia del radio.

Algoritmo:
- Vemos si el centro del círculo está dentro del triángulo pequeño. Si es así, devolver cierto (hay colisión).
- Vemos si el centro del círculo está dentro del triángulo creado (más grande)
- Si es así, ahora verificamos que algún vértice está dentro del círculo, porque pude ser que sea un caso especial (el de las esquinas) y que realmente no haya colisión. Si un vértice está dentro del círculo, devolver cierto (hay colisión). En el dibujo que he puesto si la hay.

¿Correcto?

Funcionaría correctamente para los casos especiales:


¿No?

[senior wapo]

Si, es cierto, lo olvidé. De hecho lo expliqué en este hilo de hace 3 años en referencia a un cuadrado (hay gráfico).

http://www.stratos-ad.com/forums3/viewtopic.php?t=4123&view=previous&sid=c78682150407c64c0a08e93f47bb9947

Para evitar comparar con los 3 vértices en el caso de ese hilo (contra cuadrado) recomendaba elegir el vértice a comparar usando signos (centro del círculo - centro del cuadrado)
En el caso del triéngulo con orientación arbitraria se me ocurre que el vértice a comparar es aquél que no forma parte del segmento cuya distancia al circulo es mayor (en valor absoluto). Al fin y al cabo las distancias las tenemos que calcular primero.

[Pogacha]

Jo que rápidos sois:

El circulo de abajo a la derecha tiene el centro dentro pero esta fuera del triangulo original. (Según he estado dándole vueltas siempre cerca de los vértices están los casos especiales no triviales)

Me dí cuenta también justo después de postear. Le estoy dando vueltas aquí sobre papel y en los casos de las esquinas la envolvente mayor no sería un triángulo... sino una curva (hecha con el radio). Pero en estos casos se podría ver si el vértice está dentro del círculo y ya se sabría así si hay colisión...

Por eso tenes que comprobar la proyeccion sobre el segmento.

Aca se ven todos los casos.

Si el centro esta en la zona verde esta fuera, esto se cumple cuando la distancia con signo a algun segmento es mayor al radio(*).
Si esta en la violeta esta dentro, esto es cuando todas las distancias con signos a todos los segmentos son negativos(*).
Si esta en alguna de las amarillas esta dentro, esto es si la distancia del centro del circulo a algun vertice es menor al radio.
Si esta en la marron rosasea es que esta dentro, esto es cuando la proyeccion a un segmento donde la distancia con signo sea positiva este dentro del segmento.
Con esto hemos descartado todo el espacio exepto las esquinas rojas, el centro estará en ellas y por ende esta descartado.
Saludos


* Tomar en cuenta el signo que tu tengas definido.[/img]

[Loover]

Pogacha:

Bueno, es lo mismo que digo yo (no en ese post que comentas, sino en uno posterior), solo que yo no hago proyecciones ¿no?. ¿Qué sería más rápido? O igual me estoy liando y estás diciendo exactamente lo mismo. Por cierto, ¿cómo se crearía ese triángulo más grande que comento yo? El triángulo cuyos lados se "amplian" la distancia del radio...

[Pogacha]

No, tu algoritmo fracasa, tienes que si o si buscar un metodo donde tomes un angulo recto con respecto al segmento, la proyeccion hace exactamente eso.

Ese triangulo mas grande lo logras al sumar el radio al desplazamiento al origen del segmento.

[Loover]

No veo donde está el error, estoy algo denso hoy. ¿Puedes ponerme un ejemplo donde fracase, por favor?

Algoritmo:
1) Vemos si el centro del círculo está dentro del triángulo. Si es así, devolver cierto (hay colisión).
2) Creamos el triángulo más grande. (Sus lados se amplián la distancia del radio, usando la normal de cada lado, en las esquinas quedará más separado, ahí están los casos especiales).
3.a) Vemos si el centro del círculo está dentro del triángulo creado (más grande). Si está fuera, devolver falso (no hay colisión)
3.b) Si está dentro, ahora verificamos que algún vértice del triángulo está dentro del círculo, porque puede ser que sea un caso especial (el de las esquinas) y que realmente no haya colisión. Si un vértice está dentro del círculo, devolver cierto (hay colisión) sino, devolver falso (no hay colisión).

[Pogacha]

No, perdon, es exactamente lo mismo o incluso mejor.
Me confundio tu dibujo, las normales al segmento te dan un angulo recto e incluso es mas "tranqui" de implementar que proyectando.

[Loover]

Guay, por una vez una "idea féliz" funciona. Aunque fijo que habrá por ahí métodos mas rápidos. Pero bueno, casi mejor algo que pueda hacer y entender yo mismo mientras no vaya lentísimo.

Estoy muy verde en álgebra, a ver si logro crear el triángulo este más grande... las otras dos funciones (dentro del círculo, dentro del triángulo), ya las tengo.

En cuanto tenga resultados, los postearé.