What's the most efficient way to detect triangle-triangle intersections?

How 开发者_运维问答can I tell whether two triangles intersect in 2D Euclidean space? (i.e. classic 2D geometry) given the (X,Y) coordinates of each vertex in each triangle.

---

One way is to check if two sides of triangle A intersect with any side of triangle B, and then check all six possibilities of a point of A inside B or a point of B inside A.

For a point inside a triangle see for example: Point in triangle test.

When we test collisions on polygons we also have a surrounding rectangle for our polygons. So we first test for rectangle collisions and if there is a hit we proceed with polygon collision detection.

---

Python implementation for line intersection and point in triangle test, with a little 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

---

Sort the vertices of both triangle by decreasing ordinate. That takes at most three comparisons per triangle. Then merge the two sequences. I guess that this takes at most five comparisons.

Now for every ordinate, consider an horizontal line. It intersects both triangles in at most one line segment, and it is an easy matter to check it the segments do overlap. If they do, or if they change order between two lines, then the triangles intersect.

---

Update:

There is an affine transformation that can normalize one of the triangles to (0, 0)-(1, 0)-(0, 1). Apply it to the other and many computations will simplify.

---

Here is my attempt at the triangle-triangle collision problem (implemented 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)

It works based based on the fact that the triangles do not overlap if all the points of triangle 1 are on the external side of at least one of the edges of triangle 2 (or vice versa is true). Of course, triangles are never concave.

I don't know if this approach is more or less efficient than the others.

Bonus: I ported it to C++ https://gist.github.com/TimSC/5ba18ae21c4459275f90

---

I realize that this is a very old question, but here is Rosetta code for this task in many languages: https://rosettacode.org/wiki/Determine_if_two_triangles_overlap

---

As stated, you'll need to check that a point is inside a triangle. The simplest way to check if a point is inside a closed polygon is to draw a straight line in any direction from the point and count how many times the line crosses a vertex. If the answer is odd then the point is in the polygon, even, then it's outside.

The simplest straight line to check is the one going horizontally to the right of the point (or some other perpendicular direction). This makes the check for vertex crossing nearly trivial. The following checks should suffice:

• Is the point's y-coordinate between the y-coordinates of the two end points of the vertex? No, then doesn't cross.

• Is the point's x-coordinate greater than the furthest right end point of the vertex? Yes, then doesn't cross.

• Is the point's x-coordinate less than the furthest left end point of the vertex? Yes, then does cross.

• If the cases above fail, then you can use the cross product of the vector representing the vertex and a vector formed from the end of the vertex to the point. A negative answer will indicate the point lies on one side of the vertex, a positive answer on the other side of the vertex, and a zero answer on the vertex. This works because a cross product involves taking the sine of two vectors.

---

What you're really looking for is a "Point in Polygon" algorithm. If any of the points of one triangle are in the other, they are intersecting. Here is a good question to check out.

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