Determine if two triangles overlap: Difference between revisions
Determine if two triangles overlap (view source)
Revision as of 15:54, 30 October 2018
, 5 years ago→{{header|Go}}
Walterpachl (talk | contribs) m (→{{header|REXX}}: add →REXX) |
|||
Line 516:
Triangle: Tuple!(real, real)(0, 0), Tuple!(real, real)(1, 0), Tuple!(real, real)(0, 1) and
Triangle: Tuple!(real, real)(1, 0), Tuple!(real, real)(2, 0), Tuple!(real, real)(1, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|F#|F sharp}}==
{{trans|Kotlin}}
<lang fsharp>open System
type Point = double * double
type Triangle = Point * Point * Point
let Det2D (t:Triangle) =
let (p1, p2, p3) = t
let (p1x, p1y) = p1
let (p2x, p2y) = p2
let (p3x, p3y) = p3
p1x * (p2y - p3y) +
p2x * (p3y - p1y) +
p3x * (p1y - p2y)
let CheckTriWinding allowReversed t =
let detTri = Det2D t
if detTri < 0.0 then
if allowReversed then
let (p1, p2, p3) = t
(p1, p3, p2)
else
raise (Exception "Triangle has wrong winding direction")
else
t
let boundaryCollideChk eps t =
(Det2D t) < eps
let boundaryDoesntCollideChk eps t =
(Det2D t) <= eps
let TriTri2D eps allowReversed onBoundary t1 t2 =
// Triangles must be expressed anti-clockwise
let t3 = CheckTriWinding allowReversed t1
let t4 = CheckTriWinding allowReversed t2
// 'onBoundary' determines whether points on boundary are considered as colliding or not
let chkEdge = if onBoundary then boundaryCollideChk else boundaryDoesntCollideChk
let (t1p1, t1p2, t1p3) = t3
let (t2p1, t2p2, t2p3) = t4
// Check all points of t2 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (chkEdge eps (t1p1, t1p2, t2p1)) && (chkEdge eps (t1p1, t1p2, t2p2)) && (chkEdge eps (t1p1, t1p2, t2p3)) then
false
else if (chkEdge eps (t1p2, t1p3, t2p1)) && (chkEdge eps (t1p2, t1p3, t2p2)) && (chkEdge eps (t1p2, t1p3, t2p3)) then
false
else if (chkEdge eps (t1p3, t1p1, t2p1)) && (chkEdge eps (t1p3, t1p1, t2p2)) && (chkEdge eps (t1p3, t1p1, t2p3)) then
false
// Check all points of t1 lay on the external side of edge E.
// If they do, the triangles do not overlap.
else if (chkEdge eps (t2p1, t2p2, t1p1)) && (chkEdge eps (t2p1, t2p2, t1p2)) && (chkEdge eps (t2p1, t2p2, t1p3)) then
false
else if (chkEdge eps (t2p2, t2p3, t1p1)) && (chkEdge eps (t2p2, t2p3, t1p2)) && (chkEdge eps (t2p2, t2p3, t1p3)) then
false
else if (chkEdge eps (t2p3, t2p1, t1p1)) && (chkEdge eps (t2p3, t2p1, t1p2)) && (chkEdge eps (t2p3, t2p1, t1p3)) then
false
else
// The triangles overlap
true
let Print t1 t2 =
Console.WriteLine("{0} and\n{1}\n{2}\n", t1, t2, if TriTri2D 0.0 false true t1 t2 then "overlap" else "do not overlap")
[<EntryPoint>]
let main _ =
let t1 = ((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
let t2 = ((0.0, 0.0), (5.0, 0.0), (0.0, 6.0))
Print t1 t2
let t3 = ((0.0, 0.0), (0.0, 5.0), (5.0, 0.0))
Console.WriteLine("{0} and\n{1}\n{2}\n", t3, t3, if TriTri2D 0.0 true true t3 t3 then "overlap (reversed)" else "do not overlap")
let t4 = ((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
let t5 = ((-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0))
Print t4 t5
let t6 = ((0.0, 0.0), (5.0, 0.0), (2.5, 5.0))
let t7 = ((0.0, 4.0), (2.5, -1.0), (5.0, 4.0))
Print t6 t7
let t8 = ((0.0, 0.0), (1.0, 1.0), (0.0, 2.0))
let t9 = ((2.0, 1.0), (3.0, 0.0), (3.0, 2.0))
Print t8 t9
let t10 = ((2.0, 1.0), (3.0, -2.0), (3.0, 4.0))
Print t8 t10
let t11 = ((0.0, 0.0), (1.0, 0.0), (0.0, 1.0))
let t12 = ((1.0, 0.0), (2.0, 0.0), (1.0, 1.1))
printfn "The following triangles which have only a single corner in contact, if boundary points collide"
Print t11 t12
Console.WriteLine("{0} and\n{1}\nwhich have only a single corner in contact, if boundary points do not collide\n{2}", t11, t12, if TriTri2D 0.0 false false t11 t12 then "overlap" else "do not overlap")
0 // return an integer exit code</lang>
{{out}}
<pre>((0, 0), (5, 0), (0, 5)) and
((0, 0), (5, 0), (0, 6))
overlap
((0, 0), (0, 5), (5, 0)) and
((0, 0), (0, 5), (5, 0))
overlap (reversed)
((0, 0), (5, 0), (0, 5)) and
((-10, 0), (-5, 0), (-1, 6))
do not overlap
((0, 0), (5, 0), (2.5, 5)) and
((0, 4), (2.5, -1), (5, 4))
overlap
((0, 0), (1, 1), (0, 2)) and
((2, 1), (3, 0), (3, 2))
do not overlap
((0, 0), (1, 1), (0, 2)) and
((2, 1), (3, -2), (3, 4))
do not overlap
The following triangles which have only a single corner in contact, if boundary points collide
((0, 0), (1, 0), (0, 1)) and
((1, 0), (2, 0), (1, 1.1))
overlap
((0, 0), (1, 0), (0, 1)) and
((1, 0), (2, 0), (1, 1.1))
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
| |||