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)


// A triangle is three pairs of points: ( (x,y), (x,y), (x,y) )
 
fcn det2D(triangle){
   p1,p2,p3 := triangle;
   p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1]);
}
fcn checkTriWinding(triangle,allowReversed){ //-->triangle, maybe new
   detTri:=det2D(triangle);
   if(detTri<0.0){
      if(allowReversed){ p1,p2,p3 := triangle; return(p1,p3,p2); }  // reverse
      else throw(Exception.AssertionError(
		  "triangle has wrong winding direction"));
   }
   triangle	// no change
}
fcn triTri2D(triangle1,triangle2, eps=0.0, allowReversed=False, onBoundary=True){
   // Trangles must be expressed anti-clockwise
   triangle1=checkTriWinding(triangle1, allowReversed);
   triangle2=checkTriWinding(triangle2, allowReversed);
 
   chkEdge:=
      if(onBoundary) // Points on the boundary are considered as colliding
	 fcn(triangle,eps){ det2D(triangle)<eps }
      else           // Points on the boundary are not considered as colliding
	 fcn(triangle,eps){ det2D(triangle)<=eps };; // first ; terminates if
 
   t1,t2 := triangle1,triangle2;	// change names to protect the typist
   do(2){				// check triangle1 and then triangle2
      foreach i in (3){	//For edge E of trangle 1,
	 j:=(i+1)%3;	// 1,2,0
	 // 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(T(t1[i],t1[j],t2[0]), eps) and
	    chkEdge(T(t1[i],t1[j],t2[1]), eps) and
	    chkEdge(T(t1[i],t1[j],t2[2]), eps)) return(False);  // no collision
      }
      t2,t1 = triangle1,triangle2; // flip and re-test
   }
   True   // The triangles collide
}