Determine if two triangles overlap: Difference between revisions
Determine if two triangles overlap (view source)
Revision as of 00:24, 25 January 2019
, 5 years ago→{{header|Modula-2}}
Line 1,428:
do not overlap
</pre>
=={{header|Lua}}==
{{trans|C++}}
<lang lua>function det2D(p1,p2,p3)
return p1.x * (p2.y - p3.y)
+ p2.x * (p3.y - p1.y)
+ p3.x * (p1.y - p2.y)
end
function checkTriWinding(p1,p2,p3,allowReversed)
local detTri = det2D(p1,p2,p3)
if detTri < 0.0 then
if allowReversed then
local t = p3
p3 = p2
p2 = t
else
error("triangle has wrong winding direction")
end
end
return nil
end
function boundaryCollideChk(p1,p2,p3,eps)
return det2D(p1,p2,p3) < eps
end
function boundaryDoesntCollideChk(p1,p2,p3,eps)
return det2D(p1,p2,p3) <= eps
end
function triTri2D(t1,t2,eps,allowReversed,onBoundary)
eps = eps or 0.0
allowReversed = allowReversed or false
onBoundary = onBoundary or true
-- triangles must be expressed anti-clockwise
checkTriWinding(t1[1], t1[2], t1[3], allowReversed)
checkTriWinding(t2[1], t2[2], t2[3], allowReversed)
local chkEdge
if onBoundary then
-- points on the boundary are considered as colliding
chkEdge = boundaryCollideChk
else
-- points on the boundary are not considered as colliding
chkEdge = boundaryDoesntCollideChk
end
-- for edge E of triangle 1
for i=0,2 do
local j = (i+1)%3
-- check all points of triangle 2 lay on the external side of the edge E.
-- If they do, the triangles do not collide
if chkEdge(t1[i+1], t1[j+1], t2[1], eps) and
chkEdge(t1[i+1], t1[j+1], t2[2], eps) and
chkEdge(t1[i+1], t1[j+1], t2[3], eps) then
return false
end
end
-- for edge E of triangle 2
for i=0,2 do
local j = (i+1)%3
-- check all points of triangle 1 lay on the external side of the edge E.
-- If they do, the triangles do not collide
if chkEdge(t2[i+1], t2[j+1], t1[1], eps) and
chkEdge(t2[i+1], t2[j+1], t1[2], eps) and
chkEdge(t2[i+1], t2[j+1], t1[3], eps) then
return false
end
end
-- the triangles collide
return true
end
function formatTri(t)
return "Triangle: ("..t[1].x..", "..t[1].y
.."), ("..t[2].x..", "..t[2].y
.."), ("..t[3].x..", "..t[3].y..")"
end
function overlap(t1,t2,eps,allowReversed,onBoundary)
if triTri2D(t1,t2,eps,allowReversed,onBoundary) then
return "overlap\n"
else
return "do not overlap\n"
end
end
-- Main
local t1 = {{x=0,y=0},{x=5,y=0},{x=0,y=5}}
local t2 = {{x=0,y=0},{x=5,y=0},{x=0,y=6}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))
t1 = {{x=0,y=0},{x=0,y=5},{x=5,y=0}}
t2 = {{x=0,y=0},{x=0,y=5},{x=5,y=0}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,true))
t1 = {{x=0,y=0},{x=5,y=0},{x=0,y=5}}
t2 = {{x=-10,y=0},{x=-5,y=0},{x=-1,y=6}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))
t1 = {{x=0,y=0},{x=5,y=0},{x=2.5,y=5}}
t2 = {{x=0,y=4},{x=2.5,y=-1},{x=5,y=4}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))
t1 = {{x=0,y=0},{x=1,y=1},{x=0,y=2}}
t2 = {{x=2,y=1},{x=3,y=0},{x=3,y=2}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))
t1 = {{x=0,y=0},{x=1,y=1},{x=0,y=2}}
t2 = {{x=2,y=1},{x=3,y=-2},{x=3,y=4}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2))
-- Barely touching
t1 = {{x=0,y=0},{x=1,y=0},{x=0,y=1}}
t2 = {{x=1,y=0},{x=2,y=0},{x=1,y=1}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,false,true))
-- Barely touching
local t1 = {{x=0,y=0},{x=1,y=0},{x=0,y=1}}
local t2 = {{x=1,y=0},{x=2,y=0},{x=1,y=1}}
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,false,false))</lang>
{{out}}
<pre>Triangle: (0, 0), (5, 0), (0, 5) and
Triangle: (0, 0), (5, 0), (0, 6)
overlap
Triangle: (0, 0), (0, 5), (5, 0) and
Triangle: (0, 0), (0, 5), (5, 0)
overlap
Triangle: (0, 0), (5, 0), (0, 5) and
Triangle: (-10, 0), (-5, 0), (-1, 6)
do not overlap
Triangle: (0, 0), (5, 0), (2.5, 5) and
Triangle: (0, 4), (2.5, -1), (5, 4)
overlap
Triangle: (0, 0), (1, 1), (0, 2) and
Triangle: (2, 1), (3, 0), (3, 2)
do not overlap
Triangle: (0, 0), (1, 1), (0, 2) and
Triangle: (2, 1), (3, -2), (3, 4)
do not overlap
Triangle: (0, 0), (1, 0), (0, 1) and
Triangle: (1, 0), (2, 0), (1, 1)
overlap
Triangle: (0, 0), (1, 0), (0, 1) and
Triangle: (1, 0), (2, 0), (1, 1)
overlap</pre>
=={{header|Modula-2}}==
| |||