93 lines
3 KiB
Text
93 lines
3 KiB
Text
#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
|