Comment puis-je savoir si deux triangles se croisent dans l'espace Euclidien 2D? (C'est-à-dire la géométrie 2D classique) Compte tenu des coordonnées (x, y) de chaque sommet dans chaque triangle.
6 Réponses :
Un moyen est de vérifier si les deux côtés du triangle A intersect avec n'importe quel côté du triangle B, puis vérifiez les six possibilités d'un point d'un point B ou un point de B à l'intérieur d'un.
Pour un point à l'intérieur d'un triangle, voir par exemple: point dans Triangle Test.
Lorsque nous testons des collisions sur des polygones, nous avons également un rectangle environnant pour nos polygones. Nous essuons donc d'abord pour les collisions rectangulaires et s'il y a un frappé nous procédons à la détection de collision polygone.
salut Joe. Il est correct que nous devions vérifier tous les 3 côtés d'un contre les 3 côtés de B. Mais car nous allons vérifier si les coins de A sont à l'intérieur B (et inversement) - après les chèques d'intersection du segment de ligne - Toute la procédure fonctionne toujours . C'est parce que si nous détectons un coin dans l'autre triangle, nous avons une collision.
Nécessite seulement 4 points dans les tests de triangle. jsfiddle.net/eyal/gxw3632c Ce n'est pas un algorithme rapide pour l'intersection Triangle-Triangle
Qu'est-ce que vous cherchez vraiment est un algorithme "point en polygone". Si l'un des points d'un triangle est de l'autre, ils se croisent. Voici une bonne question à vérifier.
Comment puis-je déterminer si un point 2D est dans un polygone?
Cela ne donnera pas une solution General , car il est possible que deux triangles se chevauchent sans que votre sommet ne soit à l'intérieur de l'autre.
Si seulement un minuscule se chevauche, il est difficile de savoir quel point de sélectionner pour le test
Comme indiqué, vous devrez vérifier qu'un point est à l'intérieur d'un triangle. Le moyen le plus simple de vérifier si un point est à l'intérieur d'un polygone fermé consiste à dessiner une ligne droite dans n'importe quelle direction du point et à compter combien de fois la ligne traverse un sommet. Si la réponse est impair, le point est dans le polygone, même s'il est dehors.
La ligne droite la plus simple à vérifier est celle qui va horizontalement à droite du point (ou une autre direction perpendiculaire). Cela rend le chèque de Vertex traversant presque trivial. Les chèques suivants doivent suffire:
est la coordonnée Y du point entre les coordonnées y des deux extrémités points du sommet? Non, alors ne traverse pas.
est la coordonnée X du point supérieur au point final le plus éloigné de le sommet? Oui, alors ne traverse pas.
est la coordonnée X du point inférieur au point d'extrémité gauche le plus éloigné du sommet? Oui, puis fait croix.
Si les cas ci-dessus échouent, alors vous pouvez Utilisez le produit croisé du vecteur représentant le sommet et un vecteur formé à partir de la fin du sommet à le point. Une réponse négative indiquera que le point réside sur un côté du sommet, une réponse positive de l'autre côté du sommet et une réponse zéro sur le sommet. Cela fonctionne car un produit croisé implique de prendre le sinus de deux vecteurs.
Cela ne vous dira pas si deux triangles se croisent, qui était la question. Vous ne pouvez pas simplement tester les sommets d'un triangle, car les triangles peuvent se croiser sans des sommets à l'autre (par exemple, étoile de David).
Pensez-vous vraiment que cela contribuera à "Quel est le moyen le plus efficace de détecter les intersections triangle-triangle?"
implémentation de python pour intersection de la ligne et Point dans Triangle Test , avec une petite modification.
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
Cela obtient la mauvaise réponse dans ce cas: t1 = [[0,0], [5,0], [0,5]]; T2 = [[10,0], [- 5,0], [- 1,6]]; Imprimer (Tri_InterSect2 (T1, T2), FALSE)
@ Ttimsc Oui, il ne parvient pas à détecter l'intersection de deux lignes parallèles. Vous pouvez appliquer que | D | est supérieur à un peu de points positat dans la fonction line_intersect2 .
Vous n'avez pas besoin de faire toutes les intersections de la ligne, vous pouvez en faire juste 8. Parce que si l'un des triangles se traverse dans l'autre, il doit également reculer. Donc, s'il y a 1 intersection, il doit y avoir deux. De plus, vous n'avez pas besoin de tout le point dans les tests de triangle car, s'il n'y a pas d'intersections, alors tous les points sont à l'intérieur ou aucun. Vous pouvez donc faire 8 lignes_intersect et 2 point dans Triangle. Ou faire 6 lignes_intersect puis 6 point dans le triangle. Dépend de ce qui est plus rapide pour vous.
Voici ma tentative du problème de collision triangle-triangle (implémenté dans 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)
Trier les sommets du triangle par ordonnance décroissante. Cela prend au plus trois comparaisons par triangle. Puis fusionner les deux séquences. Je suppose que cela prend au plus cinq comparaisons.
Maintenant pour chaque ordonnée, envisagez une ligne horizontale. Il coupe les deux triangles dans la plupart des segments de ligne, et c'est une question facile à vérifier que les segments se chevauchent. S'ils le font, ou s'ils changent d'ordre entre deux lignes, les triangles se croisent.
L'algorithme vraiment le plus efficace, il n'ya pas eu beaucoup de travail sur cette question - personne n'a montré de manière décisive quelle variation est la plus rapide. Un problème est que beaucoup de discussion implique Tris dans l'espace 3D. Par exemple, realtimecollisionDetection.net/blog/?p=29 PS Les problèmes sont souvent lancés en termes de points étant sur le "côté correct" d'un segment de ligne. Par exemple mochima.com/articles/cuj_geometry_article/.../a> Comme Nick pointe dans son Dernier para, dans la pratique, il s'agit de la façon dont vous êtes bon.