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)


# Points are realized as arrays of two numbers [x, y]
 
# Triangles are realized as triples of Points [p1, p2, p3] 
 
# Input: a Triangle
def det2D:
  . as [ [$p1x, $p1y],  [$p2x, $p2y],  [$p3x, $p3y]] 
  | $p1x * ($p2y - $p3y) +
    $p2x * ($p3y - $p1y) +
    $p3x * ($p1y - $p2y) ;
 
# Input: a Triangle
def checkTriWinding(allowReversed):
  if det2D < 0
  then if allowReversed
       then . as [$p1, $p2, $p3]
       | [$p1, $p3, $p2 ]
       else "Triangle has wrong winding direction" | error
       end
  else .
  end;
 
def boundaryCollideChk(eps): det2D < eps;
 
def boundaryDoesntCollideChk(eps): det2D <= eps;
 
def triTri2D($t1; $t2; $eps; $allowReversed; $onBoundary):
  def chkEdge:
    if $onBoundary then boundaryCollideChk($eps)
    else boundaryDoesntCollideChk($eps)
    end;
 
  # Triangles must be expressed anti-clockwise
  ($t1|checkTriWinding($allowReversed))
  |  ($t2|checkTriWinding($allowReversed))
  # 'onBoundary' determines whether points on boundary are considered as colliding or not
  # for each edge E of t1
  | first( range(0;3) as $i
        | (($i + 1) % 3) as $j
        # Check all points of t2 lie on the external side of edge E.
        # If they do, the triangles do not overlap.
        | if ([$t1[$i], $t1[$j], $t2[0]]| chkEdge) and
             ([$t1[$i], $t1[$j], $t2[1]]| chkEdge) and
             ([$t1[$i], $t1[$j], $t2[2]]| chkEdge) 
          then 0
          else empty
  	  end) // true
  | if . == 0 then false
    else 
    # for each edge E of t2
    first( range(0;3) as $i
        |  (($i + 1) % 3) as $j
        # Check all points of t1 lie on the external side of edge E.
        # If they do, the triangles do not overlap.
        | if ([$t2[$i], $t2[$j], $t1[0]] | chkEdge) and
             ([$t2[$i], $t2[$j], $t1[1]] | chkEdge) and
             ([$t2[$i], $t2[$j], $t1[2]] | chkEdge) 
	  then 0
	  else empty
	  end) // true
    | if . == 0 then false
      else true # The triangles overlap
      end
    end ;