¿Cómo puedo saber si dos triángulos se cruzan en el espacio euclidiano 2D? (es decir, geometría 2D clásica) dadas las coordenadas (X, Y) de cada vértice en cada triángulo.¿Cuál es la forma más eficiente de detectar intersecciones triángulo-triángulo?
Una forma es comprobar si dos lados de triángulo A intersect con cualquier lado del triángulo B, y después comprobar los seis posibilidades de un punto de A dentro de B o un punto de B dentro A.
Para una apuntar dentro de un triángulo, ver por ejemplo: Point in triangle test.
Cuando probamos colisiones en polígonos, también tenemos un rectángulo circundante para nuestros polígonos. Así que primero probamos las colisiones de rectángulo y si hay un , pulse y procedemos con la detección de colisión de polígono.
hi @Joe. Es correcto que verifiquemos los 3 lados de A contra los 3 lados de A contra los 3 lados de B. Pero como vamos a verificar si las esquinas de A están dentro de B (y viceversa), después de que la intersección del segmento de línea revise, todo el procedimiento sigue funcionando . Eso es porque si detectamos cualquier esquina dentro del otro triángulo, tenemos una colisión. –
sí, ahora es mucho más preciso. Gracias @Joe. ¡Aclamaciones! –
Solo necesita 4 puntos en las pruebas triangulares. https://jsfiddle.net/eyal/gxw3632c/ Este no es un algoritmo rápido para la intersección triángulo-triángulo – Eyal
Lo que realmente está buscando es un algoritmo de "punto en el polígono". Si alguno de los puntos de un triángulo está en el otro, se cruzan. Aquí hay una buena pregunta para ver.
Esto no dará una solución * general *, ya que es posible que dos triángulos se superpongan sin que ninguno de sus vértices esté dentro el otro. – gnovice
si solo se superpone un punto pequeño, es difícil saber qué punto seleccionar para la prueba –
Como se ha indicado, se tendrá que comprobar que un punto está dentro de un triángulo. La forma más sencilla de comprobar si un punto está dentro de un polígono cerrado es trazar una línea recta en cualquier dirección desde el punto y contar cuántas veces la línea cruza un vértice. Si la respuesta es impar, entonces el punto está en el polígono, incluso, luego está afuera.
La línea recta más simple para verificar es la que va horizontalmente a la derecha del punto (u otra dirección perpendicular). Esto hace que la comprobación del cruce de vértices sea casi trivial. Los siguientes controles deben ser suficientes:
¿El punto de coordenada entre las coordenadas de los dos puntos finales del vértice? No, entonces no se cruza.
¿La coordenada x del punto es mayor que el punto extremo derecho más alejado de el vértice? Sí, entonces no se cruza.
¿La coordenada x del punto es menor que el punto final más alejado del vértice? Sí, entonces cruza.
Si los casos anteriores no logran, entonces puede usar el producto cruzado del vector que representa el vértice y un vector formado a partir del final del vértice a el punto. Una respuesta negativa indicará que el punto se encuentra en un lado del vértice, una respuesta positiva en el otro lado del vértice y una respuesta cero en el vértice. Esto funciona porque un producto cruzado implica tomar el seno de dos vectores.
Esto no le dirá si dos triángulos se cruzan, que era la pregunta. No puedes simplemente probar los vértices de un triángulo, ya que los triángulos pueden cruzarse sin que haya vértices dentro uno del otro (por ejemplo, la estrella de David). – Ergwun
aplicación Python para line intersection y point in triangle test, con una pequeña modificación.
def line_intersect2(v1,v2,v3,v4):
'''
judge if line (v1,v2) intersects with line(v3,v4)
'''
d = (v4[1]-v3[1])*(v2[0]-v1[0])-(v4[0]-v3[0])*(v2[1]-v1[1])
u = (v4[0]-v3[0])*(v1[1]-v3[1])-(v4[1]-v3[1])*(v1[0]-v3[0])
v = (v2[0]-v1[0])*(v1[1]-v3[1])-(v2[1]-v1[1])*(v1[0]-v3[0])
if d<0:
u,v,d= -u,-v,-d
return (0<=u<=d) and (0<=v<=d)
def point_in_triangle2(A,B,C,P):
v0 = [C[0]-A[0], C[1]-A[1]]
v1 = [B[0]-A[0], B[1]-A[1]]
v2 = [P[0]-A[0], P[1]-A[1]]
cross = lambda u,v: u[0]*v[1]-u[1]*v[0]
u = cross(v2,v0)
v = cross(v1,v2)
d = cross(v1,v0)
if d<0:
u,v,d = -u,-v,-d
return u>=0 and v>=0 and (u+v) <= d
def tri_intersect2(t1, t2):
'''
judge if two triangles in a plane intersect
'''
if line_intersect2(t1[0],t1[1],t2[0],t2[1]): return True
if line_intersect2(t1[0],t1[1],t2[0],t2[2]): return True
if line_intersect2(t1[0],t1[1],t2[1],t2[2]): return True
if line_intersect2(t1[0],t1[2],t2[0],t2[1]): return True
if line_intersect2(t1[0],t1[2],t2[0],t2[2]): return True
if line_intersect2(t1[0],t1[2],t2[1],t2[2]): return True
if line_intersect2(t1[1],t1[2],t2[0],t2[1]): return True
if line_intersect2(t1[1],t1[2],t2[0],t2[2]): return True
if line_intersect2(t1[1],t1[2],t2[1],t2[2]): return True
inTri = True
inTri = inTri and point_in_triangle2(t1[0],t1[1],t1[2], t2[0])
inTri = inTri and point_in_triangle2(t1[0],t1[1],t1[2], t2[1])
inTri = inTri and point_in_triangle2(t1[0],t1[1],t1[2], t2[2])
if inTri == True: return True
inTri = True
inTri = inTri and point_in_triangle2(t2[0],t2[1],t2[2], t1[0])
inTri = inTri and point_in_triangle2(t2[0],t2[1],t2[2], t1[1])
inTri = inTri and point_in_triangle2(t2[0],t2[1],t2[2], t1[2])
if inTri == True: return True
return False
Hay un demo totalmente interactivo.
Esto obtiene la respuesta incorrecta en este caso: 't1 = [[0,0], [5,0], [0,5]]; t2 = [[-10,0], [- 5,0], [- 1,6]]; print (tri_intersect2 (t1, t2), False) ' – TimSC
@TimSC Sí, falla al detectar intersección para dos líneas paralelas. Puede hacer cumplir que | d | es mayor que un pequeño número positivo en la función 'line_intersect2'. –
No necesita hacer las 9 intersecciones de líneas, puede hacer solo 8. Porque si uno de los triángulos se cruza con el otro, también debe cruzar hacia atrás. Entonces, si hay 1 intersección, debe haber dos. Además, no necesita todo el punto en las pruebas triangulares porque, si no hay intersecciones, todos los puntos están dentro o ninguno. Entonces puedes hacer 8 line_intersect y 2 puntos en Triangle. O haga 6 line_intersect y luego 6 point en Triangle. Depende de lo que es más rápido para ti. – Eyal
Aquí está mi intento de resolver el problema del triángulo-triángulo de colisión (implementado en Python):
#2D Triangle-Triangle collisions in python
#Release by Tim Sheerman-Chase 2016 under CC0
import numpy as np
def CheckTriWinding(tri, allowReversed):
trisq = np.ones((3,3))
trisq[:,0:2] = np.array(tri)
detTri = np.linalg.det(trisq)
if detTri < 0.0:
if allowReversed:
a = trisq[2,:].copy()
trisq[2,:] = trisq[1,:]
trisq[1,:] = a
else: raise ValueError("triangle has wrong winding direction")
return trisq
def TriTri2D(t1, t2, eps = 0.0, allowReversed = False, onBoundary = True):
#Trangles must be expressed anti-clockwise
t1s = CheckTriWinding(t1, allowReversed)
t2s = CheckTriWinding(t2, allowReversed)
if onBoundary:
#Points on the boundary are considered as colliding
chkEdge = lambda x: np.linalg.det(x) < eps
else:
#Points on the boundary are not considered as colliding
chkEdge = lambda x: np.linalg.det(x) <= eps
#For edge E of trangle 1,
for i in range(3):
edge = np.roll(t1s, i, axis=0)[:2,:]
#Check all points of trangle 2 lay on the external side of the edge E. If
#they do, the triangles do not collide.
if (chkEdge(np.vstack((edge, t2s[0]))) and
chkEdge(np.vstack((edge, t2s[1]))) and
chkEdge(np.vstack((edge, t2s[2])))):
return False
#For edge E of trangle 2,
for i in range(3):
edge = np.roll(t2s, i, axis=0)[:2,:]
#Check all points of trangle 1 lay on the external side of the edge E. If
#they do, the triangles do not collide.
if (chkEdge(np.vstack((edge, t1s[0]))) and
chkEdge(np.vstack((edge, t1s[1]))) and
chkEdge(np.vstack((edge, t1s[2])))):
return False
#The triangles collide
return True
if __name__=="__main__":
t1 = [[0,0],[5,0],[0,5]]
t2 = [[0,0],[5,0],[0,6]]
print (TriTri2D(t1, t2), True)
t1 = [[0,0],[0,5],[5,0]]
t2 = [[0,0],[0,6],[5,0]]
print (TriTri2D(t1, t2, allowReversed = True), True)
t1 = [[0,0],[5,0],[0,5]]
t2 = [[-10,0],[-5,0],[-1,6]]
print (TriTri2D(t1, t2), False)
t1 = [[0,0],[5,0],[2.5,5]]
t2 = [[0,4],[2.5,-1],[5,4]]
print (TriTri2D(t1, t2), True)
t1 = [[0,0],[1,1],[0,2]]
t2 = [[2,1],[3,0],[3,2]]
print (TriTri2D(t1, t2), False)
t1 = [[0,0],[1,1],[0,2]]
t2 = [[2,1],[3,-2],[3,4]]
print (TriTri2D(t1, t2), False)
#Barely touching
t1 = [[0,0],[1,0],[0,1]]
t2 = [[1,0],[2,0],[1,1]]
print (TriTri2D(t1, t2, onBoundary = True), True)
#Barely touching
t1 = [[0,0],[1,0],[0,1]]
t2 = [[1,0],[2,0],[1,1]]
print (TriTri2D(t1, t2, onBoundary = False), False)
funciona basándose basan en el hecho de que los triángulos no se superponen si todos los puntos de triángulo 1 están el lado externo de al menos uno de los bordes del triángulo 2 (o viceversa es verdadero). Por supuesto, los triángulos nunca son cóncavos.
No sé si este enfoque es más o menos eficiente que los demás.
Bono: Me portado a C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90
Re el algoritmo hiciera más eficiente, no ha habido mucho trabajo hecho en esa pregunta - nadie ha demostrado de manera decisiva el que la variación es más rápido. Un problema es que gran parte de la discusión involucra tris en el espacio tridimensional. Ej. Realtimecollisiondetection.net/blog/?p=29 PS Tales problemas a menudo se expresan en términos de que los puntos están en el "lado correcto" de un segmento de línea. Ej. Http://www.mochima.com/articles/cuj_geometry_article/cuj_geometry_article.html Como Nick señala en su último párrafo, en la práctica todo se trata de lo bueno que hace el sacrificio. – Fattie