Rosetta Code

Determine if two triangles overlap: Difference between revisions

Page Discussion

Determine if two triangles overlap (view source)

Revision as of 20:31, 11 February 2021

123 bytes removed ,  3 years ago
m
→‎{{header|Raku}}: reformatting for clarity
m (→‎{{header|Phix}}: IupCloseOnEscape no longer needed)
m (→‎{{header|Raku}}: reformatting for clarity)
Line 4,407:
# 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) {
Line 4,415 ⟶ 4,413:
 
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 = sign (pt, $d2Y[0], $d3Y[1]);
my Bool$d2 = sign ($has_negpt, $has_posY[1], Y[2]);
my $d3 = sign (pt, Y.[2], Y.[0]);▼
 
my $d1has_neg = sign[or] (pt$d1 < 0, Y.[$d2 < 0], Y.[1])$d3 < 0;
my $d2has_pos = sign[or] (pt$d1 > 0, Y.[1]$d2 > 0, Y.[2])$d3 > 0;
▲ $d3 = sign (pt, Y.[2], Y.[0]);
 
$has_negreturn =not ($d1has_neg <and 0) || ($d2 < 0) || ($d3 < 0has_pos);
$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▼
 
▲ return (val > 0) ?? 1 !! 2; # clock or counterclock wise
}
 
sub onSegment(\P, \Q, \R --> Bool) {
Q.[0] <=≤ max(P.[0], R.[0]) &&and Q.[0] >=≥ min(P.[0], R.[0]) &&and
Q.[1] <=≤ max(P.[1], R.[1]) &&and 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 True if o1 != o2 &&and o3 != o4;
return False;▼
▲ returnor True if (o1 == 0 &&and onSegment( A, C, D)) ;
▲ returnor True if (o2 == 0 &&and onSegment( B, C, D)) ;
▲ returnor True if (o3 == 0 &&and onSegment( A, B, C)) ;
▲ returnor True if (o4 == 0 &&and onSegment( A, B, D)) ;
▲ return ?? True !! False;
}
 
for ^3 {
{ $result = True; last } if point-in-triangle A.[$^i] , B or
point-in-triangle BA.[$^i] , AB ;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.[1] or
intersect A.[0], A.[1], B.[0], B.[2]
}
 
say "{A, ".gist} and ", {B, ".gist} do",{' NOT' unless $result ?? "" !! " NOT" , "} overlap.";
}
 
Line 4,488 ⟶ 4,482:
 
if-overlap $_ for DATA ;</lang>
{{out}}
{{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.
Line 4,494 ⟶ 4,489:
[(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>
</pre>
 
=={{header|REXX}}==
SqrtNegInf
2,392

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/272427"