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)


#macro min(x,y)
   Iif(x>y,y,x)
#endmacro
#macro max(x,y)
   Iif(x>y,x,y)
#endmacro
 
type pnt  'typedef for a point
    x as double
    y as double
end type
 
type edg  'typedef for an edge
    p1 as pnt
    p2 as pnt
end type
 
function point_in_tri( r as pnt, a as pnt, b as pnt, c as pnt ) as boolean
    'uses barycentric coordinates to determine whether point r is in the triangle defined by a, b, c
    dim as double k = ((b.y - c.y)*(a.x - c.x) + (c.x - b.x)*(a.y - c.y))
    dim as double v = ((b.y - c.y)*(r.x - c.x) + (c.x - b.x)*(r.y - c.y)) / k
    dim as double w = ((c.y - a.y)*(r.x - c.x) + (a.x - c.x)*(r.y - c.y)) / k
    dim as double z = 1 - v- w
    if v<0 or v>1 then return false
    if w<0 or w>1 then return false
    if z<0 or z>1 then return false
    return true
end function
 
function bbox_overlap( a1 as pnt, a2 as pnt, b1 as pnt, b2 as pnt) as boolean
    dim as double a1x = min(a1.x, a2.x), a1y = min(a1.y, a2.y)
    dim as double a2x = max(a1.x, a2.x), a2y = max(a1.y, a2.y)
    dim as double b1x = min(b1.x, b2.x), b1y = min(b1.y, b2.y)
    dim as double b2x = max(b1.x, b2.x), b2y = max(b1.y, b2.y)
    if a1x > b2x or b1x > a2x then return false 
    if a1y > b2y or b2y > a2y then return false 
    return true
end function
 
function ccw( a as pnt, b as pnt, c as pnt) as double
   return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
end function
 
function line_intersect( a as edg, b as edg ) as boolean
   if ccw(a.p1, a.p2, b.p1)*ccw(a.p1, a.p2, b.p2) > 0 then return false
   if ccw(b.p1, b.p2, a.p1)*ccw(b.p1, b.p2, a.p2) > 0 then return false
   if not bbox_overlap( a.p1, a.p2, b.p1, b.p2 ) then return false
   return true
end function
 
function triangle_overlap( a() as pnt, b() as pnt ) as boolean
    'if two triangles overlap then either a corner of one triangle is inside
    'the other OR an edge of one triangle intersects an edge of the other.
    dim as uinteger i, j
    dim as edg c, d
    for i = 0 to 2
        if point_in_tri( a(i), b(0), b(1), b(2) ) then return true
        if point_in_tri( b(i), a(0), a(1), a(2) ) then return true
        c.p1.x = a(i).x
        c.p1.y = a(i).y
        c.p2.x = a((i+1) mod 3).x
        c.p2.y = a((i+1) mod 3).y
        for j = 0 to 2
            d.p1.x = b(i).x
            d.p1.y = b(i).y
            d.p2.x = b((i+1) mod 3).x
            d.p2.y = b((i+1) mod 3).y
            if line_intersect( c, d ) then return true
        next j 
    next i
    return 00
end function
 
data 0,0 , 5,0 , 0,5     ,    0,0 , 5,0 , 0,6
data 0,0 , 0,5 , 5,0     ,    0,0 , 0,5 , 5,0
data 0,0 , 5,0 , 0,5     ,    -10,0 , -5,0 , -1,6
data 0,0 , 5,0 , 2.5,5   ,    0,4 , 2.5,-1 , 5,4
data 0,0 , 1,1 , 0,2     ,    2,1 , 3,0 , 3,2
data 0,0 , 1,1 , 0,2     ,    2,1 , 3,-2 , 3,4
data 0,0 , 1,0 , 0,1     ,    1,0 , 2,0 , 1,1
 
dim as uinteger t, i
dim as pnt a(0 to 2), b(0 to 2)
 
for t = 1 to 7
    for i = 0 to 2
        read a(i).x, a(i).y
    next i
    for i = 0 to 2
        read b(i).x, b(i).y
    next i
    print triangle_overlap( a(), b() )
next t
 