Determine if two triangles overlap: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: IupCloseOnEscape no longer needed)
m (→‎{{header|Raku}}: reformatting for clarity)
Line 4,407: Line 4,407:
# https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle
# 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/
# https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

use v6;


sub if-overlap ($triangle-pair) {
sub if-overlap ($triangle-pair) {
Line 4,415: Line 4,413:


sub sign (\T) {
sub sign (\T) {
return (T.[0][0] - T[2][0]) * (T[1][1] - T[2][1]) -
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]);
(T[1;0] - T[2;0]) × (T[0;1] - T[2;1]);
}
}


sub point-in-triangle (\pt, \Y --> Bool) {
sub point-in-triangle (\pt, \Y --> Bool) {
my ($d1, $d2, $d3);
my $d1 = sign (pt, Y[0], Y[1]);
my Bool ($has_neg, $has_pos);
my $d2 = sign (pt, Y[1], Y[2]);
⚫
my $d3 = sign (pt, Y[2], Y[0]);


$d1 = sign (pt, Y.[0], Y.[1]);
my $has_neg = [or] $d1 < 0, $d2 < 0, $d3 < 0;
$d2 = sign (pt, Y.[1], Y.[2]);
my $has_pos = [or] $d1 > 0, $d2 > 0, $d3 > 0;
⚫
$d3 = sign (pt, Y.[2], Y.[0]);


$has_neg = ($d1 < 0) || ($d2 < 0) || ($d3 < 0);
return not ($has_neg and $has_pos);
$has_pos = ($d1 > 0) || ($d2 > 0) || ($d3 > 0);

return !($has_neg && $has_pos);
}
}


sub orientation(\P, \Q, \R --> Int) {
sub orientation(\P, \Q, \R --> Int) {
my \val = (Q.[1] - P.[1]) * (R.[0] - Q.[0]) -
my \val = (Q[1] - P[1]) × (R[0] - Q[0]) -
(Q.[0] - P.[0]) * (R.[1] - Q.[1]);
(Q[0] - P[0]) × (R[1] - Q[1]);


return 0 if val == 0; # colinear
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) {
sub onSegment(\P, \Q, \R --> Bool) {
Q.[0] <= max(P.[0], R.[0]) && Q.[0] >= min(P.[0], R.[0]) &&
Q[0] ≤ max(P[0], R[0]) and Q[0] ≥ min(P[0], R[0]) and
Q.[1] <= max(P.[1], R.[1]) && Q.[1] >= min(P.[0], R.[1])
Q[1] ≤ max(P[1], R[1]) and Q[1] ≥ min(P[0], R[1])
?? True !! False;
?? True !! False
}
}


sub intersect(\A,\B,\C,\D --> Bool) {
sub intersect(\A,\B,\C,\D --> Bool) {
my \o1 = orientation A,C,D;
my \o1 = orientation A, C, D;
my \o2 = orientation B,C,D;
my \o2 = orientation B, C, D;
my \o3 = orientation A,B,C;
my \o3 = orientation A, B, C;
my \o4 = orientation A,B,D;
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)) ;


⚫
o1 != o2 and o3 != o4
⚫
return False;
⚫
or o1 == 0 and onSegment A, C, D
⚫
or o2 == 0 and onSegment B, C, D
⚫
or o3 == 0 and onSegment A, B, C
⚫
or o4 == 0 and onSegment A, B, D
⚫
?? True !! False
}
}


for ^3 {
for ^3 {
{$result = True; last } if point-in-triangle A.[$^i] , B or
{ $result = True; last } if
point-in-triangle B.[$^i] , A ;
point-in-triangle A.[$^i], B or
point-in-triangle B.[$^i], A ;
}
}


unless $result {
unless $result {
$result = True if intersect A.[0], A.[1], B.[0], B.[1] or
$result = True if
intersect A.[0], A.[1], B.[0], B.[1] or
intersect A.[0], A.[1], B.[0], B.[2]
intersect A.[0], A.[1], B.[0], B.[2]
}
}


say A, " and ", B, " do", $result ?? "" !! " NOT" , " overlap.";
say "{A.gist} and {B.gist} do{' NOT' unless $result} overlap.";
}
}


Line 4,488: Line 4,482:


if-overlap $_ for DATA ;</lang>
if-overlap $_ for DATA ;</lang>
{{out}}
{{out}}<pre>[(0 0) (5 0) (0 5)] and [(0 0) (5 0) (0 6)] do overlap.
<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) (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) (0 5)] and [(-10 0) (-5 0) (-1 6)] do NOT overlap.
Line 4,494: Line 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 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 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.
[(0 0) (1 0) (0 1)] and [(1 0) (2 0) (1 1)] do overlap.</pre>
</pre>


=={{header|REXX}}==
=={{header|REXX}}==
Retrieved from "https://rosettacode.org/wiki/Determine_if_two_triangles_overlap"