Determine if two triangles overlap

From Rosetta Code
Determine if two triangles overlap is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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++[edit]

#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;}
 
}
Output:
1,1
1,1
0,0
1,1
0,0
0,0
1,1
0,0

Kotlin[edit]

Translation of: C++
// version 1.1.0
 
typealias Point = Pair<Double, Double>
 
data class Triangle(var p1: Point, var p2: Point, var p3: Point) {
override fun toString() = "Triangle: $p1, $p2, $p3"
}
 
fun det2D(t: Triangle): Double {
val (p1, p2, p3) = t
return p1.first * (p2.second - p3.second) +
p2.first * (p3.second - p1.second) +
p3.first * (p1.second - p2.second)
}
 
fun checkTriWinding(t: Triangle, allowReversed: Boolean) {
val detTri = det2D(t)
if (detTri < 0.0) {
if (allowReversed) {
val a = t.p3
t.p3 = t.p2
t.p2 = a
}
else throw RuntimeException("Triangle has wrong winding direction")
}
}
 
fun boundaryCollideChk(t: Triangle, eps: Double) = det2D(t) < eps
 
fun boundaryDoesntCollideChk(t: Triangle, eps: Double) = det2D(t) <= eps
 
fun triTri2D(t1: Triangle, t2: Triangle, eps: Double = 0.0,
allowReversed: Boolean = false, onBoundary: Boolean = true): Boolean {
// Triangles must be expressed anti-clockwise
checkTriWinding(t1, allowReversed)
checkTriWinding(t2, allowReversed)
// 'onBoundary' determines whether points on boundary are considered as colliding or not
val chkEdge = if (onBoundary) ::boundaryCollideChk else ::boundaryDoesntCollideChk
val lp1 = listOf(t1.p1, t1.p2, t1.p3)
val lp2 = listOf(t2.p1, t2.p2, t2.p3)
 
// for each edge E of t1
for (i in 0 until 3) {
val j = (i + 1) % 3
// Check all points of t2 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (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)) return false
}
 
// for each edge E of t2
for (i in 0 until 3) {
val j = (i + 1) % 3
// Check all points of t1 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (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)) return false
}
 
// The triangles overlap
return true
}
 
fun main(args: Array<String>) {
var t1: Triangle
var t2: Triangle
 
t1 = Triangle(0.0 to 0.0, 5.0 to 0.0, 0.0 to 5.0)
t2 = Triangle(0.0 to 0.0, 5.0 to 0.0, 0.0 to 6.0)
println("$t1 and\n$t2")
println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")
 
// need to allow reversed for this pair to avoid exception
t1 = Triangle(0.0 to 0.0, 0.0 to 5.0, 5.0 to 0.0)
t2 = t1
println("\n$t1 and\n$t2")
println(if (triTri2D(t1, t2, 0.0, true)) "overlap (reversed)" else "do not overlap")
 
t1 = Triangle(0.0 to 0.0, 5.0 to 0.0, 0.0 to 5.0)
t2 = Triangle(-10.0 to 0.0, -5.0 to 0.0, -1.0 to 6.0)
println("\n$t1 and\n$t2")
println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")
 
t1.p3 = 2.5 to 5.0
t2 = Triangle(0.0 to 4.0, 2.5 to -1.0, 5.0 to 4.0)
println("\n$t1 and\n$t2")
println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")
 
t1 = Triangle(0.0 to 0.0, 1.0 to 1.0, 0.0 to 2.0)
t2 = Triangle(2.0 to 1.0, 3.0 to 0.0, 3.0 to 2.0)
println("\n$t1 and\n$t2")
println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")
 
t2 = Triangle(2.0 to 1.0, 3.0 to -2.0, 3.0 to 4.0)
println("\n$t1 and\n$t2")
println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")
 
t1 = Triangle(0.0 to 0.0, 1.0 to 0.0, 0.0 to 1.0)
t2 = Triangle(1.0 to 0.0, 2.0 to 0.0, 1.0 to 1.1)
println("\n$t1 and\n$t2")
println("which have only a single corner in contact, if boundary points collide")
println(if (triTri2D(t1, t2)) "overlap" else "do not overlap")
 
println("\n$t1 and\n$t2")
println("which have only a single corner in contact, if boundary points do not collide")
println(if (triTri2D(t1, t2, 0.0, false, false)) "overlap" else "do not overlap")
}
Output:
Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 6.0)
overlap

Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0) and
Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0)
overlap (reversed)

Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0)
do not overlap

Triangle: (0.0, 0.0), (5.0, 0.0), (2.5, 5.0) and
Triangle: (0.0, 4.0), (2.5, -1.0), (5.0, 4.0)
overlap

Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, 0.0), (3.0, 2.0)
do not overlap

Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, -2.0), (3.0, 4.0)
do not overlap

Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points collide
overlap

Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap

ooRexx[edit]

/*--------------------------------------------------------------------
* Determine if two triangles overlap
* Fully (?) tested with integer coordinates of the 6 corners
* This was/is an exercise with ooRexx
* Removed the fraction arithmetic
*-------------------------------------------------------------------*/

Parse Version v
 
oid='trioo.txt'; 'erase' oid
Call o v
case=0
cc=0
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2'
Call trio_test '0 0 0 6 8 3 8 0 8 8 0 3'
Call trio_test '0 0 0 2 2 0 0 0 4 0 0 6'
/* The task's specified input */
Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6'
Call trio_test '0 0 0 5 5 0 0 0 0 5 5 0'
Call trio_test '0 0 5 0 0 5 -10 0 -5 0 -1 6'
Call trio_test '0 0 5 0 2.5 5 0 4 2.5 -1 5 4'
Call trio_test '0 0 1 1 0 2 2 1 3 0 3 2'
Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4'
Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1'
Exit
/* Other test cases */
Call trio_test '0 0 0 4 4 0 0 2 2 2 2 0'
Call trio_test '0 0 0 5 5 0 0 0 0 5 5 0'
Call trio_test '0 0 0 5 5 0 0 0 0 5 7 0'
Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1'
Call trio_test '0 0 1 1 0 2 2 1 3 0 3 2'
Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4'
Call trio_test '0 0 2 0 2 2 3 3 5 3 5 5'
Call trio_test '0 0 2 0 2 3 0 0 2 0 2 3'
Call trio_test '0 0 4 0 0 4 0 2 2 0 2 2'
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2'
Call trio_test '0 0 5 0 0 2 5 0 8 0 4 8'
Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6'
Call trio_test '0 0 5 0 0 5 -10 0 -5 0 -1 6'
Call trio_test '0 0 5 0 0 5 -5 0 -1 6 -3 0'
Call trio_test '0 0 5 0 3 5 0 4 3 -1 5 4'
Call trio_test '0 0 6 0 4 6 1 1 4 2 7 1'
Call trio_test '0 1 0 4 2 2 3 1 3 4 5 2'
Call trio_test '1 0 3 0 2 2 1 3 3 3 2 2'
Call trio_test '1 0 3 0 2 2 1 3 3 3 2 5'
Call trio_test '1 1 4 2 7 1 0 0 8 0 4 8'
Call trio_test '2 0 2 6 1 8 0 1 0 5 8 3'
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2'
Say case 'cases tested'
Say cc
Exit
 
trio_test:
Parse Arg tlist
cc+=1
tlist=space(tlist)
tl1=tlist  ; Call trio_t tl1
tl2=reversex(tlist)  ; Call trio_t tl2
tl3=''
tl=tlist
Do While tl<>''
Parse Var tl x y tl
tl3=tl3 y x
End
Call trio_t tl3
tl4=reversex(tl3)  ; Call trio_t tl4
tl5=subword(tl4,7) subword(tl4,1,6)  ; Call trio_t tl5
tl6=subword(tl5,7) subword(tl5,1,6)  ; Call trio_t tl6
Return
 
trio_t:
Parse Arg tlist
tlist=space(tlist)
Say tlist
case+=1
Parse Arg ax ay bx by cx cy dx dy ex ey fx fy
/*---------------------------------------------------------------------
* First build the objects needed
*--------------------------------------------------------------------*/

a=.point~new(ax,ay); b=.point~new(bx,by); c=.point~new(cx,cy)
d=.point~new(dx,dy); e=.point~new(ex,ey); f=.point~new(fx,fy)
abc=.triangle~new(a,b,c)
def=.triangle~new(d,e,f)
Call o 'Triangle: ABC:' abc ,1
Call o 'Edges of ABC:'; Do i=1 To 3; Call o ' 'abc~edge(i); End
Call o 'Triangle: DEF:' def ,1
Call o 'Edges of DEF:'; Do i=1 To 3; Call o ' 'def~edge(i); End
pixl=' '
Do i=1 To 3
pixl=pixl abc~draw(i,'O')
pixl=pixl def~draw(i,'*')
End
res=0
fc=0
touch=0
bordl=''
Do i=1 To 3
p1=abc~point(i)
p2=def~point(i)
Do j=1 To 3
e1=abc~edge(j)
e2=def~edge(j)
If e1~contains(p2) Then Do
Call o e1 'contains' p2
ps=p2~string
If wordpos(ps,bordl)=0 Then Do
bordl=bordl ps
touch+=1
End
End
Else
Call o e1 'does not contain' p2 i j
If e2~contains(p1) Then Do
Call o e2 'contains' p1
ps=p1~string
If wordpos(ps,bordl)=0 Then Do
bordl=bordl ps
touch+=1
End
End
Else
Call o e2 'does not contain' p1
End
End
 
wb=words(bordl) /* how many of them? */
If wb>0 Then
Call o 'Corner(s) that touch the other triangle:' bordl,1
 
/*---------------------------------------------------------------------
* How many of them are corners of both triangles
*--------------------------------------------------------------------*/

m=0
cmatch=''
do i=1 To 3
If wordpos(abc~point(i),bordl)>0 &,
wordpos(abc~point(i),def)>0 Then Do
cmatch=cmatch abc~point(i)
m+=1
End
End
 
/*---------------------------------------------------------------------
* With two or three touching corners we show the result and return
*--------------------------------------------------------------------*/

Select
When wb=3 Then Do /* all three touch */
Call draw(pixl)
Select
When m=3 Then
Call o 'Triangles are identical',1
When m=2 Then
Call o 'Triangles have an edge in common:' cmatch,1
Otherwise
Call o 'Triangles overlap and touch on' bordl,1
End
Call o '',1
-- Pull .
Return
End
When wb=2 Then Do /* two of them match */
Call draw(pixl)
If m=2 Then
Call o 'Triangles have an edge in common:' cmatch,1
Else
Call o 'Triangles overlap and touch on' bordl,1
Call o ''
-- Pull .
Return
End
When wb=1 Then Do /* one of them matches */
Call o 'Triangles touch on' bordl,1 /* other parts may overlap */
Call o ' we analyze further',1
End
Otherwise /* we know nothing yet */
Nop
End
 
/*---------------------------------------------------------------------
* Now we look for corners of abc that are within the triangle def
*--------------------------------------------------------------------*/

in_def=0
Do i=1 To 3
p=abc~point(i)
Call o 'p ='p
Call o 'def='def
If def~contains(p) &,
wordpos(p,bordl)=0 Then Do
Call o def 'contains' p
in_def+=1
End
End
 
If in_def=3 Then Do
Call o abc 'is fully contained in' def,1
Call o '',1
Call draw(pixl)
fc=1
End
res=(in_def>0)
/*---------------------------------------------------------------------
* Now we look for corners of def that are within the triangle abc
*--------------------------------------------------------------------*/

If res=0 Then Do
in_abc=0
If res=0 Then Do
Do i=1 To 3
p=def~point(i)
Call o 'p ='p
Call o 'def='def
If abc~contains(p) &,
wordpos(p,bordl)=0 Then Do
Call o abc 'contains' p
in_abc+=1
End
End
End
If in_abc=3 Then Do
Call o def 'is fully contained in' abc,1
Call o '',1
Call draw(pixl)
fc=1
End
res=(in_abc>0)
 
End
 
/*---------------------------------------------------------------------
* Now we check if some edge of abc crosses any edge of def
*--------------------------------------------------------------------*/

If res=0 Then Do
Do i=1 To 3
Do j=1 To 3
e1=abc~edge(i); Call o 'e1='e1
e2=def~edge(j); Call o 'e2='e2
Call o 'crossing???'
res=e1~crosses(e2)
If res Then Do
End
If res Then
Call o 'edges cross'
Else
Call o 'edges don''t cross'
End
End
End
 
If fc=0 Then Do /* no fully contained */
Call draw(pixl)
If res=0 Then /* no overlap */
If wb=1 Then /* but one touching corner */
call o abc 'and' def 'don''t overlap but touch on' bordl,1
Else
call o abc 'and' def 'don''t overlap',1
Else /* overlap */
If wb>0 Then /* one touching corner */
call o abc 'and' def 'overlap and touch on' bordl,1
Else
call o abc 'and' def 'overlap',1
Call o '',1
-- Pull .
End
Return
 
/*---------------------------------------------------------------------
* And here are all the classes and methods needed:
* point init, x, y, string
* triangle init, point, edge, contains, string
* edge init, p1, p2, kdx, contains, crosses, string
*--------------------------------------------------------------------*/

 
::class point public
::attribute x
::attribute y
::method init
expose x y
use arg x,y
::method string
expose x y
return "("||x","y")"
 
::class triangle public
::method init
expose point edge
use arg p1,p2,p3
point=.array~new
point[1]=p1
point[2]=p2
point[3]=p3
edge=.array~new
Do i=1 To 3
ia=i+1; If ia=4 Then ia=1
edge[i]=.edge~new(point[i],point[ia])
End
::method point
expose point
use arg n
Return point[n]
::method edge
expose edge
use arg n
Return edge[n]
::method contains
expose point edge
use arg pp
Call o self
Call o 'pp='pp
xmin=1.e9
ymin=1.e9
xmax=-1.e9
ymax=-1.e9
Do i=1 To 3
e=edge[i]
Parse Value e~kdx With ka.i da.i xa.i
Call o show_g(ka.i,da.i,xa.i)
p1=e~p1
p2=e~p2
xmin=min(xmin,p1~x,p2~x)
xmax=max(xmax,p1~x,p2~x)
ymin=min(ymin,p1~y,p2~y)
ymax=max(ymax,p1~y,p2~y)
End
If pp~x<xmin|pp~x>xmax|pp~y<ymin|pp~y>ymax Then
res=0
Else Do
e=edge[1]
e2=edge[2]
p1=e2~p1
p2=e2~p2
Call o 'e:' e
Select
When ka.1='*' Then Do
y2=ka.2*pp~x+da.2
y3=ka.3*pp~x+da.3
res=between(y2,pp~y,y3)
End
When ka.2='*' Then Do
y2=ka.1*pp~x+da.1
res=between(p1~y,y2,p2~y)
End
Otherwise Do
dap=pp~y-ka.1*pp~x
If ka.3='*' Then
x3=xa.3
Else
x3=(da.3-dap)/(ka.1-ka.3)
x2=(da.2-dap)/(ka.1-ka.2)
res=between(x2,pp~x,x3)
End
End
End
Return res
::method string
expose point
ol=''
Do p over point
ol=ol p~string
End
return ol
::method draw
expose point
Use Arg i,c
p=self~point(i)
Return p~x p~y c
::class edge public
::method init
expose edge p1 p2
use arg p1,p2
edge=.array~new
edge[1]=p1
edge[2]=p2
::method p1
expose edge p1 p2
return p1
::method p2
expose edge p1 p2
return p2
::method kdx
expose edge p1 p2
x1=p1~x
y1=p1~y
x2=p2~x
y2=p2~y
If x1=x2 Then Do
Parse Value '*' '-' x1 With ka da xa
Call o show_g(ka,da,xa)
End
Else Do
ka=(y2-y1)/(x2-x1)
da=y2-ka*x2
xa='*'
End
Return ka da xa
::method contains
Use Arg p
p1=self~p1
p2=self~p2
parse Value self~kdx With k d x
If k='*' Then Do
res=(p~x=p1~x)&between(p1~y,p~y,p2~y,'I')
End
Else Do
ey=k*p~x+d
res=(ey=p~y)&between(p1~x,p~x,p2~x,'I')
End
If res Then Call o self 'contains' p
Else Call o self 'does not contain' p
Return res
::method crosses
expose p1 p2
Use Arg e
q1=e~p1
q2=e~p2
Call o 'Test if' e 'crosses' self
Call o self~kdx
Call o e~kdx
Parse Value self~kdx With ka da xa; Call o ka da xa
Call o show_g(ka,da,xa)
Parse Value e~kdx With kb db xb; Call o kb db xb
Call o show_g(kb,db,xb)
Call o 'ka='ka
Call o 'kb='kb
Select
When ka='*' Then Do
If kb='*' Then Do
res=(xa=xb)
End
Else Do
Call o 'kb='kb 'xa='||xa 'db='db
yy=kb*xa+db
res=between(q1~y,yy,q2~y)
End
End
When kb='*' Then Do
yy=ka*xb+da
res=between(p1~y,yy,p2~y)
End
When ka=kb Then Do
If da=db Then Do
If min(p1~x,p2~x)>max(q1~x,q2~x) |,
min(q1~x,q2~x)>max(p1~x,p2~x) Then
res=0
Else Do
res=1
End
End
Else
res=0
End
Otherwise Do
x=(db-da)/(ka-kb)
y=ka*x+da
Call o 'cross:' x y
res=between(p1~x,x,p2~x)
End
End
Return res
::method string
expose edge p1 p2
ol=p1~string'-'p2~string
return ol
 
::routine between /* check if a number is between two others */
Use Arg a,x,b,inc
Call o 'between:' a x b
Parse Var a anom '/' adenom
Parse Var x xnom '/' xdenom
Parse Var b bnom '/' bdenom
If adenom='' Then adenom=1
If xdenom='' Then xdenom=1
If bdenom='' Then bdenom=1
aa=anom*xdenom*bdenom
xx=xnom*adenom*bdenom
bb=bnom*xdenom*adenom
If inc='I' Then
res=sign(xx-aa)<>sign(xx-bb)
Else
res=sign(xx-aa)<>sign(xx-bb) & (xx-aa)*(xx-bb)<>0
Call o a x b 'res='res
Return res
 
::routine show_g /* show a straight line's forula */
/*---------------------------------------------------------------------
* given slope, y-distance, and (special) x-value
* compute y=k*x+d or, if a vertical line, k='*'; x=c
*--------------------------------------------------------------------*/

Use Arg k,d,x
Select
When k='*' Then res='x='||x /* vertical line */
When k=0 Then res='y='d /* horizontal line */
Otherwise Do /* ordinary line */
Select
When k=1 Then res='y=x'dd(d)
When k=-1 Then res='y=-x'dd(d)
Otherwise res='y='k'*x'dd(d)
End
End
End
Return res
 
::routine dd /* prepare a displacement for presenting it in show_g */
/*---------------------------------------------------------------------
* prepare y-distance for display
*--------------------------------------------------------------------*/

Use Arg dd
Select
When dd=0 Then dd='' /* omit dd if it's zero */
When dd<0 Then dd=dd /* use dd as is (-value) */
Otherwise dd='+'dd /* prepend '+' to positive dd */
End
Return dd
 
::routine o /* debug output */
Use Arg txt,say
If say=1 Then
Say txt
oid='trioo.txt'
Return lineout(oid,txt)
 
::routine draw
Use Arg pixl
Return /* remove to see the triangle corners */
Say 'pixl='pixl
pix.=' '
Do While pixl<>''
Parse Var pixl x y c pixl
x=2*x+16; y=2*y+4
If pix.x.y=' ' Then
pix.x.y=c
Else
pix.x.y='+'
End
Do j= 20 To 0 By -1
ol=''
Do i=0 To 40
ol=ol||pix.i.j
End
Say ol
End
Return
::routine reversex
Use Arg list
n=words(list)
res=word(list,n)
Do i=n-1 to 1 By -1
res=res word(list,i)
End
Return res
Output:
0 0 4 0 0 4 1 1 2 1 1 2
Triangle: ABC:  (0,0) (4,0) (0,4)
Triangle: DEF:  (1,1) (2,1) (1,2)
 (1,1) (2,1) (1,2) is fully contained in  (0,0) (4,0) (0,4)

2 1 1 2 1 1 4 0 0 4 0 0
Triangle: ABC:  (2,1) (1,2) (1,1)
Triangle: DEF:  (4,0) (0,4) (0,0)
 (2,1) (1,2) (1,1) is fully contained in  (4,0) (0,4) (0,0)

1 2 2 1 1 1 0 4 4 0 0 0
Triangle: ABC:  (1,2) (2,1) (1,1)
Triangle: DEF:  (0,4) (4,0) (0,0)
 (1,2) (2,1) (1,1) is fully contained in  (0,4) (4,0) (0,0)

0 0 0 4 4 0 1 1 1 2 2 1
Triangle: ABC:  (0,0) (0,4) (4,0)
Triangle: DEF:  (1,1) (1,2) (2,1)
 (1,1) (1,2) (2,1) is fully contained in  (0,0) (0,4) (4,0)

1 1 1 2 2 1 0 0 0 4 4 0
Triangle: ABC:  (1,1) (1,2) (2,1)
Triangle: DEF:  (0,0) (0,4) (4,0)
 (1,1) (1,2) (2,1) is fully contained in  (0,0) (0,4) (4,0)

0 0 0 4 4 0 1 1 1 2 2 1
Triangle: ABC:  (0,0) (0,4) (4,0)
Triangle: DEF:  (1,1) (1,2) (2,1)
 (1,1) (1,2) (2,1) is fully contained in  (0,0) (0,4) (4,0)

0 0 0 6 8 3 8 0 8 8 0 3
Triangle: ABC:  (0,0) (0,6) (8,3)
Triangle: DEF:  (8,0) (8,8) (0,3)
Corner(s) that touch the other triangle:  (0,3) (8,3)
Triangles overlap and touch on  (0,3) (8,3)
3 0 8 8 0 8 3 8 6 0 0 0
Triangle: ABC:  (3,0) (8,8) (0,8)
Triangle: DEF:  (3,8) (6,0) (0,0)
Corner(s) that touch the other triangle:  (3,8) (3,0)
Triangles overlap and touch on  (3,8) (3,0)
0 3 8 8 8 0 8 3 0 6 0 0
Triangle: ABC:  (0,3) (8,8) (8,0)
Triangle: DEF:  (8,3) (0,6) (0,0)
Corner(s) that touch the other triangle:  (8,3) (0,3)
Triangles overlap and touch on  (8,3) (0,3)
0 0 6 0 3 8 0 8 8 8 3 0
Triangle: ABC:  (0,0) (6,0) (3,8)
Triangle: DEF:  (0,8) (8,8) (3,0)
Corner(s) that touch the other triangle:  (3,0) (3,8)
Triangles overlap and touch on  (3,0) (3,8)
0 8 8 8 3 0 0 0 6 0 3 8
Triangle: ABC:  (0,8) (8,8) (3,0)
Triangle: DEF:  (0,0) (6,0) (3,8)
Corner(s) that touch the other triangle:  (3,8) (3,0)
Triangles overlap and touch on  (3,8) (3,0)
0 0 6 0 3 8 0 8 8 8 3 0
Triangle: ABC:  (0,0) (6,0) (3,8)
Triangle: DEF:  (0,8) (8,8) (3,0)
Corner(s) that touch the other triangle:  (3,0) (3,8)
Triangles overlap and touch on  (3,0) (3,8)
0 0 0 2 2 0 0 0 4 0 0 6
Triangle: ABC:  (0,0) (0,2) (2,0)
Triangle: DEF:  (0,0) (4,0) (0,6)
Corner(s) that touch the other triangle:  (0,0) (0,2) (2,0)
Triangles overlap and touch on  (0,0) (0,2) (2,0)

6 0 0 4 0 0 0 2 2 0 0 0
Triangle: ABC:  (6,0) (0,4) (0,0)
Triangle: DEF:  (0,2) (2,0) (0,0)
Corner(s) that touch the other triangle:  (0,2) (2,0) (0,0)
Triangles overlap and touch on  (0,2) (2,0) (0,0)

0 6 4 0 0 0 2 0 0 2 0 0
Triangle: ABC:  (0,6) (4,0) (0,0)
Triangle: DEF:  (2,0) (0,2) (0,0)
Corner(s) that touch the other triangle:  (2,0) (0,2) (0,0)
Triangles overlap and touch on  (2,0) (0,2) (0,0)

0 0 2 0 0 2 0 0 0 4 6 0
Triangle: ABC:  (0,0) (2,0) (0,2)
Triangle: DEF:  (0,0) (0,4) (6,0)
Corner(s) that touch the other triangle:  (0,0) (2,0) (0,2)
Triangles overlap and touch on  (0,0) (2,0) (0,2)

0 0 0 4 6 0 0 0 2 0 0 2
Triangle: ABC:  (0,0) (0,4) (6,0)
Triangle: DEF:  (0,0) (2,0) (0,2)
Corner(s) that touch the other triangle:  (0,0) (2,0) (0,2)
Triangles overlap and touch on  (0,0) (2,0) (0,2)

0 0 2 0 0 2 0 0 0 4 6 0
Triangle: ABC:  (0,0) (2,0) (0,2)
Triangle: DEF:  (0,0) (0,4) (6,0)
Corner(s) that touch the other triangle:  (0,0) (2,0) (0,2)
Triangles overlap and touch on  (0,0) (2,0) (0,2)

0 0 5 0 0 5 0 0 5 0 0 6
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,6)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles have an edge in common:  (0,0) (5,0)

6 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC:  (6,0) (0,5) (0,0)
Triangle: DEF:  (5,0) (0,5) (0,0)
Corner(s) that touch the other triangle:  (5,0) (0,5) (0,0)
Triangles have an edge in common:  (0,5) (0,0)

0 6 5 0 0 0 0 5 5 0 0 0
Triangle: ABC:  (0,6) (5,0) (0,0)
Triangle: DEF:  (0,5) (5,0) (0,0)
Corner(s) that touch the other triangle:  (0,5) (5,0) (0,0)
Triangles have an edge in common:  (5,0) (0,0)

0 0 0 5 5 0 0 0 0 5 6 0
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,0) (0,5) (6,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles have an edge in common:  (0,0) (0,5)

0 0 0 5 6 0 0 0 0 5 5 0
Triangle: ABC:  (0,0) (0,5) (6,0)
Triangle: DEF:  (0,0) (0,5) (5,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles have an edge in common:  (0,0) (0,5)

0 0 0 5 5 0 0 0 0 5 6 0
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,0) (0,5) (6,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles have an edge in common:  (0,0) (0,5)

0 0 0 5 5 0 0 0 0 5 5 0
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,0) (0,5) (5,0)
Corner(s) that touch the other triangle:  (0,0) (0,5) (5,0)
Triangles are identical

0 5 5 0 0 0 0 5 5 0 0 0
Triangle: ABC:  (0,5) (5,0) (0,0)
Triangle: DEF:  (0,5) (5,0) (0,0)
Corner(s) that touch the other triangle:  (0,5) (5,0) (0,0)
Triangles are identical

5 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC:  (5,0) (0,5) (0,0)
Triangle: DEF:  (5,0) (0,5) (0,0)
Corner(s) that touch the other triangle:  (5,0) (0,5) (0,0)
Triangles are identical

0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,5)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles are identical

0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,5)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles are identical

0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (0,0) (5,0) (0,5)
Corner(s) that touch the other triangle:  (0,0) (5,0) (0,5)
Triangles are identical

0 0 5 0 0 5 -10 0 -5 0 -1 6
Triangle: ABC:  (0,0) (5,0) (0,5)
Triangle: DEF:  (-10,0) (-5,0) (-1,6)
 (0,0) (5,0) (0,5) and  (-10,0) (-5,0) (-1,6) don't overlap

6 -1 0 -5 0 -10 5 0 0 5 0 0
Triangle: ABC:  (6,-1) (0,-5) (0,-10)
Triangle: DEF:  (5,0) (0,5) (0,0)
 (6,-1) (0,-5) (0,-10) and  (5,0) (0,5) (0,0) don't overlap

-1 6 -5 0 -10 0 0 5 5 0 0 0
Triangle: ABC:  (-1,6) (-5,0) (-10,0)
Triangle: DEF:  (0,5) (5,0) (0,0)
 (-1,6) (-5,0) (-10,0) and  (0,5) (5,0) (0,0) don't overlap

0 0 0 5 5 0 0 -10 0 -5 6 -1
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,-10) (0,-5) (6,-1)
 (0,0) (0,5) (5,0) and  (0,-10) (0,-5) (6,-1) don't overlap

0 -10 0 -5 6 -1 0 0 0 5 5 0
Triangle: ABC:  (0,-10) (0,-5) (6,-1)
Triangle: DEF:  (0,0) (0,5) (5,0)
 (0,-10) (0,-5) (6,-1) and  (0,0) (0,5) (5,0) don't overlap

0 0 0 5 5 0 0 -10 0 -5 6 -1
Triangle: ABC:  (0,0) (0,5) (5,0)
Triangle: DEF:  (0,-10) (0,-5) (6,-1)
 (0,0) (0,5) (5,0) and  (0,-10) (0,-5) (6,-1) don't overlap

0 0 5 0 2.5 5 0 4 2.5 -1 5 4
Triangle: ABC:  (0,0) (5,0) (2.5,5)
Triangle: DEF:  (0,4) (2.5,-1) (5,4)
 (0,0) (5,0) (2.5,5) and  (0,4) (2.5,-1) (5,4) overlap

4 5 -1 2.5 4 0 5 2.5 0 5 0 0
Triangle: ABC:  (4,5) (-1,2.5) (4,0)
Triangle: DEF:  (5,2.5) (0,5) (0,0)
 (4,5) (-1,2.5) (4,0) and  (5,2.5) (0,5) (0,0) overlap

5 4 2.5 -1 0 4 2.5 5 5 0 0 0
Triangle: ABC:  (5,4) (2.5,-1) (0,4)
Triangle: DEF:  (2.5,5) (5,0) (0,0)
 (5,4) (2.5,-1) (0,4) and  (2.5,5) (5,0) (0,0) overlap

0 0 0 5 5 2.5 4 0 -1 2.5 4 5
Triangle: ABC:  (0,0) (0,5) (5,2.5)
Triangle: DEF:  (4,0) (-1,2.5) (4,5)
 (0,0) (0,5) (5,2.5) and  (4,0) (-1,2.5) (4,5) overlap

4 0 -1 2.5 4 5 0 0 0 5 5 2.5
Triangle: ABC:  (4,0) (-1,2.5) (4,5)
Triangle: DEF:  (0,0) (0,5) (5,2.5)
 (4,0) (-1,2.5) (4,5) and  (0,0) (0,5) (5,2.5) overlap

0 0 0 5 5 2.5 4 0 -1 2.5 4 5
Triangle: ABC:  (0,0) (0,5) (5,2.5)
Triangle: DEF:  (4,0) (-1,2.5) (4,5)
 (0,0) (0,5) (5,2.5) and  (4,0) (-1,2.5) (4,5) overlap

0 0 1 1 0 2 2 1 3 0 3 2
Triangle: ABC:  (0,0) (1,1) (0,2)
Triangle: DEF:  (2,1) (3,0) (3,2)
 (0,0) (1,1) (0,2) and  (2,1) (3,0) (3,2) don't overlap

2 3 0 3 1 2 2 0 1 1 0 0
Triangle: ABC:  (2,3) (0,3) (1,2)
Triangle: DEF:  (2,0) (1,1) (0,0)
 (2,3) (0,3) (1,2) and  (2,0) (1,1) (0,0) don't overlap

3 2 3 0 2 1 0 2 1 1 0 0
Triangle: ABC:  (3,2) (3,0) (2,1)
Triangle: DEF:  (0,2) (1,1) (0,0)
 (3,2) (3,0) (2,1) and  (0,2) (1,1) (0,0) don't overlap

0 0 1 1 2 0 1 2 0 3 2 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (0,3) (2,3)
 (0,0) (1,1) (2,0) and  (1,2) (0,3) (2,3) don't overlap

1 2 0 3 2 3 0 0 1 1 2 0
Triangle: ABC:  (1,2) (0,3) (2,3)
Triangle: DEF:  (0,0) (1,1) (2,0)
 (1,2) (0,3) (2,3) and  (0,0) (1,1) (2,0) don't overlap

0 0 1 1 2 0 1 2 0 3 2 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (0,3) (2,3)
 (0,0) (1,1) (2,0) and  (1,2) (0,3) (2,3) don't overlap

0 0 1 1 0 2 2 1 3 -2 3 4
Triangle: ABC:  (0,0) (1,1) (0,2)
Triangle: DEF:  (2,1) (3,-2) (3,4)
 (0,0) (1,1) (0,2) and  (2,1) (3,-2) (3,4) don't overlap

4 3 -2 3 1 2 2 0 1 1 0 0
Triangle: ABC:  (4,3) (-2,3) (1,2)
Triangle: DEF:  (2,0) (1,1) (0,0)
 (4,3) (-2,3) (1,2) and  (2,0) (1,1) (0,0) don't overlap

3 4 3 -2 2 1 0 2 1 1 0 0
Triangle: ABC:  (3,4) (3,-2) (2,1)
Triangle: DEF:  (0,2) (1,1) (0,0)
 (3,4) (3,-2) (2,1) and  (0,2) (1,1) (0,0) don't overlap

0 0 1 1 2 0 1 2 -2 3 4 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (-2,3) (4,3)
 (0,0) (1,1) (2,0) and  (1,2) (-2,3) (4,3) don't overlap

1 2 -2 3 4 3 0 0 1 1 2 0
Triangle: ABC:  (1,2) (-2,3) (4,3)
Triangle: DEF:  (0,0) (1,1) (2,0)
 (1,2) (-2,3) (4,3) and  (0,0) (1,1) (2,0) don't overlap

0 0 1 1 2 0 1 2 -2 3 4 3
Triangle: ABC:  (0,0) (1,1) (2,0)
Triangle: DEF:  (1,2) (-2,3) (4,3)
 (0,0) (1,1) (2,0) and  (1,2) (-2,3) (4,3) don't overlap

0 0 1 0 0 1 1 0 2 0 1 1
Triangle: ABC:  (0,0) (1,0) (0,1)
Triangle: DEF:  (1,0) (2,0) (1,1)
Corner(s) that touch the other triangle:  (1,0)
Triangles touch on  (1,0)
  we analyze further
 (0,0) (1,0) (0,1) and  (1,0) (2,0) (1,1) don't overlap but touch on  (1,0)

1 1 0 2 0 1 1 0 0 1 0 0
Triangle: ABC:  (1,1) (0,2) (0,1)
Triangle: DEF:  (1,0) (0,1) (0,0)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (1,1) (0,2) (0,1) and  (1,0) (0,1) (0,0) don't overlap but touch on  (0,1)

1 1 2 0 1 0 0 1 1 0 0 0
Triangle: ABC:  (1,1) (2,0) (1,0)
Triangle: DEF:  (0,1) (1,0) (0,0)
Corner(s) that touch the other triangle:  (1,0)
Triangles touch on  (1,0)
  we analyze further
 (1,1) (2,0) (1,0) and  (0,1) (1,0) (0,0) overlap and touch on  (1,0)

0 0 0 1 1 0 0 1 0 2 1 1
Triangle: ABC:  (0,0) (0,1) (1,0)
Triangle: DEF:  (0,1) (0,2) (1,1)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (0,0) (0,1) (1,0) and  (0,1) (0,2) (1,1) don't overlap but touch on  (0,1)

0 1 0 2 1 1 0 0 0 1 1 0
Triangle: ABC:  (0,1) (0,2) (1,1)
Triangle: DEF:  (0,0) (0,1) (1,0)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (0,1) (0,2) (1,1) and  (0,0) (0,1) (1,0) don't overlap but touch on  (0,1)

0 0 0 1 1 0 0 1 0 2 1 1
Triangle: ABC:  (0,0) (0,1) (1,0)
Triangle: DEF:  (0,1) (0,2) (1,1)
Corner(s) that touch the other triangle:  (0,1)
Triangles touch on  (0,1)
  we analyze further
 (0,0) (0,1) (1,0) and  (0,1) (0,2) (1,1) don't overlap but touch on  (0,1)

Python[edit]

Using numpy:

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)
Output:
True True
True True
False False
True True
False False
False False
True True
/False False

Using shapely:

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), "?")
Output:
True True
True True
False False
True True
False False
False False
True ?

REXX[edit]

Note: The triangles must be real triangles (no edge of length 0)

Signal On Halt
Signal On Novalue
Signal On Syntax
 
fid='trio.in'
oid='trio.txt'; 'erase' oid
 
 
Call trio_test '0 0 5 0 0 5 0 0 5 0 0 6'
Call trio_test '0 0 0 5 5 0 0 0 0 5 5 0'
Call trio_test '0 0 5 0 0 5 -10 0 -5 0 -1 6'
Call trio_test '0 0 5 0 2.5 5 0 4 2.5 -1 5 4'
Call trio_test '0 0 1 1 0 2 2 1 3 0 3 2'
Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4'
Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1'
 
Call trio_test '1 0 3 0 2 2 1 3 3 3 2 5'
Call trio_test '1 0 3 0 2 2 1 3 3 3 2 2'
Call trio_test '0 0 2 0 2 2 3 3 5 3 5 5'
Call trio_test '2 0 2 6 1 8 0 1 0 5 8 3'
Call trio_test '0 0 4 0 0 4 0 2 2 0 2 2'
Call trio_test '0 0 4 0 0 4 1 1 2 1 1 2'
Exit
 
trio_test:
parse Arg tlist
tlist=space(tlist)
Parse Arg ax ay bx by cx cy dx dy ex ey fx fy
 
Say 'ABC:' show_p(ax ay) show_p(bx by) show_p(cx cy)
Say 'DEF:' show_p(dx dy) show_p(ex ey) show_p(fx fy)
 
bordl=bord(tlist) /* corners that are on the other triangle's edges */
If bordl<>'' Then
Say 'Corners on the other triangle''s edges:' bordl
wb=words(bordl) /* how many of them? */
Select
When wb=3 Then Do /* all three match */
If ident(ax ay,bx by,cx cy,dx dy,ex ey,fx fy) Then
Say 'Triangles are identical'
Else
Say 'Triangles overlap'
Say ''
Return
End
When wb=2 Then Do /* two of them match */
Say 'Triangles overlap'
Say ' they have a common edge 'bordl
Say ''
Return
End
When wb=1 Then Do /* one of them match */
Say 'Triangles touch on' bordl /* other parts may overlap */
Say ' we analyze further'
End
Otherwise /* we know nothing yet */
Nop
End
 
trio_result=trio(tlist) /* any other overlap? */
 
Select
When trio_result=0 Then Do /* none whatsoever */
If wb=1 Then
Say 'Triangles touch (border case) at' show_p(bordl)
Else
Say 'Triangles don''t overlap'
End
When trio_result>0 Then /* plain overlapping case */
Say 'Triangles overlap'
End
Say ''
Return
 
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) /* corners of ABC */
def.i=subword(def,i*2-1,2) /* corners of DEF */
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 Until over
Do j=1 To 3 Until over
If ssx(s.i t.j) Then Do /* intersection of two edges */
over=1
Leave
End
End
End
 
If over=0 Then Do /* no edge intersection found */
Do ii=1 To 3 Until over /* look for first possibility */
Call o ' ' 'abc.'ii'='abc.ii 'def='def
Call o 'ii='ii 'def.'ii'='def.ii 'abc='abc
If in_tri(abc.ii,def) Then Do /* a corner of ABC is in DEF */
Say abc.ii 'is within' def
over=1
End
Else If in_tri(def.ii,abc) Then Do /* a corner of DEF is in ABC */
Say def.ii 'is within' abc
over=1
End
End
End
 
If over=0 Then rw='don''t '
Else rw=''
 
Call o 'Triangles' show_p(pax pay) show_p(pbx pby) show_p(pcx pcy),
'and' show_p(pdx pdy) show_p(pex pey) show_p(pfx pfy),
rw'overlap'
Call o ''
Return over
 
ssx: Procedure Expose oid bordl
/*---------------------------------------------------------------------
* Intersection of 2 line segments A-B and C-D
*--------------------------------------------------------------------*/

Parse Arg xa ya xb yb xc yc xd yd
 
d=ggx(xa ya xb yb xc yc xd yd)
 
Call o 'ssx:' arg(1) d
res=0
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
Select
When xa=xc & isb(xc,xb,xd)=0 Then Do; x=xa; y=ya; End
When xb=xc & isb(xc,xa,xd)=0 Then Do; x=xb; y=yb; End
When xa=xd & isb(xc,xb,xd)=0 Then Do; x=xa; y=ya; End
When xb=xd & isb(xc,xa,xd)=0 Then Do; x=xb; y=yb; End
Otherwise Do
x='*'
y=ya
End
End
Call o 'ssx:' x y
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='*'
Parse Var bordl x_bord '/' y_bord
If x=x_bord Then Do
Call o xa'/* IGNORED'
res=0
End
End
End
End
Otherwise Do
Parse Var d x y
If is_between(xa,x,xb) &,
is_between(xc,x,xd) &,
is_between(ya,y,yb) &,
is_between(yc,y,yd) Then Do
If x'/'y<>bordl Then
res=1
End
End
End
If res=1 Then Do
Say 'Intersection of line segments: ('||x'/'y')'
Parse Var bordl x_bord '/' y_bord
If x=x_bord Then Do
res=0
Call o x'/'y 'IGNORED'
End
End
Else Call o 'ssx: -'
Return res
 
ggx: Procedure Expose oid bordl
/*---------------------------------------------------------------------
* Intersection of 2 (straight) 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
 
isb: Procedure
Parse Arg a,b,c
Return sign(b-a)<>sign(b-c)
 
is_between: Procedure Expose oid
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:
/*y 'sigl='sigl */
Return lineout(oid,arg(1))
 
in_tri: Procedure Expose oid bordl
/*---------------------------------------------------------------------
* 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)
 
If px>maxx|px<minx|py>maxy|py<miny Then
Return 0
 
Parse Value mk_g(ax ay,bx by) With k.1 d.1 x.1
Parse Value mk_g(bx by,cx cy) With k.2 d.2 x.2
Parse Value mk_g(cx cy,ax ay) With k.3 d.3 x.3
/*
say 'g1:' show_g(k.1,d.1,x.1)
say 'g2:' show_g(k.2,d.2,x.2)
say 'g3:' show_g(k.3,d.3,x.3)
Say px py '-' ax ay bx by cx cy
*/

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 k.1='*' Then Do
y2=k.2*px+d.2
y3=k.3*px+d.3
If is_between(y2,py,y3) Then
res=1
End
Else Do
kp1=k.1
dp1=py-kp1*px
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(x12,px,x13) Then
res=1
End
 
If res=1 Then rr=' '
Else rr=' not '
If pos(px'/'py,bordl)>0 Then Do
ignored=' but is IGNORED'
res=0
End
Else
ignored=''
Say 'P ('px','py') is'rr'in' abc ignored
Return res
 
bord:
/*---------------------------------------------------------------------
* Look for corners of triangles that are situated
* on the edges of the other triangle
*--------------------------------------------------------------------*/

parse Arg tlist
Parse Arg pax pay pbx pby pcx pcy pdx pdy pex pey pfx pfy
bordl=''
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
 
Do i=1 To 3
i1=i+1
If i1=4 Then i1=1
Parse Value mk_g(abc.i,abc.i1) With k.1.i d.1.i x.1.i
Parse Value mk_g(def.i,def.i1) With k.2.i d.2.i x.2.i
End
Do i=1 To 3
Call o show_g(k.1.i,d.1.i,x.1.i)
End
Do i=1 To 3
Call o show_g(k.2.i,d.2.i,x.2.i)
End
 
pl=''
Do i=1 To 3
p=def.i
Do j=1 To 3
j1=j+1
If j1=4 Then j1=1
g='1.'j
If in_segment(p,abc.j,abc.j1) Then Do
pp=Translate(p,'/',' ')
If wordpos(pp,bordl)=0 Then
bordl=bordl pp
End
Call o show_p(p) show_g(k.g,d.g,x.g) '->' bordl
End
End
Call o 'Points on abc:' pl
 
pl=''
Do i=1 To 3
p=abc.i
Do j=1 To 3
j1=j+1
If j1=4 Then j1=1
g='2.'j
If in_segment(p,def.j,def.j1)Then Do
pp=Translate(p,'/',' ')
If wordpos(pp,bordl)=0 Then
bordl=bordl pp
End
Call o show_p(p) show_g(k.g,d.g,x.g) '->' bordl
End
End
Call o 'Points on def:' pl
 
Return bordl
 
in_segment: Procedure Expose g. sigl
/*---------------------------------------------------------------------
* Determine if point x/y is on the line segment ax/ay bx/by
*--------------------------------------------------------------------*/

Parse Arg x y,ax ay,bx by
Call show_p(x y) show_p(ax ay) show_p(bx by)
Parse Value mk_g(ax ay,bx by) With gk gd gx
Select
When gx<>'' Then
res=(x=gx & is_between(ay,y,by))
When gk='*' Then
res=(y=gd & is_between(ax,x,bx))
Otherwise Do
yy=gk*x+gd
res=(y=yy & is_between(ax,x,bx))
End
End
Return res
 
mk_g: Procedure Expose g.
/*---------------------------------------------------------------------
* given two points (a and b)
* compute y=k*x+d or, if a vertical line, k='*'; x=c
*--------------------------------------------------------------------*/

Parse Arg a,b /* 2 points */
Parse Var a ax ay
Parse Var b bx by
If ax=bx Then Do /* vertical line */
gk='*' /* special slope */
gx=ax /* x=ax is the equation */
gd='*' /* not required */
End
Else Do
gk=(by-ay)/(bx-ax) /* compute slope */
gd=ay-gk*ax /* compute y-distance */
gx='' /* not required */
End
Return gk gd gx
 
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)
 
show_p: Procedure
Call trace 'O'
Parse Arg x y
If pos('/',x)>0 Then
Parse Var x x '/' y
Return space('('||x'/'y')',0)
 
isb: Procedure Expose oid
Parse Arg a,b,c
Return sign(b-a)<>sign(b-c)
 
o: Call o arg(1)
Return
 
show_g: Procedure
/*---------------------------------------------------------------------
* given slope, y-distance, and (special) x-value
* compute y=k*x+d or, if a vertical line, k='*'; x=c
*--------------------------------------------------------------------*/

Parse Arg k,d,x
Select
When k='*' Then res='x='||x /* vertical line */
When k=0 Then res='y='d /* horizontal line */
Otherwise Do /* ordinary line */
Select
When k=1 Then res='y=x'dd(d)
When k=-1 Then res='y=-x'dd(d)
Otherwise res='y='k'*x'dd(d)
End
End
End
Return res
 
dd: Procedure
/*---------------------------------------------------------------------
* prepare y-distance for display
*--------------------------------------------------------------------*/

Parse Arg dd
Select
When dd=0 Then dd='' /* omit dd if it's zero */
When dd<0 Then dd=dd /* use dd as is (-value) */
Otherwise dd='+'dd /* prepend '+' to positive dd */
End
Return dd
 
ident: Procedure
/*---------------------------------------------------------------------
* Determine if the corners ABC match those of DEF (in any order)
*--------------------------------------------------------------------*/

cnt.=0
Do i=1 To 6
Parse Value Arg(i) With x y
cnt.x.y=cnt.x.y+1
End
Do i=1 To 3
Parse Value Arg(i) With x y
If cnt.x.y<>2 Then
Return 0
End
Return 1
 
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
Output:
ABC: (0/0) (5/0) (0/5)
DEF: (0/0) (5/0) (0/6)
Corners on the other triangle's edges:  0/0 5/0 0/5
Triangles overlap

ABC: (0/0) (0/5) (5/0)
DEF: (0/0) (0/5) (5/0)
Corners on the other triangle's edges:  0/0 0/5 5/0
Triangles are identical

ABC: (0/0) (5/0) (0/5)
DEF: (-10/0) (-5/0) (-1/6)
Triangles don't overlap

ABC: (0/0) (5/0) (2.5/5)
DEF: (0/4) (2.5/-1) (5/4)
Intersection of line segments: (2/0)
Triangles overlap

ABC: (0/0) (1/1) (0/2)
DEF: (2/1) (3/0) (3/2)
Triangles don't overlap

ABC: (0/0) (1/1) (0/2)
DEF: (2/1) (3/-2) (3/4)
Triangles don't overlap

ABC: (0/0) (1/0) (0/1)
DEF: (1/0) (2/0) (1/1)
Corners on the other triangle's edges:  1/0
Triangles touch on  1/0
  we analyze further
Intersection of line segments: (1/0)
P (1,0) is in 0 0 1 0 0 1  but is IGNORED
P (1,0) is in 1 0 2 0 1 1  but is IGNORED
P (1,1) is not in 0 0 1 0 0 1
Triangles touch (border case) at (1/0)

ABC: (1/0) (3/0) (2/2)
DEF: (1/3) (3/3) (2/5)
Triangles don't overlap

ABC: (1/0) (3/0) (2/2)
DEF: (1/3) (3/3) (2/2)
Corners on the other triangle's edges:  2/2
Triangles touch on  2/2
  we analyze further
P (2,2) is in 1 3 3 3 2 2  but is IGNORED
P (2,2) is in 1 0 3 0 2 2  but is IGNORED
Triangles touch (border case) at (2/2)

ABC: (0/0) (2/0) (2/2)
DEF: (3/3) (5/3) (5/5)
Triangles don't overlap

ABC: (2/0) (2/6) (1/8)
DEF: (0/1) (0/5) (8/3)
Intersection of line segments: (2/4.50)
Triangles overlap

ABC: (0/0) (4/0) (0/4)
DEF: (0/2) (2/0) (2/2)
Corners on the other triangle's edges:  0/2 2/0 2/2
Triangles overlap

ABC: (0/0) (4/0) (0/4)
DEF: (1/1) (2/1) (1/2)
P (1,1) is in 0 0 4 0 0 4
1 1 is within 0 0 4 0 0 4
Triangles overlap

zkl[edit]

Translation of: C++
// 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
}
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
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