Quel est le moyen le plus efficace pour détecter les intersections triangle triangle?

Question

Comment puis-je savoir si deux triangles se croisent dans l'espace euclidien 2D? (À savoir la géométrie 2D classique) donnée (X, Y) les coordonnées de chaque sommet de chaque triangle.

Answer 1

Une façon consiste à vérifier si les deux côtés du triangle A intersection avec un côté du triangle B, puis vérifier tous les six possibilités d'un point de a l'intérieur de B ou à un point B à l'intérieur de a.

Pour un point à l'intérieur d'un triangle voir par exemple:. Point test triangulaire

Lorsque nous testons les collisions sur les polygones que nous avons aussi un rectangle pour nos polygones. Nous avons donc premier test pour les collisions rectangle et s'il y a un hit nous procédons à la détection de collision de polygone.

Answer 2

mise en œuvre Python intersection ligne et point test triangulaire, 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

Il y a une démo .

Answer 3

Voici ma tentative au problème de collision triangle triangle (mis en œuvre 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)

Il fonctionne sur la base du fait que les triangles ne se chevauchent pas, si tous les points du triangle 1 sont sur le côté externe d'au moins l'un des bords du triangle 2 (ou vice versa est vrai). Bien sûr, les triangles ne sont jamais concaves.

Je ne sais pas si cette approche est plus ou moins efficace que les autres.

Bonus: Je l'ai porté C ++ https://gist.github.com/TimSC/5ba18ae21c4459275f90

Answer 4

Comme indiqué, vous devez vérifier qu'un point est à l'intérieur d'un triangle. La façon la plus simple de vérifier si un point est à l'intérieur d'un polygone fermé est de tracer une ligne droite dans une direction quelconque à partir du point et compter combien de fois la ligne traverse un sommet. Si la réponse est impair alors le point est dans le polygone, même, il est à l'extérieur.

à vérifier est celle qui va horizontalement simple ligne droite vers la droite du point (ou une autre direction perpendiculaire). Cela rend le contrôle pour le franchissement des sommets presque trivial. Les contrôles suivants devraient suffire:

• est le point de la coordonnée y entre les coordonnées y des deux extrémité points du sommet? Non, alors ne traverse pas.

• est du point de la coordonnée x supérieure au point d'extrémité droite le plus de le sommet? Oui, alors ne traverse pas.

• est du point de la coordonnée x moins que le point le plus éloigné de la fin gauche du sommet? Oui, fait alors croix.

• Si les cas ci-dessus échoue, vous pouvez utiliser le produit vectoriel du vecteur représentant le sommet et un vecteur formé à partir de l'extrémité du sommet de le point. Une réponse négative indique le point se trouve 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 parce qu'un produit croisé implique de prendre le sinus de deux vecteurs.

Answer 5

Qu'est-ce que vous cherchez vraiment est un algorithme « Point Polygon ». Si l'un des points d'un triangle sont dans l'autre, ils se croisent. Voici une bonne question pour vérifier.

Comment puis-je déterminer si un point 2D est dans un Polygon?