Wie kann ich feststellen, ob sich zwei Dreiecke im euklidischen 2D-Raum schneiden? (d. h. klassische 2D-Geometrie) unter Berücksichtigung der (X, Y) -Koordinaten jedes Eckpunkts in jedem Dreieck.Wie können Dreieck-Dreieck-Schnittpunkte am effizientesten erkannt werden?
Eine Möglichkeit ist es, wenn zwei Seiten des Dreiecks A intersect mit jeder Seite des Dreiecks B zu überprüfen, und dann alle sechs Möglichkeiten eines Punkt eines Inneren B prüfen oder einem Punkt B innerhalb A.
Für eine Punkt innerhalb eines Dreiecks siehe zum Beispiel: Point in triangle test.
Wenn wir Kollisionen auf Polygonen testen wir auch eine umgebende Rechteck für unsere Polygone haben. Also testen wir zuerst auf Rechteckkollisionen und wenn es einen Treffer gibt, fahren wir mit Polygonkollisionserkennung fort.
Hallo @Joe. Es ist richtig, dass wir alle 3 Seiten von A gegen alle 3 Seiten von B überprüfen sollten. Aber da wir überprüfen werden, ob die Ecken von A innerhalb von B liegen (und umgekehrt) - nach den Überprüfungen der Liniensegmentüberschneidung - funktioniert die ganze Prozedur immer noch . Das liegt daran, dass wir eine Kollision haben, wenn wir eine Ecke innerhalb des anderen Dreiecks entdecken. –
Ja, jetzt ist es viel genauer. Danke @Joe. Prost! –
Benötigen nur 4 Punkte in Dreieckstests. https://jsfiddle.net/eyal/gxw3632c/ Dies ist kein schneller Algorithmus für Dreieck-Dreieck-Schnittpunkte. – Eyal
Was Sie wirklich suchen, ist ein "Point in Polygon" -Algorithmus. Wenn einer der Punkte eines Dreiecks in dem anderen liegt, kreuzen sie sich. Hier ist eine gute Frage zu überprüfen.
Dies wird keine * allgemeine * Lösung ergeben, da es möglich ist, dass sich zwei Dreiecke überlappen, ohne dass einer ihrer Eckpunkte innen ist das andere. – gnovice
Wenn sich nur ein winziger Punkt überschneidet, ist es schwierig zu wissen, welcher Punkt für den Test ausgewählt werden soll. –
Wie bereits erwähnt, müssen Sie prüfen, ob ein Punkt innerhalb eines Dreiecks. Die einfachste Möglichkeit, um zu überprüfen, ob sich ein Punkt innerhalb eines geschlossenen Polygons befindet, besteht darin, eine gerade Linie vom Punkt in eine beliebige Richtung zu zeichnen und zu zählen, wie oft die Linie einen Scheitelpunkt schneidet. Wenn die Antwort ungerade ist, dann ist der Punkt gerade im Polygon, dann ist er draußen.
Die einfachste zu prüfende Gerade ist diejenige, die sich horizontal rechts vom Punkt (oder einer anderen senkrechten Richtung) befindet. Dies macht die Überprüfung auf Vertex-Crossing fast trivial. Folgende Kontrollen sollten genügen:
ist der Punkt, der Y-Koordinate zwischen der y-Koordinaten der beiden Ende Punkte des Scheitels? Nein, dann kreuzt nicht.
Ist der Punkt des x-Koordinate größer ist als der am weitesten rechts Endpunkt die Spitze? Ja, dann kreuzt nicht.
Ist die x-Koordinate des Punktes kleiner als der äußerste linke Endpunkt des Scheitelpunkts? Ja, dann kreuzt es.
Wenn die obigen Fällen fehlschlagen, dann kann man verwenden das Kreuzprodukt des Vektors den Scheitelpunkt und einen Vektor, der vom Ende des Scheitels ausgebildet der Punkt. Eine negative Antwort zeigt an, dass der Punkt auf einer Seite des Scheitelpunkts, eine positive Antwort auf der anderen Seite des Scheitelpunkts und eine Nullantwort auf dem Scheitelpunkt liegt. Dies funktioniert, weil ein Kreuzprodukt den Sinus zweier Vektoren beinhaltet.
Dies wird Ihnen nicht sagen, ob sich zwei Dreiecke überschneiden, was die Frage war. Sie können nicht einfach die Eckpunkte eines Dreiecks testen, da sich Dreiecke kreuzen können, ohne dass irgendwelche Eckpunkte ineinander liegen (z. B. Davidstern). – Ergwun
Python-Implementierung für line intersection und point in triangle test, mit einer wenig Änderung.
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
Es gibt eine vollständige interaktive demo.
Das bekommt in diesem Fall die falsche Antwort: 't1 = [[0,0], [5,0], [0,5]]; t2 = [[-10,0], [- 5,0], [- 1,6]]; print (tri_intersect2 (t1, t2), False) ' – TimSC
@TimSC Ja, es kann keine Kreuzung für zwei parallele Linien gefunden werden. Sie können das | d | erzwingen ist größer als eine kleine positive Zahl in der Funktion 'line_intersect2'. –
Sie müssen nicht alle 9 Linienkreuzungen machen, Sie können nur 8 machen. Denn wenn eines der Dreiecke in das andere übergeht, muss es auch wieder durchqueren. Wenn es also eine Kreuzung gibt, müssen es zwei sein. Außerdem brauchen Sie nicht alle Punkte in Dreiecks-Tests, denn wenn keine Kreuzungen vorhanden sind, dann sind alle Punkte innerhalb oder keine. So können Sie 8 line_intersect und 2 Punkte in Triangle machen. Oder mache 6 line_intersect und dann 6 Punkte in Triangle. Hängt davon ab, was schneller für dich ist. – Eyal
Hier ist mein Versuch, das Problem Dreieck-Dreieck Kollision (in Python implementiert):
#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)
Es arbeitet auf der Grundlage der Tatsache, dass die Dreiecke alle nicht überlappen, wenn die Punkte des Dreiecks 1 eingeschaltet sind die Außenseite von mindestens einer der Kanten des Dreiecks 2 (oder umgekehrt ist wahr). Natürlich sind Dreiecke niemals konkav.
Ich weiß nicht, ob dieser Ansatz mehr oder weniger effizient ist als die anderen.
Bonus: Ich habe es zu C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90
Re die wirklich effizienteste Algorithmus portieren, hat es nicht viel Arbeit zu dieser Frage getan gewesen - niemand hat entscheidend gezeigt, welche Variante am schnellsten ist. Ein Problem ist, dass ein Großteil der Diskussion Tris im 3D-Raum betrifft. ZB realtimecollisiondetection.net/blog/?p=29 PS Solche Probleme werden oft in Bezug auf Punkte auf der "richtigen Seite" eines Liniensegments gegossen werden. ZB http://www.mochima.com/articles/cuj_geometry_article/cuj_geometry_article.html Wie Nick in seinem letzten Para hervorhebt, geht es in der Praxis alles darum, wie gut du es killst. – Fattie