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)


 
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
 
TYPE point
    x AS INTEGER
    y AS INTEGER
END TYPE
 
DIM coord(12, 3) AS point
 
workscreen = _NEWIMAGE(800, 800, 32)
backscreen = _NEWIMAGE(800, 800, 32)
 
SCREEN workscreen
FOR i = 1 TO 12 '12 triangles
    FOR j = 1 TO 3 'with 3 coordinates for each
        READ coord(i, j).x 'X coord
        READ coord(i, j).y 'Y coord
        FixCoord coord(i, j)
    NEXT
 
NEXT
_DELAY .5
_SCREENMOVE _MIDDLE
 
 
FOR i = 1 TO 12
    _DEST workscreen
    CLS
    _DEST backscreen
    _DONTBLEND
    CLS , 0
    PSET (coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 255, 255, 128)
    FOR j = 2 TO 3
        LINE -(coord(i, j).x, coord(i, j).y), _RGBA32(255, 255, 255, 128)
    NEXT
    LINE -(coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 255, 255, 128)
    xinside = (coord(i, 1).x + coord(i, 2).x + coord(i, 3).x) / 3
    yinside = (coord(i, 1).y + coord(i, 2).y + coord(i, 3).y) / 3
    PAINT (xinside, yinside), _RGBA32(255, 255, 255, 128)
    _BLEND
    _PUTIMAGE , backscreen, 0
    CLS , 0
    _DONTBLEND
    i = i + 1
    PSET (coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 0, 0, 128)
    FOR j = 2 TO 3
        LINE -(coord(i, j).x, coord(i, j).y), _RGBA32(255, 0, 0, 128)
    NEXT
    LINE -(coord(i, 1).x, coord(i, 1).y), _RGBA32(255, 0, 0, 128)
    xinside = (coord(i, 1).x + coord(i, 2).x + coord(i, 3).x) / 3
    yinside = (coord(i, 1).y + coord(i, 2).y + coord(i, 3).y) / 3
    PAINT (xinside, yinside), _RGBA32(255, 0, 0, 128)
    _BLEND
    _PUTIMAGE , backscreen, 0
    _DEST workscreen
    _SOURCE workscreen
    overlap = 0
    FOR x = 0 TO 999
        FOR y = 0 TO 999
            IF POINT(x, y) = _RGBA32(190, 63, 63, 255) THEN overlap = -1: GOTO overlap
        NEXT
    NEXT
    overlap:
    IF overlap THEN PRINT "OVERLAP" ELSE PRINT "NO OVERLAP"
    SLEEP
NEXT
SYSTEM
 
SUB FixCoord (p AS point)
    p.x = (10 + p.x) * 30 + 100
    p.y = (10 + p.y) * 30
END SUB
 