Jaki jest najbardziej skuteczny sposób wykrywania skrzyżowań trójkąt-trójkąt?

Question

Jak mogę stwierdzić, czy dwa trójkąty przecinają się w przestrzeni euklidesowej 2D? (tj. klasyczna geometria 2D) z uwzględnieniem współrzędnych (X, Y) każdego wierzchołka w każdym trójkącie.

Answer 1

Jednym ze sposobów jest sprawdzenie, czy dwa boki trójkąta A intersect z każdej strony trójkąta B, a następnie sprawdzić, wszystkie sześć możliwości punktu A wewnątrz B lub punkt B wewnątrz A.

dla A punkt wewnątrz trójkąta patrz na przykład: Point in triangle test.

Podczas testowania kolizji na wielokątach mamy również otaczający prostokąt dla naszych wielokątów. Dlatego najpierw testujemy kolizje prostokątów i jeśli istnieje hit, kontynuujemy wykrywanie kolizji wielokąta.

Answer 2

Tym, czego naprawdę szukasz, jest algorytm "Point in Polygon". Jeśli którykolwiek z punktów jednego trójkąta znajduje się w drugim, przecinają się. Oto dobre pytanie do sprawdzenia.

How can I determine whether a 2D Point is within a Polygon?

Answer 3

Jak stwierdzono, trzeba sprawdzić, czy punkt znajduje się wewnątrz trójkąta. Najprostszym sposobem sprawdzenia, czy punkt znajduje się wewnątrz zamkniętego wielokąta, jest narysowanie linii prostej w dowolnym kierunku od punktu i zliczenie, ile razy linia przecina wierzchołek. Jeśli odpowiedź jest dziwna, to punkt jest w wielokącie, nawet, to jest na zewnątrz.

Najprostszą prostą do sprawdzenia jest ta, która biegnie poziomo na prawo od punktu (lub innego prostopadłego kierunku). To sprawia, że ​​sprawdzanie przejścia wierzchołków jest prawie banalne. Poniższe kontrole powinny wystarczyć:

• jest punktem jest współrzędna y między Y współrzędne dwóch koniec punkty wierzchołka? Nie, następnie nie przechodzi.

• Czy współrzędna x punktu jest większa niż najdalszy prawy punkt końcowy wierzchołka? Tak, wtedy się nie krzyżuje.

• Czy współrzędna x punktu jest mniejsza niż najdalszy lewy punkt końcowy wierzchołka? Tak, to się krzyżuje.

• Jeśli przypadki powyżej zawiodą, wówczas można używać produktu Krzyż wektora reprezentującej wierzchołek oraz wektor utworzone od końca wierzchołka do chodzi. Negatywna odpowiedź wskaże punkt leżący po jednej stronie wierzchołka, pozytywną odpowiedź po drugiej stronie wierzchołka i zerową odpowiedź na wierzchołku. Działa to, ponieważ krzyżowy produkt obejmuje wzięcie sinusa dwóch wektorów.

Answer 4

implementacja Pythona do line intersection i point in triangle test, z niewielką modyfikacją.

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 

Dostępny jest pełny interaktywny demo.

Answer 5

Oto moja próba na problem kolizji trójkąt-trójkąt (wdrożone w Pythonie):

#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) 

To działa na podstawie opiera się na fakcie, że trójkąty nie pokrywają się, czy wszystkie punkty trójkąta 1 są na zewnętrzna strona co najmniej jednej krawędzi trójkąta 2 (lub odwrotnie jest prawdą). Oczywiście trójkąty nigdy nie są wklęsłe.

Nie wiem, czy to podejście jest mniej lub bardziej efektywne niż inne.

Bonus: ja przeniesiony go do C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90