Determine if two triangles overlap: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
m (increased indentations, added whitespace in formulae, added whitespace before the table of contents (TOC).) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 229:
0,false</pre>
=={{header|C
<lang csharp>using System;
using System.Collections.Generic;
Line 549 ⟶ 417:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|C++}}==
<lang cpp>#include <vector>
#include <iostream>
#include <stdexcept>
using namespace std;
typedef std::pair<double, double> TriPoint;
inline double Det2D(TriPoint &p1, TriPoint &p2, TriPoint &p3)
{
return +p1.first*(p2.second-p3.second)
+p2.first*(p3.second-p1.second)
+p3.first*(p1.second-p2.second);
}
void CheckTriWinding(TriPoint &p1, TriPoint &p2, TriPoint &p3, bool allowReversed)
{
double detTri = Det2D(p1, p2, p3);
if(detTri < 0.0)
{
if (allowReversed)
{
TriPoint a = p3;
p3 = p2;
p2 = a;
}
else throw std::runtime_error("triangle has wrong winding direction");
}
}
bool BoundaryCollideChk(TriPoint &p1, TriPoint &p2, TriPoint &p3, double eps)
{
return Det2D(p1, p2, p3) < eps;
}
bool BoundaryDoesntCollideChk(TriPoint &p1, TriPoint &p2, TriPoint &p3, double eps)
{
return Det2D(p1, p2, p3) <= eps;
}
bool TriTri2D(TriPoint *t1,
TriPoint *t2,
double eps = 0.0, bool allowReversed = false, bool onBoundary = true)
{
//Trangles must be expressed anti-clockwise
CheckTriWinding(t1[0], t1[1], t1[2], allowReversed);
CheckTriWinding(t2[0], t2[1], t2[2], allowReversed);
bool (*chkEdge)(TriPoint &, TriPoint &, TriPoint &, double) = NULL;
if(onBoundary) //Points on the boundary are considered as colliding
chkEdge = BoundaryCollideChk;
else //Points on the boundary are not considered as colliding
chkEdge = BoundaryDoesntCollideChk;
//For edge E of trangle 1,
for(int i=0; i<3; i++)
{
int j=(i+1)%3;
//Check all points of trangle 2 lay on the external side of the edge E. If
//they do, the triangles do not collide.
if (chkEdge(t1[i], t1[j], t2[0], eps) &&
chkEdge(t1[i], t1[j], t2[1], eps) &&
chkEdge(t1[i], t1[j], t2[2], eps))
return false;
}
//For edge E of trangle 2,
for(int i=0; i<3; i++)
{
int j=(i+1)%3;
//Check all points of trangle 1 lay on the external side of the edge E. If
//they do, the triangles do not collide.
if (chkEdge(t2[i], t2[j], t1[0], eps) &&
chkEdge(t2[i], t2[j], t1[1], eps) &&
chkEdge(t2[i], t2[j], t1[2], eps))
return false;
}
//The triangles collide
return true;
}
int main()
{
{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,5)};
TriPoint t2[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,6)};
cout << TriTri2D(t1, t2) << "," << true << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(0,5),TriPoint(5,0)};
TriPoint t2[] = {TriPoint(0,0),TriPoint(0,5),TriPoint(5,0)};
cout << TriTri2D(t1, t2, 0.0, true) << "," << true << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(0,5)};
TriPoint t2[] = {TriPoint(-10,0),TriPoint(-5,0),TriPoint(-1,6)};
cout << TriTri2D(t1, t2) << "," << false << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(5,0),TriPoint(2.5,5)};
TriPoint t2[] = {TriPoint(0,4),TriPoint(2.5,-1),TriPoint(5,4)};
cout << TriTri2D(t1, t2) << "," << true << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,1),TriPoint(0,2)};
TriPoint t2[] = {TriPoint(2,1),TriPoint(3,0),TriPoint(3,2)};
cout << TriTri2D(t1, t2) << "," << false << endl;}
{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,1),TriPoint(0,2)};
TriPoint t2[] = {TriPoint(2,1),TriPoint(3,-2),TriPoint(3,4)};
cout << TriTri2D(t1, t2) << "," << false << endl;}
//Barely touching
{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,0),TriPoint(0,1)};
TriPoint t2[] = {TriPoint(1,0),TriPoint(2,0),TriPoint(1,1)};
cout << TriTri2D(t1, t2, 0.0, false, true) << "," << true << endl;}
//Barely touching
{TriPoint t1[] = {TriPoint(0,0),TriPoint(1,0),TriPoint(0,1)};
TriPoint t2[] = {TriPoint(1,0),TriPoint(2,0),TriPoint(1,1)};
cout << TriTri2D(t1, t2, 0.0, false, false) << "," << false << endl;}
}</lang>
{{out}}
<pre>1,1
1,1
0,0
1,1
0,0
0,0
1,1
0,0</pre>
=={{header|D}}==
Line 3,023:
do not overlap: (0,0), (1,1), (0,2) and (2,1), (3,-2), (3,4)
overlap: (0,0), (1,0), (0,1) and (1,0), (2,0), (1,1)</pre>
=={{header|Phix}}==
Line 3,550 ⟶ 3,453:
No output → all tests passed
=={{header|Raku}}==
(formerly 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|REXX}}==
| |||