Determine if two triangles overlap: Difference between revisions
Determine if two triangles overlap (view source)
Revision as of 14:04, 12 February 2019
, 5 years agoadded Perl 6
(added Perl 6) |
|||
Line 2,873:
Triangle: (1, 0), (2, 0), (1, 1)
do not overlap</pre>
=={{header|Perl 6}}==
First, check if any vertex is inside each other triangle (that should cover most overlapping cases including enclosures). Then see if an edge of triangle A intersects any of two edges of B (for shapes like Star of David [https://en.wikipedia.org/wiki/Star_of_David])
<lang perl6>#!/usr/bin/env perl6
# Reference:
# https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle
# https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
use v6;
sub if-overlap ($triangle-pair) {
my (\A,\B) = $triangle-pair;
my Bool $result = False;
sub sign (\T) {
return (T.[0][0] - T[2][0]) * (T[1][1] - T[2][1]) -
(T[1][0] - T[2][0]) * (T[0][1] - T[2][1]);
}
sub point-in-triangle (\pt, \Y --> Bool) {
my ($d1, $d2, $d3);
my Bool ($has_neg, $has_pos);
$d1 = sign (pt, Y.[0], Y.[1]);
$d2 = sign (pt, Y.[1], Y.[2]);
$d3 = sign (pt, Y.[2], Y.[0]);
$has_neg = ($d1 < 0) || ($d2 < 0) || ($d3 < 0);
$has_pos = ($d1 > 0) || ($d2 > 0) || ($d3 > 0);
return !($has_neg && $has_pos);
}
sub orientation(\P, \Q, \R --> Int) {
my \val = (Q.[1] - P.[1]) * (R.[0] - Q.[0]) -
(Q.[0] - P.[0]) * (R.[1] - Q.[1]);
return 0 if val == 0; # colinear
return (val > 0) ?? 1 !! 2; # clock or counterclock wise
}
sub onSegment(\P, \Q, \R --> Bool) {
Q.[0] <= max(P.[0], R.[0]) && Q.[0] >= min(P.[0], R.[0]) &&
Q.[1] <= max(P.[1], R.[1]) && Q.[1] >= min(P.[0], R.[1])
?? True !! False;
}
sub intersect(\A,\B,\C,\D --> Bool) {
my \o1 = orientation A,C,D;
my \o2 = orientation B,C,D;
my \o3 = orientation A,B,C;
my \o4 = orientation A,B,D;
return True if o1 != o2 && o3 != o4;
return True if (o1 == 0 && onSegment(A, C, D)) ;
return True if (o2 == 0 && onSegment(B, C, D)) ;
return True if (o3 == 0 && onSegment(A, B, C)) ;
return True if (o4 == 0 && onSegment(A, B, D)) ;
return False;
}
for ^3 {
{$result = True; last } if point-in-triangle A.[$^i] , B or
point-in-triangle B.[$^i] , A ;
}
unless $result {
$result = True if intersect A.[0], A.[1], B.[0], B.[1] or
intersect A.[0], A.[1], B.[0], B.[2]
}
say A, " and ", B, " do", $result ?? "" !! " NOT" , " overlap.";
}
my \DATA = [
[ [(0,0),(5,0),(0,5)] , [(0,0),(5,0),(0,6)] ],
[ [(0,0),(0,5),(5,0)] , [(0,0),(0,5),(5,0)] ],
[ [(0,0),(5,0),(0,5)] , [(-10,0),(-5,0),(-1,6)] ],
[ [(0,0),(5,0),(2.5,5)] , [ (0,4),(2.5,-1),(5,4)] ],
[ [(0,0),(1,1),(0,2)] , [(2,1),(3,0),(3,2)] ],
[ [(0,0),(1,1),(0,2)] , [(2,1),(3,-2),(3,4)] ],
[ [(0,0),(1,0),(0,1)] , [(1,0),(2,0),(1,1)] ]
];
if-overlap $_ for DATA ;</lang>
{{out}}<pre>[(0 0) (5 0) (0 5)] and [(0 0) (5 0) (0 6)] do overlap.
[(0 0) (0 5) (5 0)] and [(0 0) (0 5) (5 0)] do overlap.
[(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)] do 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.
[(0 0) (1 0) (0 1)] and [(1 0) (2 0) (1 1)] do overlap.
</pre>
=={{header|Phix}}==
| |||