Determine if two triangles overlap: Difference between revisions
Determine if two triangles overlap (view source)
Revision as of 19:23, 11 October 2020
, 3 years agoadd FreeBASIC
m (→{{header|Lambdatalk}}: minor edit) |
(add FreeBASIC) |
||
Line 1,066:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|FreeBASIC}}==
<lang freebasic>#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
</lang>
{{out}}
<pre>
true
true
false
true
false
false
true
</pre>
=={{header|Go}}==
| |||