Determining if two triangles in the same plane overlap is an important topic in collision detection.



Task

Determine which of these pairs of triangles overlap in 2D:

   (0,0),(5,0),(0,5)     and   (0,0),(5,0),(0,6)
   (0,0),(0,5),(5,0)     and   (0,0),(0,5),(5,0)
   (0,0),(5,0),(0,5)     and   (-10,0),(-5,0),(-1,6)
   (0,0),(5,0),(2.5,5)   and   (0,4),(2.5,-1),(5,4)
   (0,0),(1,1),(0,2)     and   (2,1),(3,0),(3,2)
   (0,0),(1,1),(0,2)     and   (2,1),(3,-2),(3,4)


Optionally, see what the result is when only a single corner is in contact (there is no definitive correct answer):

   (0,0),(1,0),(0,1)   and   (1,0),(2,0),(1,1)


T Triangle
   (Float, Float) p1, p2, p3
 
   F (p1, p2, p3)
      .p1 = p1
      .p2 = p2
      .p3 = p3
 
   F String()
      R ‘Triangle: #., #., #.’.format(.p1, .p2, .p3)
 
   F.const det2D()
      R .p1[0] * (.p2[1] - .p3[1])
      + .p2[0] * (.p3[1] - .p1[1])
      + .p3[0] * (.p1[1] - .p2[1])
 
F checkTriWinding(Triangle &t; allowReversed)
   V detTri = t.det2D()
   I detTri < 0.0
      assert(allowReversed, ‘Triangle has wrong winding direction’)
      swap(&t.p2, &t.p3)
 
F boundaryCollideChk(Triangle t, Float eps)
   R t.det2D() < eps
 
F boundaryDoesntCollideChk(Triangle t, Float eps)
   R t.det2D() <= eps
 
F triTri2D(Triangle &t1, &t2; eps = 0.0, allowReversed = 0B, onBoundary = 1B)
   checkTriWinding(&t1, allowReversed)
   checkTriWinding(&t2, allowReversed)
   V chkEdge = I onBoundary {:boundaryCollideChk} E :boundaryDoesntCollideChk
   V lp1 = [t1.p1, t1.p2, t1.p3]
   V lp2 = [t2.p1, t2.p2, t2.p3]
 
   L(i) 3
      V j = (i + 1) % 3
      I chkEdge(Triangle(lp1[i], lp1[j], lp2[0]), eps) &
        chkEdge(Triangle(lp1[i], lp1[j], lp2[1]), eps) &
        chkEdge(Triangle(lp1[i], lp1[j], lp2[2]), eps)
         R 0B
 
   L(i) 3
      V j = (i + 1) % 3
      I chkEdge(Triangle(lp2[i], lp2[j], lp1[0]), eps) &
        chkEdge(Triangle(lp2[i], lp2[j], lp1[1]), eps) &
        chkEdge(Triangle(lp2[i], lp2[j], lp1[2]), eps)
         R 0B
 
   R 1B
 
F overlap(Triangle &t1, &t2; eps = 0.0, allowReversed = 0B, onBoundary = 1B)
   I triTri2D(&t1, &t2, eps, allowReversed, onBoundary)
      print(‘overlap’)
   E
      print(‘do not overlap’)
 
V t1 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
V t2 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 6.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
 
t1 = Triangle((0.0, 0.0), (0.0, 5.0), (5.0, 0.0))
t2 = t1
print(t1" and\n"t2)
overlap(&t1, &t2, 0.0, 1B)
print()
 
t1 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
t2 = Triangle((-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
 
t1.p3 = (2.5, 5.0)
t2 = Triangle((0.0, 4.0), (2.5, -1.0), (5.0, 4.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
 
t1 = Triangle((0.0, 0.0), (1.0, 1.0), (0.0, 2.0))
t2 = Triangle((2.0, 1.0), (3.0, 0.0), (3.0, 2.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
 
t2 = Triangle((2.0, 1.0), (3.0, -2.0), (3.0, 4.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
 
t1 = Triangle((0.0, 0.0), (1.0, 0.0), (0.0, 1.0))
t2 = Triangle((1.0, 0.0), (2.0, 0.0), (1.0, 1.1))
print(t1" and\n"t2)
print(‘which have only a single corner in contact, if boundary points collide’)
overlap(&t1, &t2)
print()
 
print(t1" and\n"t2)
print(‘which have only a single corner in contact, if boundary points do not collide’)
overlap(&t1, &t2, 0.0, 0B, 0B)