Was ist der effizienteste Weg, um zu erkennen, Dreieck-Dreieck-Kreuzungen?

Wie kann ich feststellen, ob zwei Dreiecke schneiden sich im 2D euklidischen Raum? (d.h. klassische 2D-geometrie) angesichts der (X,Y) - Koordinaten jedes vertex in jedem Dreieck.

Re das wirklich die meisten effizienten Algorithmus, hat es nicht viel Arbeit, die Frage - niemand hat sich entschlossen gezeigt, welche variation ist am schnellsten. Ein problem ist, dass ein Großteil der Diskussion bezieht tris im 3D-Raum. ZB realtimecollisiondetection.net/blog/?p=29 PS Solche Probleme sind Häufig gegossen in Bezug auf die Punkte auf der "richtigen Seite" eines Segments. ZB mochima.com/articles/cuj_geometry_article/..., Als Nick weist in seinem letzten Absatz, in der Praxis ist es alles darüber, wie gut Sie tun Keulen.

InformationsquelleAutor José Joel. | 2009-10-18

17

Eine Möglichkeit ist, zu überprüfen, ob zwei Seiten von Dreieck A schneiden mit jeder Seite des Dreiecks B, und überprüfen Sie dann alle sechs Möglichkeiten, einen Punkt von A in B oder a Punkt B innerhalb A.

Für einen Punkt innerhalb eines Dreiecks siehe zum Beispiel: Punkt-in-Dreieck-test.

Wenn wir den test auf Kollisionen mit Polygonen, wir haben auch eine umschreibende Rechteck für unsere Polygone. Also haben wir den ersten test für Rechteck-Kollisionen und wenn es ein Treffer wir gehen mit polygon-Kollisionserkennung.
- hi @Joe. Es ist richtig, dass wir überprüfen sollten, alle 3 Seiten Einer gegen alle 3 Seiten von B. Aber da wir gehen, um zu überprüfen, ob Eine der Ecken sind innen B (und Umgekehrt) - nach den line-segment-intersection - checks- das ganze Verfahren noch funktioniert. Das ist, weil, wenn wir erkennen, jede Ecke im anderen Dreieck, haben wir eine Kollision.
- ja, jetzt ist es viel präziser. Danke @Joe. Prost!
- Müssen nur die 4-Punkt-in-Dreieck-tests. jsfiddle.net/eyal/gxw3632c Dies ist nicht eine schnelle Algorithmus für-Dreieck-Dreieck-Kreuzung
InformationsquelleAutor Nick Dandoulakis

Python-Implementierung für line Kreuzung und Punkt-in-Dreieck-test, mit einer kleinen Modifikation.

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 ist eine vollständige interaktive demo.

Dieser bekommt die falsche Antwort, in diesem Fall: t1 = [[0,0],[5,0],[0,5]]; t2 = [[-10,0],[-5,0],[-1,6]]; print (tri_intersect2(t1, t2), False)
Ja, es schlägt fehl, zu erkennen, Schnittpunkt, für zwei parallele Linien. Sie können erzwingen, dass |d| größer ist als ein wenig positve Zahl in der Funktion line_intersect2.
Sie müssen nicht alle 9 Linien Kreuzungen, kann man eben nur 8. Denn wenn eines der Dreiecke, Kreuze über in das andere, es muss auch cross wieder aus. Also, wenn es 1 Kreuzung, es müssen zwei sein. Auch müssen Sie nicht alle der Punkt im Dreieck Prüfungen, weil, wenn es keine überschneidungen, dann entweder alle Punkte innerhalb oder keiner. So können Sie do 8 line_intersect und 2-Punkt-in-Dreieck. Oder do 6 line_intersect und dann 6-Punkt-in-Dreieck. Hängt davon ab, was ist schneller für Sie.

InformationsquelleAutor Martin Wang

Hier ist mein Versuch, das Dreieck-Dreieck-Kollisions-problem (implementiert in 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)

Funktioniert es basiert auf der Grundlage der Tatsache, dass die Dreiecke nicht überlappen, wenn alle Punkte des Dreiecks 1 sind auf der Außenseite mindestens einer der Kanten des Dreiecks 2 (oder Umgekehrt, ist wahr). Natürlich, Dreiecke, nie konkav.

Ich weiß nicht, ob dieser Ansatz mehr oder weniger effizient ist als die anderen.

Bonus: ich portiert, es auf C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90

InformationsquelleAutor TimSC

-3

Wie gesagt, müssen Sie überprüfen, ob ein Punkt in einem Dreieck. Der einfachste Weg, um zu überprüfen, ob ein Punkt in einem geschlossenen polygon zu zeichnen ist eine gerade Linie in jede Richtung von dem Punkt, und zählen, wie viele Male die Linie überquert einen Scheitelpunkt. Wenn die Antwort ist ungerade, dann ist der Punkt im polygon, selbst dann ist es draußen.

Einfachsten geraden Linie zu prüfen ist, die eine horizontal rechts neben dem Punkt (oder eine andere senkrechte Richtung). Dies macht die Prüfung für vertex Kreuzung fast trivial. Die folgenden Kontrollen sollten ausreichen:
- Ist der Punkt die y-Koordinate zwischen
  die y-Koordinaten der beiden end -
  Punkte der Scheitelpunkt? Nein, dann
  nicht cross.
- Ist der Punkt die x-Koordinate größer als der am weitesten rechten Punkt aus Ende
  die vertex? Ja, dann nicht kreuzen.
- Ist der Punkt die x-Koordinate kleiner als der am weitesten linken Ende der vertex? Ja, dann kreuzen.
- Wenn die oben genannten Fälle von scheitern, dann können Sie
  verwenden Sie das Kreuzprodukt der Vektor
  Vertreter der vertex und Vektor
  gebildet, der aus dem Ende des vertex zu
  der Punkt. Eine negative Antwort wird zeigen, liegt der Punkt auf einer Seite des vertex eine positive Antwort auf der anderen Seite des vertex, und eine null-Antwort auf den Scheitel. Dies funktioniert, weil ein Kreuzprodukt beinhaltet, dass der Sinus von zwei Vektoren.
- Dies werde Ihnen nicht sagen, wenn zwei Dreiecke schneiden, das war die Frage. Sie können nicht nur testen, ein Dreieck die Ecken als Dreiecke schneiden ohne Scheitelpunkte in jeder anderen (z.B. Davidstern).
- Glaubst du wirklich, es hilft, mit "Was ist der effizienteste Weg, um zu erkennen, Dreieck-Dreieck-Kreuzungen?"
InformationsquelleAutor Guillermo Phillips
-5

Was Sie wirklich suchen ist eine "Point in Polygon" - Algorithmus. Wenn einer der Punkte eines Dreiecks sind in der anderen, Sie schneiden. Hier ist eine gute Frage, um heraus zu überprüfen.

Wie kann ich feststellen, ob ein 2D-Punkt innerhalb eines Polygons?
- Diese geben nicht einen general Lösung, da es möglich ist, für zwei Dreiecke überlappen, ohne entweder von deren Knoten im inneren des anderen.
- wenn nur ein winziger Punkt überschneiden, ist es schwer zu wissen, welcher Punkt wählen Sie für den test
InformationsquelleAutor snicker

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.