Detección de colisiones triangulares en espacio 2D

Question

¿Cómo puedo detectar mediante programación si dos triángulos se tocan entre sí o no, dados sus vértices en un plano de coordenadas 2D? Esto incluye tocar puntos o bordes, así como si un triángulo está completamente dentro del otro.

Answer 1

intersección Uso Línea Línea

https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-line-intersection-and-its-applications/#line_line_intersection

Ten en cuenta también la posibilidad de que algún vértice podría estar tocando uno de los lados del otro triángulo.

http://www.blackpawn.com/texts/pointinpoly/default.html

function SameSide(p1,p2, a,b) 
    cp1 = CrossProduct(b-a, p1-a) 
    cp2 = CrossProduct(b-a, p2-a) 
    if DotProduct(cp1, cp2) >= 0 then return true 
    else return false 

function PointInTriangle(p, a,b,c) 
    if SameSide(p,a, b,c) and SameSide(p,b, a,c) 
     and SameSide(p,c, a,b) then return true 
    else return false 

O mirar en este enlace y desplazarse hacia abajo

http://compsci.ca/v3/viewtopic.php?t=6034

Answer 2

Puede probar que los dos triángulos no colisionan mediante la búsqueda de un borde (de un total de 6 aristas que forman los dos triángulos) que actúa como una línea de separación donde todos los vértices de un triángulo se encuentran en un lado y los vértices del otro triángulo se encuentran en el otro lado. Si puede encontrar tal borde, significa que los triángulos no se cruzan, de lo contrario, los triángulos están colisionando.

Aquí hay una implementación de Matlab de la función de colisión triangular. Usted puede encontrar que la teoría de la función sameside aquí: http://www.blackpawn.com/texts/pointinpoly/default.html

function flag = triangle_intersection(P1, P2) 
% triangle_test : returns true if the triangles overlap and false otherwise 

% P1, P2: a 3 by 2 array (each), describing the vertices of a triangle, 
% the first column corresponds to the x coordinates while the second column 
% corresponds to the y coordinates 

    function flag = sameside(p1,p2,a,b) 
     % sameside : returns true if the p1,p1 lie on same sides of the 
     % edge ab and false otherwise 

     p1(3) = 0; p2(3) = 0; a(3) = 0; b(3) = 0; 
     cp1 = cross(b-a, p1-a); 
     cp2 = cross(b-a, p2-a); 
     if(dot(cp1, cp2) >= 0) 
      flag = true; 
     else 
      flag = false; 
     end 
    end 

% Repeat the vertices for the loop 
P1(4:5,:) = P1(1:2,:); 
P2(4:5,:) = P2(1:2,:); 

flag = true; 

% Testing all the edges of P1 
for i=1:3 
    if(~sameside(P1(i,:), P2(1,:), P1(i+1,:), P1(i+2,:)) ... 
      && sameside(P2(1,:), P2(2,:), P1(i+1,:), P1(i+2,:)) ... 
      && sameside(P2(2,:), P2(3,:), P1(i+1,:), P1(i+2,:))) 
     flag = false; return; 
    end 
end 

% Testing all the edges of P2 
for i=1:3 
    if(~sameside(P2(i,:), P1(1,:), P2(i+1,:), P2(i+2,:)) ... 
      && sameside(P1(1,:), P1(2,:), P2(i+1,:), P2(i+2,:)) ... 
      && sameside(P1(2,:), P1(3,:), P2(i+1,:), P2(i+2,:))) 
     flag = false; return; 
    end 
end 

end 

Answer 3

En resumen, la respuesta de Hassan es más rápido.

https://jsfiddle.net/eyal/gxw3632c/

Este es el código más rápido en javascript:

// check that all points of the other triangle are on the same side of the triangle after mapping to barycentric coordinates. 
// returns true if all points are outside on the same side 
var cross2 = function(points, triangle) { 
    var pa = points.a; 
    var pb = points.b; 
    var pc = points.c; 
    var p0 = triangle.a; 
    var p1 = triangle.b; 
    var p2 = triangle.c; 
    var dXa = pa.x - p2.x; 
    var dYa = pa.y - p2.y; 
    var dXb = pb.x - p2.x; 
    var dYb = pb.y - p2.y; 
    var dXc = pc.x - p2.x; 
    var dYc = pc.y - p2.y; 
    var dX21 = p2.x - p1.x; 
    var dY12 = p1.y - p2.y; 
    var D = dY12 * (p0.x - p2.x) + dX21 * (p0.y - p2.y); 
    var sa = dY12 * dXa + dX21 * dYa; 
    var sb = dY12 * dXb + dX21 * dYb; 
    var sc = dY12 * dXc + dX21 * dYc; 
    var ta = (p2.y - p0.y) * dXa + (p0.x - p2.x) * dYa; 
    var tb = (p2.y - p0.y) * dXb + (p0.x - p2.x) * dYb; 
    var tc = (p2.y - p0.y) * dXc + (p0.x - p2.x) * dYc; 
    if (D < 0) return ((sa >= 0 && sb >= 0 && sc >= 0) || 
        (ta >= 0 && tb >= 0 && tc >= 0) || 
        (sa+ta <= D && sb+tb <= D && sc+tc <= D)); 
    return ((sa <= 0 && sb <= 0 && sc <= 0) || 
      (ta <= 0 && tb <= 0 && tc <= 0) || 
      (sa+ta >= D && sb+tb >= D && sc+tc >= D)); 
} 

var trianglesIntersect4 = function(t0, t1) { 
    return !(cross2(t0,t1) || 
      cross2(t1,t0)); 
} 

que escribió el violín de arriba para probar algunas técnicas diferentes y comparar la velocidad. Todas las técnicas se basan en una combinación de tres herramientas diferentes:

1. Baricéntrico prueba de punto en el triángulo: convertir un punto de x, y espacio para u, v espacio donde u, v son dos caras de el triangulo. Luego prueba si el punto está dentro del triángulo (0,0) (0,1) (1,0), lo cual es fácil.
2. lado misma prueba de punto en el triángulo: Esta prueba le indica si un ángulo es más o menos de 180 grados. Si el triángulo es a, b, c y su punto es p, compruebe si el ángulo pab y bac son ambos más o ambos menos de 180. Debe hacer esto para ab, bc y ca. Si alguno es cierto, el punto está afuera. Esta prueba es más lenta que baricéntrica por un punto.
3. Line segmento intersección: Comprobar si el segmento de línea a, b interseca la línea segmento c, d. Para hacer eso, encontrará el punto donde se cruzan las dos líneas y luego verifique que esas líneas estén en el cuadro delimitador de a, by b, c. Esto es casi tan rápido como Barycentric.

Esas son las herramientas.Ahora, para averiguar si los triángulos se cruzan, hay 3 formas en que he probado:

1. 8 intersección de líneas y 2 de punto en el triángulo: sólo necesita 8 intersección de líneas y no todos 9 porque no puede ser solo 1 intersección. Después de eso, necesitas 2 puntos en triángulo en caso de que 1 triángulo esté completamente dentro del otro.
2. intersección de 6 líneas y 4 puntos en triángulo: Si la dibuja, puede ver que puede ignorar por completo un lado de uno de los triángulos para la intersección de línea y luego hacer todos los puntos de otros triángulos para punto en triángulo. Debido a que la intersección de línea y la baricéntrica son aproximadamente la misma velocidad, esto no es mucho mejor que el # 1. Pero si utilizó el mismo lado, será más rápido porque el mismo punto en triángulo es más lento.
3. 9 pruebas de punto en triángulo en el mismo lado: Puede usar cualquier baricentro o el mismo lado. Para cualquiera, modifique el punto en triángulo para probar 3 puntos al mismo tiempo y no quiere simplemente probar que son los tres fuera del triángulo, debe probar que están todos 3 fuera de en el el mismo lado. Debido a que estamos reutilizando mucha información, podemos ahorrar tiempo en los cálculos. Una vez más, baricéntrico parece un poco más rápido que el mismo lado aquí también.