Determine if two triangles overlap: Difference between revisions
Content deleted Content added
Line 1,898: | Line 1,898: | ||
which have only a single corner in contact, if boundary points do not collide |
which have only a single corner in contact, if boundary points do not collide |
||
do not overlap</pre> |
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}}== |
=={{header|Julia}}== |