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

Question

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.

Lookout

Re the truly most efficient algorithm, there has not been much work done on that question - nobody has decisively shown which variation is fastest. One problem is that a lot of the discussion involves tris in 3D space. Eg realtimecollisiondetection.net/blog/?p=29 PS Such problems are often cast in terms of points being on the "correct side" of a line segment. Eg mochima.com/articles/cuj_geometry_article/… As Nick points out in his last para, in practice it is all about how good you do culling. – Lauter

Answer 1

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.

Bobbobb

hi @Joe. It's correct that we should check all 3 sides of A against all 3 sides of B. But since we're going to check if A's corners are inside B (and vice versa) - after the line segment intersection checks - the whole procedure still works. That's because if we detect any corner inside the other triangle, we have a collision. – Bobbobb

Only need 4 point in triangle tests. jsfiddle.net/eyal/gxw3632c This is not a fast algorithm for triangle-triangle intersection – Lundeen

Answer 2

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

Rootstock

This gets the wrong answer in this case: t1 = [[0,0],[5,0],[0,5]]; t2 = [[-10,0],[-5,0],[-1,6]]; print (tri_intersect2(t1, t2), False) – Pudens

@Pudens Yes, it fails to detect intersection for two parallel lines. You can enforce that |d| is greater than a little positve number in function line_intersect2. – Rootstock

You don't need to do all 9 line intersections, you can do just 8. Because if one of the triangles crosses over into the other, it must also cross back out. So if there is 1 intersection, there must be two. Also, you don't need all the point in triangle tests because, if there are no intersections, then either all the points are inside or none. So you can do 8 line_intersect and 2 point in Triangle. Or do 6 line_intersect and then 6 point in Triangle. Depends what's faster for you. – Lundeen

Answer 3

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.

Pelargonium

Answer 4

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

Pudens

Answer 5

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

Carrasco

Answer 6

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.

Sediment

This won't tell you if two triangles intersect, which was the question. You can't just test one triangle's vertices, as triangles can intersect without any vertices being inside each other (e.g. star of david). – Doyen

Do you really think it will helps with "What's the most efficient way to detect triangle-triangle intersections?" – Willock

Answer 7

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?

Papistry

This won't give a general solution, since it's possible for two triangles to overlap without either of their vertices being inside the other. – Schlesien

if only a tiny point overlap, it is hard to know which point to select for test – Unclothe