Determine if two triangles overlap: Difference between revisions

Content added Content deleted
(→‎{{header|Python}}: add lib header for NumPy)
Line 4,200:
Triangles overlap
</pre>
 
=={{header|Ruby}}==
{{trans|C}}
<lang ruby>require "matrix"
 
def det2D(p1, p2, p3)
return p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1])
end
 
def checkTriWinding(p1, p2, p3, allowReversed)
detTri = det2D(p1, p2, p3)
if detTri < 0.0 then
if allowReversed then
p2[0], p3[0] = p3[0], p2[0]
p2[1], p3[1] = p3[1], p2[1]
else
raise "Triangle has incorrect winding"
end
end
end
 
def boundaryCollideChk(p1, p2, p3, eps)
return det2D(p1, p2, p3) < eps
end
 
def boundaryDoesntCollideChk(p1, p2, p3, eps)
return det2D(p1, p2, p3) <= eps
end
 
def triTri2D(t1, t2, eps, allowReversed, onBoundary)
# Triangles must be expressed anti-clockwise
checkTriWinding(t1[0], t1[1], t1[2], allowReversed)
checkTriWinding(t2[0], t2[1], t2[2], allowReversed)
 
if onBoundary then
# Points on the boundary are considered as colliding
chkEdge = -> (p1, p2, p3, eps) { boundaryCollideChk(p1, p2, p3, eps) }
else
# Points on the boundary are not considered as colliding
chkEdge = -> (p1, p2, p3, eps) { boundaryDoesntCollideChk(p1, p2, p3, eps) }
end
 
# For edge E of triangle 1
for i in 0..2 do
j = (i + 1) % 3
 
# Check all points of trangle 2 lay on the external side of the edge E. If
# they do, the triangles do not collide.
if chkEdge.(t1[i], t1[j], t2[0], eps) and chkEdge.(t1[i], t1[j], t2[1], eps) and chkEdge.(t1[i], t1[j], t2[2], eps) then
return false
end
end
 
# For edge E of triangle 2
for i in 0..2 do
j = (i + 1) % 3
 
# Check all points of trangle 1 lay on the external side of the edge E. If
# they do, the triangles do not collide.
if chkEdge.(t2[i], t2[j], t1[0], eps) and chkEdge.(t2[i], t2[j], t1[1], eps) and chkEdge.(t2[i], t2[j], t1[2], eps) then
return false
end
end
 
# The triangles collide
return true
end
 
def main
t1 = [Vector[0,0], Vector[5,0], Vector[0,5]]
t2 = [Vector[0,0], Vector[5,0], Vector[0,6]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
 
t1 = [Vector[0,0], Vector[0,5], Vector[5,0]]
t2 = [Vector[0,0], Vector[0,5], Vector[5,0]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, true, true)]
 
t1 = [Vector[ 0,0], Vector[ 5,0], Vector[ 0,5]]
t2 = [Vector[-10,0], Vector[-5,0], Vector[-1,6]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
 
t1 = [Vector[0,0], Vector[ 5, 0], Vector[2.5,5]]
t2 = [Vector[0,4], Vector[2.5,-1], Vector[ 5,4]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
 
t1 = [Vector[0,0], Vector[1,1], Vector[0,2]]
t2 = [Vector[2,1], Vector[3,0], Vector[3,2]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
 
t1 = [Vector[0,0], Vector[1, 1], Vector[0,2]]
t2 = [Vector[2,1], Vector[3,-2], Vector[3,4]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
 
# Barely touching
t1 = [Vector[0,0], Vector[1,0], Vector[0,1]]
t2 = [Vector[1,0], Vector[2,0], Vector[1,1]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
 
# Barely touching
t1 = [Vector[0,0], Vector[1,0], Vector[0,1]]
t2 = [Vector[1,0], Vector[2,0], Vector[1,1]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, false)]
end
 
main()</lang>
{{out}}
<pre>Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 5]]
Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 6]]
overlap: true
 
Triangle: [Vector[0, 0], Vector[0, 5], Vector[5, 0]]
Triangle: [Vector[0, 0], Vector[0, 5], Vector[5, 0]]
overlap: true
 
Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 5]]
Triangle: [Vector[-10, 0], Vector[-5, 0], Vector[-1, 6]]
overlap: false
 
Triangle: [Vector[0, 0], Vector[5, 0], Vector[2.5, 5]]
Triangle: [Vector[0, 4], Vector[2.5, -1], Vector[5, 4]]
overlap: true
 
Triangle: [Vector[0, 0], Vector[1, 1], Vector[0, 2]]
Triangle: [Vector[2, 1], Vector[3, 0], Vector[3, 2]]
overlap: false
 
Triangle: [Vector[0, 0], Vector[1, 1], Vector[0, 2]]
Triangle: [Vector[2, 1], Vector[3, -2], Vector[3, 4]]
overlap: false
 
Triangle: [Vector[0, 0], Vector[1, 0], Vector[0, 1]]
Triangle: [Vector[1, 0], Vector[2, 0], Vector[1, 1]]
overlap: true
 
Triangle: [Vector[0, 0], Vector[1, 0], Vector[0, 1]]
Triangle: [Vector[1, 0], Vector[2, 0], Vector[1, 1]]
overlap: false</pre>
 
=={{header|Scala}}==
Retrieved from "https://rosettacode.org/wiki/Determine_if_two_triangles_overlap"