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

[Loover]

Llevo todo el día buscado por google una función que realice una detección de colisión entre un triángulo y un círculo en un plano 2d:

Código [Seleccionar] Expand


// Point es un vector de 2 coordenadas (horizonta, vertical)
bool IsCircleToTriangleCollision (point posCircle, int radius, point v1, point v2, point v3)


Que lo que haga sea devolverme cierto si hay colisión entre un círculo de posición "circle" y radio "radius" y un triángulo de vértices "v1", "v2" y "v3". Y colisión me refiero a que se solapen, vamos, que no me vale que solo intersecten. Es decir, un triángulo dentro de un círculo o viceversa es colisión.

He encontrado muchas cosas, pero casi todas son colisiones entre rectángulos o entre polígonos o de círculo a círculo, colisiones todas ellas que ya tengo implementadas. Y tampoco encuentro código fuente.

Solo necesito "collision", no un vector que describa la "collision response".

Fijo que alguien me resuelve esta duda en un plisplas :)

[Tei]

Hoy estoy vago..  

yo de matematicas se muy poco, pero.. ¿no puede reducir tu problema a colision de un segmento y un circulo?

por otra parte, seguramente puedes calcular el punto de un segmento que si trazas una linea de ese punto, al centro del circulo, ese trazo es perpendicular a la linea. Si ese punto ese segmento tiene una longitud infedior a r, entonces el segmento corta al circulo.  No se si me he explicado bien.

lo que no se, es como calcular ese punto. Pero ese punto, otro punto cualquiera del segmento, y el centro del circulo, forman un triangulo rectangulo. Lo cual seguramente es una pista.  Dadme una folio, un lapiz, una toballa, media bañera llena de agua caliente, una toballa, y dentro de media hora estare gritando EUREKA!

oops: no habia visto lo de que decias que no te vale como colision que solo intersecten. Joder.. si solo quieres saber si un trinagulo esta dentro de un criculo, solo compruebna si los vertices del triangulo estan dentro del circulo.   el calculo de distancia es una eso de sqrt(abs(xi-xc)+abs(yi-yc)) que no me acuerdo como se llama.

[[EX3]]

Y colisión me refiero a que se solapen, vamos, que no me vale que solo intersecten. Es decir, un triángulo dentro de un círculo o viceversa es colisión.

Pues si lo que quieres saber si se solapa el triangulo dentro del circulo yo creo que con calcular las distancias de los vertices del triangulo respecto al centro de la circunferencia y comprobar que sean iguales o menores al radio bastaria. Si los 3 vertices son iguales o menores en distancia al centro es que el triangulo esta dentro del circulo.

Salu2...

[Loover]

Bueno, ideas, he visto varias por internet, lo que me serviría de veras es el código fuente en c++ de la función que os he puesto. Pero bueno, como os habeis tomado la molestia de escribir (gracias de veras), os respondo a ambos.

1) Sobre lo que comenta [EX3]:

Pues si lo que quieres saber si se solapa el triangulo dentro del circulo yo creo que con calcular las distancias de los vertices del triangulo respecto al centro de la circunferencia y comprobar que sean iguales o menores al radio bastaria. Si los 3 vertices son iguales o menores en distancia al centro es que el triangulo esta dentro del circulo.

Eso, no sé porque, es lo primero que se me ocurrió a mi también, pero es erroneo.. Con eso solo sabrás si los vértices están o no dentro del círculo. Mira la figura y verás por qué rápidamente:


2) En cuanto a lo que comenta Tei:

¿no puede reducir tu problema a colision de un segmento y un circulo?

No, así no sabría si el círculo está totalmente dentro del triángulo o al revés. Ya lo comenté en el post anterior.

Lo segundo que propones también lo había pensado yo, pero nuevamente no vale, porque si está dentro no hay intersección. Lo que se podría hacer es calcular el punto de ese segmento (que va del centro del círculo en dirección al centro del triángulo y de longitud la del radio)  está dentro del triángulo: así sí funcionaria. Y la función para saber si un punto está dentro de un triángulo ya la tengo, fácil. Esa es la forma que yo había pensado... pero estoy seguro que todas estas chapuzas que se me ocurren a mi sobre el papel, se podrían hacer mil veces más rápido de otra forma.



Vamos, que no quiero reinventar la rueda, quiero un código fuente en c++ que lo haga de manera rápida y eficiente, sin preocuparme mucho cómo funciona. Si nadie da otra propuesta mejor o un link a función que ya lo haga pues lo implementaré de la menera que he puesto en el segundo dibujo. Pero me cuesta creer que no pueda encontrarlo en google... y eso que busco en inglés :P

[tamat]

que tal un triangle-sphere collision ?

Yo suelo usar esta tabla pero por desgracia cada dia los enlaces estan mas muertos.

[Mars Attacks]

Hmmm... Tres puntos que definen rectas dos a dos; tres inecuaciones que resuelven el lado "bueno" a partir del punto que no define su recta. Calculas si el centro del círculo está en el lado "bueno" de las tres inecuaciones y luego compruebas si intersectan o no.

Si están en el lado bueno y no intersectan, uno está dentro del otro, o viceversa.

[Loover]

¡Buena tabla Tamat! Hay algo de circle to triangle aquí: http://www.andrewaye.com/TgS%20MLE@COLLISION/TgS%20Collision%20-%20Circle-Triangle.cpp.html
Bastante lioso sin explicaciones, le echaré un vistazo con calma luego.

Hmmm... Tres puntos que definen rectas dos a dos; tres inecuaciones que resuelven el lado "bueno" a partir del punto que no define su recta. Calculas si el centro del círculo está en el lado "bueno" de las tres inecuaciones y luego compruebas si intersectan o no.

Si están en el lado bueno y no intersectan, uno está dentro del otro, o viceversa.

Inecuacinamelo en una función escrita en c++ :D, o funciones matemáticas, o un dibujito. Que el lenguaje castellano pa estas cosas es algo chungo.

[senior wapo]

Si la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.

Se asume que el lado positivo es el interior del triángulo, por ejemplo, tomando el orden de los vértices en el sentido de las agujas del reloj.

Es el mismo concepto que has programado mil veces en octrees, bsps y cualquier otro sistema de particionamiento convexo: lo que está a un lado (ej: el positivo) del separador puede estar dentro o no (hay que probar todos los separadores), pero lo que está al otro lado, está fuera seguro.

[Loover]

Si la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.

Define "distancia". Supongo que te refieres al segmento con dirección de la normal de la cara del triángulo al centro del círculo. ¿Y cómo va a ser negativa?

¿Código fuente?

[senior wapo]

Si la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.

Define "distancia". Supongo que te refieres al segmento con dirección de la normal de la cara del triángulo al centro del círculo. ¿Y cómo va a ser negativa?

¿Código fuente?

No me seas vago que poniendo "line circle intersection" te salen mil links en google :P

Si tu sustituyes un punto en la ecuación de una recta el valor resultante es positivo o negativo según a que lado estés. La distancia, es el valor absoluto de esa magnitud.

Ax + By - D = 0 (te suena a la ecuación del plano pero con Z=0?)

A,B es el vector que va del vértice de origen al vértice destino y D es el valor de Y en la recta cuando la prolongas hasta x=0.

Hay otras formas de representar las ecuaciones de una recta, aunque en este caso no te sirven, es para que entiendas:

Código [Seleccionar] Expand

x´= x1 + t * (x2-x1)
y´= y1 + t * (y2-y1)

Llamamos "distancia" al valor de t (cuantas veces hay que multiplicar el vector de dirección para llegar al destino). Si ésta formula la aplicamos a la normal de la recta para llegar al centro del circulo, te sale la "distancia".

La fórmula a usar es la primera, que si te das cuenta A*x + B*Y es el Dot product que aparece en el código que has puesto, considerando A,B y X,Y como dos vectores (que lo son).

La distancia D de la fórmula la conviertes en cero si consideras que el vertice de inicio del lado del triángulo es el origen de coordenadas. Por tanto, si tanto al segundo vértice como al centro del círculo les restas el vértice de origen, te queda:

Cx * X2 + Cy * Y2 = 0

donde a todos esos términos le ha restado previamente x1,y1.

Supongo que ahora podrás entender mejor el código, si no, pregunta lo que sea.

Por cierto, me he saltado el tema de normalzaciones y demás para no complicarlo o termino escribiéndote de nuevo el código que has puesto o que encuentres por ahí :P

[senior wapo]

Define "distancia". Supongo que te refieres al segmento con dirección de la normal de la cara del triángulo al centro del círculo. ¿Y cómo va a ser negativa?

Respondiéndote en una frase: si la normal apunta adentro del triángulo, la distancia te sale con signo contrario a si la normal apunta hacia fuera del triángulo.

[senior wapo]

Añado (ale 3 post seguidos) para que entiendas el signo mejor:

Si coges la normal de una arista del triángulo y la lanzas desde el centro del círculo, tarde o temprano chocará con la recta o se alejará en dirección contraria, dependiendo de a que lado hayas cogido la normal.

[[EX3]]

1) Sobre lo que comenta [EX3]:

Pues si lo que quieres saber si se solapa el triangulo dentro del circulo yo creo que con calcular las distancias de los vertices del triangulo respecto al centro de la circunferencia y comprobar que sean iguales o menores al radio bastaria. Si los 3 vertices son iguales o menores en distancia al centro es que el triangulo esta dentro del circulo.

Eso, no sé porque, es lo primero que se me ocurrió a mi también, pero es erroneo.. Con eso solo sabrás si los vértices están o no dentro del círculo. Mira la figura y verás por qué rápidamente:

Quizas no me explique bien:

Si mal no entendi tu buscas lo primero:

Código [Seleccionar] Expand

Colision = (Dist(A, O) =< R) && (Dist(B, O) =< R) && (Dist(C, O) =< R)
En cuanto uno de los vectores este fuera de la circunferencia su distancia al centro de esta sera superior a su radio. Que no sea el metodo mas optimo no te lo discuto :P

Salu2...

EDITO, disculpar pero hoy voy un poco lento de neuronas, no duermo mucho estos ultimos dias y ya me esta pasando factura :P Mi codigo oviamente solo vale para triangulos mas pequeños que el circulo, pero no para el caso inverso que es el que muestras arriba.

[Pogacha]

Código [Seleccionar] Expand



enum {
CLOCKWISE = -1,
COLINEAR = 0,
COUNTERCLOCKWISE = 1
};

const float Epsilon = 0.0001f;

struct Vector2 {

const static Vector2 Zero;

Vector2() { }
Vector2(float _x,float _y) : x(_x), y(_y) { }
Vector2(const Vector2 &v) : x(v.x), y(v.y) { }

int operator==(const Vector2 &V) const { return (fabs(x-V.x)<Epsilon && fabs(y-V.y)<Epsilon); }
int operator!=(const Vector2 &V) const { return (fabs(x-V.x)>Epsilon || fabs(y-V.y)>Epsilon); }

float Dot(const Vector2 &t) const { return x * t.x + y * t.y; }

Vector2 operator*(float f) const { return Vector2(x * f,y * f); }
Vector2 operator/(float f) const { f=1.0f/f; return Vector2(x * f,y * f); }
Vector2 operator+(const Vector2 &t) const { return Vector2(x + t.x, y + t.y); }
Vector2 operator-() const { return Vector2(-x,-y); }
Vector2 operator-(const Vector2 &t) const { return Vector2(x - t.x , y - t.y); }

Vector2 &operator*=(float f) { return *this = *this * f; }
Vector2 &operator/=(float f) { return *this = *this / f; }
Vector2 &operator+=(const Vector2 &t) { return *this = *this + t; }
Vector2 &operator-=(const Vector2 &t) { return *this = *this - t; }

operator float*() { return w; }
operator const float*() const { return w; }

float &operator[](int i) { return w[i]; }
const float operator[](int i) const { return w[i]; }

Vector2 Tangent(void) const { return Vector2(y, -x); }

float Length() const { return float(sqrt(x*x + y*y)); }

float Angle() const {
float d=Length();
if(d<Epsilon) return 0.0f;
float a=Rad2Deg(acos(x/d));
return (y<0.0f) ? 360.0f-a : a;
}

float Square_Length() const { return x*x + y*y; }

float Normalize() {
float inv, l = Length();
if(l>Epsilon) inv = 1.0f / l;
u *= inv;
v *= inv;
return l;
}



//***************************************************************
// To determine a triangle side
//***************************************************************

static inline int Triangle_Side(const Vector2 a, const Vector2 b, const Vector2 c)
{
const float d = (b-a).Dot( (c-a).Tangent() );

if( d > Epsilon ) return CLOCKWISE;
if( d < -Epsilon ) return COUNTERCLOCKWISE;

return COLINEAR;
}


static bool Are_Segments_Crossing(const Vector2& a1, const Vector2& a2, const Vector2& b1, const Vector2& b2)
{
Vector2 t;

t = (a2-a1).Tangent();
if( t.Dot(b1-a1) * t.Dot(b2-a1) > Epsilon*Epsilon) return false;

t = (b2-b1).Tangent();
if( t.Dot(a1-b1) * t.Dot(a2-b1) > Epsilon*Epsilon) return false;

return true;
}

union {
struct {
float x,y;
};
struct {
float u,v;
};
float w[2];
};
};



struct Circle
{
 Vector2 Center;
 float Radius;

 Circle() { }
 Circle(const Vector2 &c, float r) : Center(c), Radius(r) { }

 bool Intersection(const Vector2 &v) const
 {
 Vector2 c=v-Center;
 return  c.Dot(c) <= Square(Radius);

 }

 // segment, not tested
 bool Intersection(const Vector2 &a, const Vector2 &b) const
 {
 Vector2 ba = b-a;
 Vector2 ca = Center-a;
 float d = ba.Tangent().Dot(ca);
 if( d > Radius ) return false;
 if( d < Radius ) return false;

 if( (ca).Square_Length() < Radius*Radius) return true;
 if( (Center-b).Square_Length() < Radius*Radius) return true;

 float l = ba.Square_Length();
 d = ba.Dot(ca);

 if( d <= l && d >= 0.0f) return true;
 }


 // triangle, not tested
 bool Intersection(const Vector2 &a, const Vector2 &b, const Vector2 &c) const
 {
 const Vector2 v[3] = { a, b, c };
 Vector2 dv[3];
 Vector2 dc[3];

 int j = 2;
 for(int i=0; i<3; ++i)
 {
 dv[i] = v[i] - v[j];
 dc[i] = Center - v[i];
 if(dv[i].Tangent().Dot(dc[i]) > Radius) return false;
 j = i;
 }

 for(int i=0; i<3; ++i)
 if(dc[i].Square_Length() > Radius*Radius) return true;

 j = 2;
 for(int i=0; i<3; ++i)
 {
 float d = dv[i].Dot(dc[j]);
 if(d >= 0.0f)
 {
 float l = dv[i].Square_Length();
 if(d <= l) return true;
 }
 j = i;
 }
 
 return false;
 }

 bool Intersection(const Box2 &c) const
 {
 if(c.Intersection(Center)) return true;
 float r;
 r = fmin( Square(c.Min.x - Center.x) , Square(c.Max.x - Center.x));
 r += fmin( Square(c.Min.x - Center.x) , Square(c.Max.x - Center.x));
 return  r <= Square(Radius);
 }

 bool Intersection(const Circle &c) const
 {
 Vector2 d=c.Center - Center;
 return  d.Square_Length() <= Square(Radius + c.Radius);
 }
};


No esta probado ojo.

El algoritmo es:

Descartar si el producto punto de la tangente a un segmento por el origen del circulo mas el dezplazamiento al origen del segmento es mayor al radio.

Si la distancia del origen del circulo a un vertice es menor que el radio entonces esta dentro.

Determinar la proyeccion del origen del circulo a la recta donde posa un segmento, si el proyectado esta dentro del segmento incorporar (hay intersepcion)

Saludos

[nostromo]

Si la distancia del centro del círculo a al menos una de las 3 rectas que definen el triángulo es negativa y superior en valor absoluto al radio no hay invasión del triángulo.

Se asume que el lado positivo es el interior del triángulo, por ejemplo, tomando el orden de los vértices en el sentido de las agujas del reloj.

.

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.

El problema no es trivial, hay que tener en cuenta los diferentes casos.

Mi solucion(por casos):
- 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)

Saludos
Nostromo