Determine if two triangles overlap

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 definitively correct answer):

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

C++

<lang cpp>#include <vector>

include <iostream>
include <stdexcept>

using namespace std;

typedef std::pair<double, double> TriPoint;

inline double Det2D(TriPoint &p1, TriPoint &p2, TriPoint &p3) { return +p1.first*(p2.second-p3.second) +p2.first*(p3.second-p1.second) +p3.first*(p1.second-p2.second); }

void CheckTriWinding(TriPoint &p1, TriPoint &p2, TriPoint &p3, bool allowReversed) { double detTri = Det2D(p1, p2, p3); if(detTri < 0.0) { if (allowReversed) { TriPoint a = p3; p3 = p2; p2 = a; } else throw std::runtime_error("triangle has wrong winding direction"); } }

bool BoundaryCollideChk(TriPoint &p1, TriPoint &p2, TriPoint &p3, double eps) { return Det2D(p1, p2, p3) < eps; }

bool BoundaryDoesntCollideChk(TriPoint &p1, TriPoint &p2, TriPoint &p3, double eps) { return Det2D(p1, p2, p3) <= eps; }

bool TriTri2D(TriPoint *t1, TriPoint *t2, double eps = 0.0, bool allowReversed = false, bool onBoundary = true) { //Trangles must be expressed anti-clockwise CheckTriWinding(t1[0], t1[1], t1[2], allowReversed); CheckTriWinding(t2[0], t2[1], t2[2], allowReversed);

bool (*chkEdge)(TriPoint &, TriPoint &, TriPoint &, double) = NULL; if(onBoundary) //Points on the boundary are considered as colliding chkEdge = BoundaryCollideChk; else //Points on the boundary are not considered as colliding chkEdge = BoundaryDoesntCollideChk;

//For edge E of trangle 1, for(int i=0; i<3; i++) { int j=(i+1)%3;

//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(t1[i], t1[j], t2[0], eps) && chkEdge(t1[i], t1[j], t2[1], eps) && chkEdge(t1[i], t1[j], t2[2], eps)) return false; }

//For edge E of trangle 2, for(int i=0; i<3; i++) { int j=(i+1)%3;

//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(t2[i], t2[j], t1[0], eps) && chkEdge(t2[i], t2[j], t1[1], eps) && chkEdge(t2[i], t2[j], t1[2], eps)) return false; }

//The triangles collide return true; }

int main() { {TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,5)}; TriPoint t2[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,6)}; cout << TriTri2D(t1, t2) << "," << true << endl;}

{TriPoint t1[] = {TriPoint(0,0),TriPoint(0,5),TriPoint(5,0)}; TriPoint t2[] = {TriPoint(0,0),TriPoint(0,5),TriPoint(5,0)}; cout << TriTri2D(t1, t2, 0.0, true) << "," << true << endl;}

{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,5)}; TriPoint t2[] = {TriPoint(-10,0),TriPoint(-5,0),TriPoint(-1,6)}; cout << TriTri2D(t1, t2) << "," << false << endl;}

{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(2.5,5)}; TriPoint t2[] = {TriPoint(0,4),TriPoint(2.5,-1),TriPoint(5,4)}; cout << TriTri2D(t1, t2) << "," << true << endl;}

{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,1),TriPoint(0,2)}; TriPoint t2[] = {TriPoint(2,1),TriPoint(3,0),TriPoint(3,2)}; cout << TriTri2D(t1, t2) << "," << false << endl;}

{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,1),TriPoint(0,2)}; TriPoint t2[] = {TriPoint(2,1),TriPoint(3,-2),TriPoint(3,4)}; cout << TriTri2D(t1, t2) << "," << false << endl;}

//Barely touching {TriPoint t1[] = {TriPoint(0,0),TriPoint(1,0),TriPoint(0,1)}; TriPoint t2[] = {TriPoint(1,0),TriPoint(2,0),TriPoint(1,1)}; cout << TriTri2D(t1, t2, 0.0, false, true) << "," << true << endl;}

//Barely touching {TriPoint t1[] = {TriPoint(0,0),TriPoint(1,0),TriPoint(0,1)}; TriPoint t2[] = {TriPoint(1,0),TriPoint(2,0),TriPoint(1,1)}; cout << TriTri2D(t1, t2, 0.0, false, false) << "," << false << endl;}

}</lang>

Output:

1,1
1,1
0,0
1,1
0,0
0,0
1,1
0,0

Python

Using numpy:

<lang python>from __future__ import print_function 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)</lang>

Output:

True True
True True
False False
True True
False False
False False
True True
/False False

Using shapely:

<lang python>from __future__ import print_function from shapely.geometry import Polygon

def PolyOverlaps(poly1, poly2): poly1s = Polygon(poly1) poly2s = Polygon(poly2) return poly1s.intersects(poly2s)

if __name__=="__main__": t1 = [[0,0],[5,0],[0,5]] t2 = [[0,0],[5,0],[0,6]] print (PolyOverlaps(t1, t2), True)

t1 = [[0,0],[0,5],[5,0]] t2 = [[0,0],[0,6],[5,0]] print (PolyOverlaps(t1, t2), True)

t1 = [[0,0],[5,0],[0,5]] t2 = [[-10,0],[-5,0],[-1,6]] print (PolyOverlaps(t1, t2), False)

t1 = [[0,0],[5,0],[2.5,5]] t2 = [[0,4],[2.5,-1],[5,4]] print (PolyOverlaps(t1, t2), True)

t1 = [[0,0],[1,1],[0,2]] t2 = [[2,1],[3,0],[3,2]] print (PolyOverlaps(t1, t2), False)

t1 = [[0,0],[1,1],[0,2]] t2 = [[2,1],[3,-2],[3,4]] print (PolyOverlaps(t1, t2), False)

#Barely touching t1 = [[0,0],[1,0],[0,1]] t2 = [[1,0],[2,0],[1,1]] print (PolyOverlaps(t1, t2), "?")</lang>

Output:

True True
True True
False False
True True
False False
False False
True ?

REXX

<lang> Signal On Halt

 Signal On Novalue
 Signal On Syntax

oid='trio.txt'; 'erase' oid

Call trio '0 0 5 0 0 5 0 0 5 0 0 6 ' Call trio '0 0 0 5 5 0 0 0 0 5 5 0 ' Call trio '0 0 5 0 0 5 -10 0 -5 0 -1 6 ' Call trio '0 0 5 0 2.5 5 0 4 2.5 -1 5 4' Call trio '0 0 1 1 0 2 2 1 3 0 3 2 ' Call trio '0 0 1 1 0 2 2 1 3 -2 3 4 ' Call trio '0 0 1 0 0 1 1 0 2 0 1 1 ' Call trio '1 0 3 0 2 2 1 3 3 3 2 5 ' Call trio '1 0 3 0 2 2 1 3 3 3 2 2 ' Call trio '0 0 2 0 2 2 3 3 5 3 5 5 ' Exit

trio: /*---------------------------------------------------------------------

Determine if two triangles overlap
--------------------------------------------------------------------*/

parse Arg tlist Parse Arg pax pay pbx pby pcx pcy pdx pdy pex pey pfx pfy

abc=subword(tlist,1,6) def=subword(tlist,7,6)

Do i=1 To 3

 s.i=subword(abc abc,i*2-1,4)
 t.i=subword(def def,i*2-1,4)
 End

abc_= def_=

Do i=1 To 3

 abc.i=subword(abc,i*2-1,2)
 def.i=subword(def,i*2-1,2)
 Parse Var abc.i x y; abc_=abc_ '('||x','y')'
 Parse Var def.i x y; def_=def_ '('||x','y')'
 End

Call o 'abc_='abc_ Call o 'def_='def_

over=0

 Do i=1 To 3
   Do j=1 To 3
     If ssx(s.i t.j) Then Do
       over=1
       Leave
       End
     End
   End

If over=0 Then Do

 Do ii=1 To 3 Until over
   Call o 'ii='ii 'def.'ii'='def.ii 'abc='abc
   Call o '    '  'abc.'ii'='abc.ii 'def='def
   Select
     When in_tri(def.ii,abc) Then over=1
     When in_tri(abc.ii,def) Then over=1
     Otherwise Nop
     End
   End
 End

If over=0 Then rw='dont ' Else rw=

Say 'Triangles' point(pax,pay) point(pbx,pby) point(pcx,pcy),

         'and' point(pdx,pdy) point(pex,pey) point(pfx,pfy) rw'overlap'

Say Return

ssx: Procedure Expose oid /*---------------------------------------------------------------------

Intersection of 2 line segments
--------------------------------------------------------------------*/

Parse Arg xa ya xb yb xc yc xd yd d=ggx(xa ya xb yb xc yc xd yd) Call o d Select

 When d='-' Then res=0
 When d='I' Then Do
   If xa<>xb Then Do
     xab_min=min(xa,xb)
     xcd_min=min(xc,xd)
     xab_max=max(xa,xb)
     xcd_max=max(xc,xd)
     If xab_min>xcd_max |,
        xcd_min>xab_max Then
       res=0
     Else Do
       res=1
       x='*'
       y=ya
       End
     End
   Else Do
     yab_min=min(ya,yb)
     ycd_min=min(yc,yd)
     yab_max=max(ya,yb)
     ycd_max=max(yc,yd)
     If yab_min>ycd_max |,
        ycd_min>yab_max Then
       res=0
     Else Do
       res=1
       x='xa'
       y='*'
       End
     End
   End
 Otherwise Do
   Parse Var d x y
   res=is_between(xa,x,xb) &,
       is_between(xc,x,xd) &,
       is_between(ya,y,yb) &,
       is_between(yc,y,yd)
   End
 End
 If xa=xc Then Do
   x=xa
   y='*'
   End
 If res=1 Then Call o 'intersection of line segments: ('||x'/'y')'

Return res

ggx: Procedure Expose oid /*---------------------------------------------------------------------

Intersection of 2 lines
--------------------------------------------------------------------*/

Parse Arg xa ya xb yb xc yc xd yd res= If xa=xb Then Do

 k1='*'
 x1=xa
 If ya=yb Then Do
   res='Points A and B are identical'
   rs='*'
   End
 End

Else Do

 k1=(yb-ya)/(xb-xa)
 d1=ya-k1*xa
 End

If xc=xd Then Do

 k2='*'
 x2=xc
 If yc=yd Then Do
   res='Points C and D are identical'
   rs='*'
   End
 End

Else Do

 k2=(yd-yc)/(xd-xc)
 d2=yc-k2*xc
 End

If res= Then Do

 If k1='*' Then Do
   If k2='*' Then Do
     If x1=x2 Then Do
       res='Lines AB and CD are identical'
       rs='I'
       End
     Else Do
       res='Lines AB and CD are parallel'
       rs='-'
       End
     End
   Else Do
     x=x1
     y=k2*x+d2
     End
   End
 Else Do
   If k2='*' Then Do
     x=x2
     y=k1*x+d1
     End
   Else Do
     If k1=k2 Then Do
       If d1=d2 Then Do
         res='Lines AB and CD are identical'
         rs='I'
         End
       Else Do
         res='Lines AB and CD are parallel'
         rs='-'
         End
       End
     Else Do
       x=(d2-d1)/(k1-k2)
       y=k1*x+d1
       End
     End
   End
 End
 If res= Then Do
   res='Intersection is ('||x'/'y')'
   rs=x y
   Call o 'line intersection' x y
   End
 Call o 'A=('xa'/'ya') B=('||xb'/'yb') C=('||xc'/'yc') D=('||xd'/'yd')' '-->' res
 Return rs

is_between: Procedure

 Parse Arg a,b,c
 Return diff_sign(b-a,b-c)

diff_sign: Procedure

 Parse Arg diff1,diff2
 Return (sign(diff1)<>sign(diff2))|(sign(diff1)=0)

o: Return lineout(oid,arg(1))

in_tri: Procedure Expose oid /*---------------------------------------------------------------------

Determine if the point (px/py) is within the given triangle
--------------------------------------------------------------------*/

Parse Arg px py,ax ay bx by cx cy abc=ax ay bx by cx cy res=0 maxx=max(ax,bx,cx) minx=min(ax,bx,cx) maxy=max(ay,by,cy) miny=min(ay,by,cy) Call mk_g 1,'A','B' Call mk_g 2,'B','C' Call mk_g 3,'C','A'

Do i=1 To 3

 Select
   When k.i='*' Then
     Call o g.i':' 'x='||x.i
   When k.i=0 Then
     Call o g.i':' 'y='d.i
   Otherwise
     Call o g.i':' 'y=' k.i'*x'dd(d.i)
   End
 End

If px>maxx|px<minx|py>maxy|py<miny Then Nop

Else Do

 kp1=k.1
 dp1=py-kp1*px
 Call o 'p1: y='kp1'*x'dd(dp1)
 If k.2='*' Then
   x12=x.2
 Else
   x12=(d.2-dp1)/(kp1-k.2)
 If k.3='*' Then
   x13=x.3
 Else
   x13=(d.3-dp1)/(kp1-k.3)
 If is_between(ax,x12,bx) Then Do
   Call o x12 px x13
   d12=x12-px
   d13=x13-px
   Call o d12 d13
   res=res|diff_sign(d12,d13)
   End
 If k.2='*' Then Do
   x21=x.2
   x23=x.2
    End
 Else Do
   kp2=k.2
   dp2=py-kp2*px
   Call o 'p2: y='kp2'*x'dd(dp2)
   If k.1='*' Then
     x21=x.1
   Else
     x21=(d.1-dp2)/(kp2-k.1)
   If k.3='*' Then
     x23=x.3
   Else
     x23=(d.3-dp2)/(kp2-k.3)
   End
 If is_between(bx,x21,ax) Then Do
   Call o x21 px x23
   d21=x21-px
   d23=x23-px
   Call o d21 d23
   res=res|diff_sign(d21,d23)
   End
 kp3=k.3
 dp3=py-kp3*px
 Call o 'p3: y='kp3'*x'dd(dp3)
 If k.2='*' Then
   x32=x.2
 Else
   x32=(d.2-dp3)/(kp3-k.2)
 x31=(d.1-dp3)/(kp3-k.1)
 If is_between(cx,x32,bx) Then Do
   Call o x31 px x32
   d31=x31-px
   d32=x32-px
   Call o d31 d32
   res=res|diff_sign(d31,d32)
   End
 End

If res=1 Then rr=' '

        Else rr=' not '

Call o 'P ('px','py') is'rr'in' abc Return res

mk_g: Parse Arg g,a,b g.g='('a','||b')' If value(a||'x')=value(b||'x') Then Do

 k.g='*'
 x.g=value(a||'x')
 End

Else Do

 k.g=(value(b||'y')-value(a||'y'))/(value(b||'x')-value(a||'x'))
 d.g=value(a||'y')-k.g*value(a||'x')
 End

Return

dd: Procedure

 Parse Arg dd
 Select
   When dd=0 Then dd=
   When dd<0 Then dd=dd
   Otherwise      dd='+'dd
   End
 Return dd

point: Return '('arg(1)','arg(2)')'

Novalue:

 Say 'Novalue raised in line' sigl
 Say sourceline(sigl)
 Say 'Variable' condition('D')
 Signal lookaround

Syntax:

 Say 'Syntax raised in line' sigl
 Say sourceline(sigl)
 Say 'rc='rc '('errortext(rc)')'

halt: lookaround:

 If fore() Then Do
   Say 'You can look around now.'
   Trace ?R
   Nop
   End
 Exit 12</lang>

Output:

Triangles (0,0) (5,0) (0,5) and (0,0) (5,0) (0,6 ) overlap

Triangles (0,0) (0,5) (5,0) and (0,0) (0,5) (5,0 ) overlap

Triangles (0,0) (5,0) (0,5) and (-10,0) (-5,0) (-1,6 ) don't overlap

Triangles (0,0) (5,0) (2.5,5) and (0,4) (2.5,-1) (5,4) overlap

Triangles (0,0) (1,1) (0,2) and (2,1) (3,0) (3,2 ) don't overlap

Triangles (0,0) (1,1) (0,2) and (2,1) (3,-2) (3,4 ) don't overlap

Triangles (0,0) (1,0) (0,1) and (1,0) (2,0) (1,1 ) overlap

Triangles (1,0) (3,0) (2,2) and (1,3) (3,3) (2,5 ) don't overlap

Triangles (1,0) (3,0) (2,2) and (1,3) (3,3) (2,2 ) overlap

Triangles (0,0) (2,0) (2,2) and (3,3) (5,3) (5,5 ) don't overlap

zkl

Translation of: C++

<lang zkl>// 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

}</lang> <lang zkl>fcn toTri(ax,ay,bx,by,cx,cy){ //-->( (ax,ay),(bx,by),(cx,cy) )

  vm.arglist.apply("toFloat").pump(List,Void.Read)

} triangles:=T( // pairs of triangles

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

);

 // Expect: overlap, overlap (reversed), no overlap, overlap, no overlap, no overlap

foreach t1,t2 in (triangles){

  reg r, reversed=False;
  try{ r=triTri2D(t1,t2) }
  catch(AssertionError){ r=triTri2D(t1,t2,0.0,True); reversed=True; }
  print(t1,"\n",t2," ");
  println(r and "overlap" or "no overlap", reversed and " (reversed)" or "");
  println();

}

c1,c2 := toTri(0,0, 1,0, 0,1), toTri(1,0, 2,0, 1,1); println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,True)); // True println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,False)); // False</lang>

Output:

L(L(0,0),L(5,0),L(0,5))
L(L(0,0),L(5,0),L(0,6)) overlap

L(L(0,0),L(0,5),L(5,0))
L(L(0,0),L(0,5),L(5,0)) overlap (reversed)

L(L(0,0),L(5,0),L(0,5))
L(L(-10,0),L(-5,0),L(-1,6)) no overlap

L(L(0,0),L(5,0),L(2.5,5))
L(L(0,4),L(2.5,-1),L(5,4)) overlap

L(L(0,0),L(1,1),L(0,2))
L(L(2,1),L(3,0),L(3,2)) no overlap

L(L(0,0),L(1,1),L(0,2))
L(L(2,1),L(3,-2),L(3,4)) no overlap

Corner case (barely touching): True
Corner case (barely touching): False