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)


 
Here we present a rasterized version based on a single function "isInside". 
 
1) isInside
 
Given A, B, C, P is in the triangle ABC if the three cross-products 
PA^PB, PB^PC and PC^PA are of equal sign.
 
{def isInside
 {lambda {:a :b :c :p}
  {let { {:ax {car :a}} {:ay {cdr :a}}
         {:bx {car :b}} {:by {cdr :b}} 
         {:cx {car :c}} {:cy {cdr :c}} 
         {:px {car :p}} {:py {cdr :p}}
       } {let { {:w1 {- {* {- :px :ax} {- :cy :ay}}
                        {* {- :cx :ax} {- :py :ay}} }}
                {:w2 {- {* {- :px :bx} {- :ay :by}} 
                        {* {- :ax :bx} {- :py :by}} }}
                {:w3 {- {* {- :px :cx} {- :by :cy}} 
                        {* {- :bx :cx} {- :py :cy}} }}
              } {or {and {>= :w1 0} {>= :w2 0} {>= :w3 0}} 
                    {and {<  :w1 0} {<  :w2 0} {<  :w3 0}}} }}}}
-> isInside
 
2) overlapping
 
For every points in the rectangle surrounding two given triangles
we compute the number of points inside both. If it is null they don't overlap.
 
{def overlap 
 
 {def overlap.row
  {lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h :y}
     {S.map {{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :qp}
                     {if {and {isInside :p0 :p1 :p2 :qp}
                              {isInside :q0 :q1 :q2 :qp}}
                      then x else}} :p0 :p1 :p2 :q0 :q1 :q2}
     {S.map {{lambda {:y :x} {cons :x :y}} :y}
            {S.serie :w :h} }}}}
 
 {lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h}
  {S.length {S.map {overlap.row :p0 :p1 :p2 :q0 :q1 :q2 :w :h}
            {S.serie :w :h}} }}}
-> overlap
 
Given coordonnees will just be scaled to become integers, here miltiplied by 10
 
{overlap {cons 0 0} {cons 50 0} {cons 0 50}
         {cons 0 0} {cons 50 0} {cons 0 60} 0 60}          -> 1326
 
{overlap {cons 0 0} {cons 0 50} {cons 50 0}
         {cons 0 0} {cons 0 50} {cons 50 0} 0 50}          -> 1176
 
{overlap {cons 0 0} {cons 50 0} {cons 0 50}
         {cons -100 0} {cons -50 0} {cons -10 60} 100 60}  -> 0
 
{overlap {cons 0 0} {cons 50 0} {cons 25 50}
         {cons 0 40} {cons 25 -10} {cons 50 40} -10 50}    -> 831
 
{overlap {cons 0 0} {cons 10 10} {cons 0 20}
         {cons 20 10} {cons 30 0} {cons 30 20} 0 20}       -> 0
 
{overlap {cons 0 0} {cons 10 10} {cons 0 20}
         {cons 20 10} {cons 30 -20} {cons 40 40} -20 40}   -> 0
 
{overlap {cons 0 0} {cons 10 0} {cons 0 10}
         {cons 10 0} {cons 20 0} {cons 10 10} 0 20}        -> 1
 
3) plot
 
The first triangle is plotted with 1s, the second with 2s,
 the intersection with 3s, else with dots.
 
{def plot 
 {def plot.row
  {lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h :y}
   {br}{S.replace \s by in 
    {S.map {{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :qp}
                    {let { {:isinp {isInside :p0 :p1 :p2 :qp}}
                           {:isinq {isInside :q0 :q1 :q2 :qp}}
                         } {if {and :isinp :isinq} then 3
                            else {if :isnp then 1
                            else {if :isnq then 2
                            else .}}} }} :p0 :p1 :p2 :q0 :q1 :q2}
     {S.map {{lambda {:y :x} {cons :x :y}} :y}
            {S.serie :w :h} }}} }}
 {lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h}
  {S.map {plot.row :p0 :p1 :p2 :q0 :q1 :q2 :w :h}
         {S.serie :w :h}} }}
-> plot
 
{plot {cons 0 0} {cons 30 0} {cons 30 30}
      {cons 5 10} {cons 25 10} {cons 5 25} 0 30} 
-> 
 
1111111111111111111111111111111 
.111111111111111111111111111111 
..11111111111111111111111111111 
...1111111111111111111111111111 
....111111111111111111111111111 
.....11111111111111111111111111 
......1111111111111111111111111 
.......111111111111111111111111 
........11111111111111111111111 
.........1111111111111111111111 
.....22222333333333333333311111 
.....22222233333333333331111111 
.....22222223333333333311111111 
.....22222222333333333111111111 
.....22222222233333311111111111 
.....22222222223333111111111111 
.....22222222222331111111111111 
.....22222222222.11111111111111 
.....2222222222...1111111111111 
.....222222222.....111111111111 
.....2222222........11111111111 
.....222222..........1111111111 
.....22222............111111111 
.....222...............11111111 
.....22.................1111111 
.....2...................111111 
..........................11111 
...........................1111 
............................111 
.............................11 
..............................1
 