Determine if two triangles overlap: Difference between revisions
Determine if two triangles overlap (view source)
Revision as of 07:26, 6 November 2021
, 2 years ago→{{header|jq}}
Line 1,898:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<lang jq># Points are realized as arrays of two numbers [x, y]
# Triangles are realized as triples of Points [p1, p2, p3]
# Input: a Triangle
def det2D:
. as [ [$p1x, $p1y], [$p2x, $p2y], [$p3x, $p3y]]
| $p1x * ($p2y - $p3y) +
$p2x * ($p3y - $p1y) +
$p3x * ($p1y - $p2y) ;
# Input: a Triangle
def checkTriWinding(allowReversed):
if det2D < 0
then if allowReversed
then . as [$p1, $p2, $p3]
| [$p1, $p3, $p2 ]
else "Triangle has wrong winding direction" | error
end
else .
end;
def boundaryCollideChk(eps): det2D < eps;
def boundaryDoesntCollideChk(eps): det2D <= eps;
def triTri2D($t1; $t2; $eps; $allowReversed; $onBoundary):
def chkEdge:
if $onBoundary then boundaryCollideChk($eps)
else boundaryDoesntCollideChk($eps)
end;
# Triangles must be expressed anti-clockwise
($t1|checkTriWinding($allowReversed))
| ($t2|checkTriWinding($allowReversed))
# 'onBoundary' determines whether points on boundary are considered as colliding or not
# for each edge E of t1
| first( range(0;3) as $i
| (($i + 1) % 3) as $j
# Check all points of t2 lie on the external side of edge E.
# If they do, the triangles do not overlap.
| if ([$t1[$i], $t1[$j], $t2[0]]| chkEdge) and
([$t1[$i], $t1[$j], $t2[1]]| chkEdge) and
([$t1[$i], $t1[$j], $t2[2]]| chkEdge)
then 0
else empty
end) // true
| if . == 0 then false
else
# for each edge E of t2
first( range(0;3) as $i
| (($i + 1) % 3) as $j
# Check all points of t1 lie on the external side of edge E.
# If they do, the triangles do not overlap.
| if ([$t2[$i], $t2[$j], $t1[0]] | chkEdge) and
([$t2[$i], $t2[$j], $t1[1]] | chkEdge) and
([$t2[$i], $t2[$j], $t1[2]] | chkEdge)
then 0
else empty
end) // true
| if . == 0 then false
else true # The triangles overlap
end
end ;</lang>
'''The Task'''
<lang jq>def task:
def t: "Triangle: ";
def printTris(t1; t2; nl):
"\(nl)\(t)\(t1) and\n\(t)\(t2)" ;
def overlap(t1; t2):
if triTri2D(t1; t2; 0; false; true) then "overlap" else "do not overlap" end;
def overlapr(t1; t2):
if triTri2D(t1; t2; 0; true; true) then "overlap (reversed)" else "do not overlap" end;
([ [0, 0], [5, 0], [0, 5] ] as $t1
| [ [0, 0], [5, 0], [0, 6] ] as $t2
| printTris($t1; $t2; ""),
overlap($t1; $t2) ),
([ [0, 0], [0, 5], [5, 0] ] as $t1
| $t1 as $t2
| printTris($t1; $t2; "\n"),
# need to allow reversed for this pair to avoid exception
overlapr($t1; $t2) ),
([ [0, 0], [5, 0], [0, 5] ] as $t1
| [ [-10, 0], [-5, 0], [-1, 6] ] as $t2
| printTris($t1; $t2; "\n"),
overlap($t1; $t2) ),
([ [0, 0], [5, 0], [2.5, 5] ] as $t1
| [ [0, 4], [2.5, -1], [5, 4] ] as $t2
| printTris($t1; $t2; "\n"),
overlap($t1; $t2) ),
([ [0, 0], [1, 1], [0, 2] ] as $t1
| ([ [2, 1], [3, 0], [3, 2] ] as $t2
| printTris($t1; $t2; "\n"),
overlap($t1; $t2) ),
( [[2, 1], [3, -2], [3, 4]] as $t2
| printTris($t1; $t2; "\n"),
overlap($t1; $t2) )),
([ [0, 0], [1, 0], [0, 1] ] as $t1
| [ [1, 0], [2, 0], [1, 1.1] ] as $t2
| (printTris($t1; $t2; ""),
"which have only a single corner in contact, if boundary points collide",
overlap($t1; $t2) ),
(printTris($t1; $t2; "\n"),
"which have only a single corner in contact, if boundary points do not collide",
if triTri2D($t1; $t2; 0; false; false) then "overlap" else "do not overlap" end) );
task</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 (reversed)
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.1]]
which have only a single corner in contact, if boundary points collide
overlap
Triangle: [[0,0],[1,0],[0,1]] and
Triangle: [[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>
=={{header|Julia}}==
| |||