Determine if two triangles overlap: Difference between revisions
Added Easylang
m (increased indentations, added whitespace in formulae, added whitespace before the table of contents (TOC).) |
(Added Easylang) |
||
| (37 intermediate revisions by 22 users not shown) | |||
Line 1:
[[Category:Geometry]]
[[Category:Collision detection]]
{{
Determining if two triangles in the same plane overlap is an important topic in collision detection.
Line 17:
Optionally, see what the result is when only a single corner is in contact (there is no
:::* (0,0),(1,0),(0,1) and (1,0),(2,0),(1,1)
<br><br>
;Related tasks
* [[Check_if_two_polygons_overlap|Check if two polygons overlap]]
* [[Check_if_a_polygon_overlaps_with_a_rectangle|Check if a polygon overlaps with a rectangle]]
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight lang="11l">T Triangle
(Float, Float) p1, p2, p3
F (p1, p2, p3)
.p1 = p1
.p2 = p2
.p3 = p3
F String()
R ‘Triangle: #., #., #.’.format(.p1, .p2, .p3)
F.const det2D()
R .p1[0] * (.p2[1] - .p3[1])
+ .p2[0] * (.p3[1] - .p1[1])
+ .p3[0] * (.p1[1] - .p2[1])
F checkTriWinding(Triangle &t; allowReversed)
V detTri = t.det2D()
I detTri < 0.0
assert(allowReversed, ‘Triangle has wrong winding direction’)
swap(&t.p2, &t.p3)
F boundaryCollideChk(Triangle t, Float eps)
R t.det2D() < eps
F boundaryDoesntCollideChk(Triangle t, Float eps)
R t.det2D() <= eps
F triTri2D(Triangle &t1, &t2; eps = 0.0, allowReversed = 0B, onBoundary = 1B)
checkTriWinding(&t1, allowReversed)
checkTriWinding(&t2, allowReversed)
V chkEdge = I onBoundary {:boundaryCollideChk} E :boundaryDoesntCollideChk
V lp1 = [t1.p1, t1.p2, t1.p3]
V lp2 = [t2.p1, t2.p2, t2.p3]
L(i) 3
V j = (i + 1) % 3
I chkEdge(Triangle(lp1[i], lp1[j], lp2[0]), eps) &
chkEdge(Triangle(lp1[i], lp1[j], lp2[1]), eps) &
chkEdge(Triangle(lp1[i], lp1[j], lp2[2]), eps)
R 0B
L(i) 3
V j = (i + 1) % 3
I chkEdge(Triangle(lp2[i], lp2[j], lp1[0]), eps) &
chkEdge(Triangle(lp2[i], lp2[j], lp1[1]), eps) &
chkEdge(Triangle(lp2[i], lp2[j], lp1[2]), eps)
R 0B
R 1B
F overlap(Triangle &t1, &t2; eps = 0.0, allowReversed = 0B, onBoundary = 1B)
I triTri2D(&t1, &t2, eps, allowReversed, onBoundary)
print(‘overlap’)
E
print(‘do not overlap’)
V t1 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
V t2 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 6.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1 = Triangle((0.0, 0.0), (0.0, 5.0), (5.0, 0.0))
t2 = t1
print(t1" and\n"t2)
overlap(&t1, &t2, 0.0, 1B)
print()
t1 = Triangle((0.0, 0.0), (5.0, 0.0), (0.0, 5.0))
t2 = Triangle((-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1.p3 = (2.5, 5.0)
t2 = Triangle((0.0, 4.0), (2.5, -1.0), (5.0, 4.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1 = Triangle((0.0, 0.0), (1.0, 1.0), (0.0, 2.0))
t2 = Triangle((2.0, 1.0), (3.0, 0.0), (3.0, 2.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t2 = Triangle((2.0, 1.0), (3.0, -2.0), (3.0, 4.0))
print(t1" and\n"t2)
overlap(&t1, &t2)
print()
t1 = Triangle((0.0, 0.0), (1.0, 0.0), (0.0, 1.0))
t2 = Triangle((1.0, 0.0), (2.0, 0.0), (1.0, 1.1))
print(t1" and\n"t2)
print(‘which have only a single corner in contact, if boundary points collide’)
overlap(&t1, &t2)
print()
print(t1" and\n"t2)
print(‘which have only a single corner in contact, if boundary points do not collide’)
overlap(&t1, &t2, 0.0, 0B, 0B)</syntaxhighlight>
{{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
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|Ada}}==
<
WITH Ada.Text_IO; USE Ada.Text_IO;
Line 62 ⟶ 210:
Put ((0.0, 0.0, 1.0, 0.0, 0.0, 1.0), (1.0, 0.0, 2.0, 0.0, 1.0, 1.0));
END Main;
</syntaxhighlight>
{{out}}
<pre>true
Line 72 ⟶ 220:
true
</pre>
=={{header|ALGOL 68}}==
Uses the code from the Algol 68 sample for the [[Check if two polygons overlap]] task.<br>
Triangles with a single point in contact are considerfed to overlap.
<syntaxhighlight lang="algol68">
BEGIN # test for overlapping 2D triangles - using the code from the Algol 68 #
# sample for the Check if two polygons overlap task, the code of which #
# is based on a translation of that tasks' Go which is a translation #
# of Wren #
# In the following a polygon is represented as a row of vertices #
# and a vertex ( POINT ) by a pair of x, y coordinates in the plane #
MODE POINT = STRUCT( REAL x, y );
MODE PROJECTION = STRUCT( REAL min, max );
MODE POLYGON = FLEX[ 1 : 0 ]POINT;
PRIO DOT = 3;
OP DOT = ( POINT v, other )REAL:
( x OF v * x OF other ) + ( y OF v * y OF other );
# returns the axes of the polygon defined by poly #
OP AXES = ( POLYGON poly )[]POINT:
BEGIN
[ LWB poly : UPB poly ]POINT result;
FOR i FROM LWB poly TO UPB poly DO
INT j = IF i = UPB poly THEN LWB poly ELSE i + 1 FI;
POINT vertex1 = poly[ i ];
POINT vertex2 = poly[ j ];
POINT edge = ( x OF vertex1 - x OF vertex2, y OF vertex1 - y OF vertex2 );
result[ i ] := ( - y OF edge, x OF edge )
OD;
result
END # AXES # ;
# returns the projection of poly onto axis #
PRIO PROJECTONTO = 3;
OP PROJECTONTO = ( POLYGON poly, POINT axis )PROJECTION:
BEGIN
REAL min := axis DOT poly[ LWB poly ];
REAL max := min;
FOR i FROM LWB poly + 1 TO UPB poly DO
REAL p = axis DOT poly[ i ];
IF p < min THEN
min := p
ELIF p > max THEN
max := p
FI
OD;
PROJECTION( min, max )
END # PROJECTONTO # ;
PRIO OVERLAPS = 5;
# returns TRUE if the projections proj1 and proj2 overlap, #
# FALSE otherrwise #
OP OVERLAPS = ( PROJECTION proj1, proj2 )BOOL:
IF max OF proj1 < min OF proj2 THEN FALSE
ELIF max OF proj2 < min OF proj1 THEN FALSE
ELSE TRUE
FI # OVERLAPS # ;
# returns TRUE if the ppolygons poly1 and poly2 overlap, #
# FALSE otherrwise #
OP OVERLAPS = ( POLYGON poly1, poly2 )BOOL:
BEGIN
[]POINT axes1 = AXES poly1, axes2 = AXES poly2;
BOOL does overlap := TRUE;
FOR a FROM LWB axes1 TO UPB axes1 WHILE does overlap DO
does overlap := ( poly1 PROJECTONTO axes1[ a ] )
OVERLAPS ( poly2 PROJECTONTO axes1[ a ] )
OD;
FOR a FROM LWB axes2 TO UPB axes2 WHILE does overlap DO
does overlap := ( poly1 PROJECTONTO axes2[ a ] )
OVERLAPS ( poly2 PROJECTONTO axes2[ a ] )
OD;
does overlap
END # OVERLAPS # ;
# returns x as a string without trailing 0 decoimals #
OP TOSTRING = ( REAL x )STRING:
BEGIN
STRING v := fixed( x, -14, 11 );
INT end pos := UPB v;
WHILE IF end pos < LWB v THEN FALSE ELSE v[ end pos ] = "0" FI DO
end pos -:= 1
OD;
IF end pos >= LWB v THEN
IF v[ end pos ] = "." THEN end pos -:= 1 FI
FI;
INT start pos := LWB v;
WHILE IF start pos > end pos THEN FALSE ELSE v[ start pos ] = " " FI DO
start pos +:= 1
OD;
IF end pos < start pos THEN "0" ELSE v[ start pos : end pos ] FI
END # TOSTRING # ;
# returns a string representation of the POINT p #
OP TOSTRING = ( POINT p )STRING: "( " + TOSTRING x OF p + ", " + TOSTRING y OF p + " )";
# returns a string representation of the points of p #
OP TOSTRING = ( POLYGON p )STRING:
BEGIN
STRING result := "(", separator := "";
FOR i FROM LWB p TO UPB p DO
result +:= separator + " " + TOSTRING p[ i ];
separator := ","
OD;
result + " )"
END # TOSTRING # ;
# code specific to thius task #
# test cases - using the general POLYGON MODE to represent triangles #
[,]POLYGON triangle pairs
= ( ( ( ( 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 ) ) )
);
FOR t pos FROM LWB triangle pairs TO UPB triangle pairs DO
[]POLYGON tpair = triangle pairs[ t pos, : ];
POLYGON t1 = tpair[ LWB tpair ];
POLYGON t2 = tpair[ UPB tpair ];
print( ( TOSTRING t1
, IF t1 OVERLAPS t2 THEN " overlaps " ELSE " does not overlap " FI
, TOSTRING t2
, newline
)
)
OD
END
</syntaxhighlight>
{{out}}
<pre>
( ( 0, 0 ), ( 5, 0 ), ( 0, 5 ) ) overlaps ( ( 0, 0 ), ( 5, 0 ), ( 0, 6 ) )
( ( 0, 0 ), ( 0, 5 ), ( 5, 0 ) ) overlaps ( ( 0, 0 ), ( 0, 5 ), ( 5, 0 ) )
( ( 0, 0 ), ( 5, 0 ), ( 0, 5 ) ) does not overlap ( ( -10, 0 ), ( -5, 0 ), ( -1, 6 ) )
( ( 0, 0 ), ( 5, 0 ), ( 2.5, 5 ) ) overlaps ( ( 0, 4 ), ( 2.5, -1 ), ( 5, 4 ) )
( ( 0, 0 ), ( 1, 1 ), ( 0, 2 ) ) does not overlap ( ( 2, 1 ), ( 3, 0 ), ( 3, 2 ) )
( ( 0, 0 ), ( 1, 1 ), ( 0, 2 ) ) does not overlap ( ( 2, 1 ), ( 3, -2 ), ( 3, 4 ) )
( ( 0, 0 ), ( 1, 0 ), ( 0, 1 ) ) overlaps ( ( 1, 0 ), ( 2, 0 ), ( 1, 1 ) )
</pre>
=={{header|ALGOL W}}==
{{Trans|Kotlin}}
... with different output format (based on Modula 2).
<syntaxhighlight lang="algolw">begin % determine if two triangles overlap %
record Point ( real x, y );
record Triangle ( reference(Point) p1, p2, p3 );
procedure WritePoint ( reference(Point) value p ) ;
writeon( r_w := 3, r_d := 1, r_format := "A", s_w := 0, "(", x(p), ", ", y(p), ")" );
procedure WriteTriangle ( reference(Triangle) value t ) ;
begin
WritePoint( p1(t) );
writeon( ", " );
WritePoint( p2(t) );
writeon( ", " );
WritePoint( p3(t) )
end WriteTriangle ;
real procedure Det2D ( reference(Triangle) value t ) ;
( ( x(p1(t)) * ( y(p2(t)) - y(p3(t)) ) )
+ ( x(p2(t)) * ( y(p3(t)) - y(p1(t)) ) )
+ ( x(p3(t)) * ( y(p1(t)) - y(p2(t)) ) )
);
procedure CheckTriWinding ( reference(Triangle) value t ; logical value allowReversed ) ;
begin
real detTri;
detTri := Det2D(t);
if detTri < 0.0 then begin
if allowReversed then begin
reference(Point) a;
a := p3(t);
p3(t) := p2(t);
p2(t) := a
end
else begin
write( "triangle has wrong winding direction" );
assert( false )
end
end if_detTri_lt_0
end CheckTriWinding ;
logical procedure BoundaryCollideChk( reference(Triangle) value t ; real value eps ) ; Det2D( t ) < eps ;
logical procedure BoundaryDoesntCollideChk( reference(Triangle) value t ; real value eps ) ; Det2D( t ) <= eps ;
logical procedure TriTri2D( reference(Triangle) value t1, t2 ; real value eps ; logical value allowReversed, onBoundary ) ;
begin
logical procedure ChkEdge( reference(Triangle) value t ) ;
if onBoundary then % Points on the boundary are considered as colliding %
BoundaryCollideChk( t, eps )
else % Points on the boundary are not considered as colliding %
BoundaryDoesntCollideChk( t, eps )
;
reference(Point) array lp1, lp2 ( 0 :: 2 );
logical overlap;
overlap := true;
% Triangles must be expressed anti-clockwise %
CheckTriWinding( t1, allowReversed );
CheckTriWinding( t2, allowReversed );
lp1( 0 ) := p1(t1); lp1( 1 ) := p2(t1); lp1( 2 ) := p3(t1);
lp2( 0 ) := p1(t2); lp2( 1 ) := p2(t2); lp2( 2 ) := p3(t2);
% for each edge E of t1 %
for i := 0 until 2 do begin
integer j;
j := ( i + 1 ) rem 3;
% Check all points of t2 lay on the external side of edge E. %
% if they do, the triangles do not overlap. %
if ChkEdge( Triangle( lp1( i ), lp1( j ), lp2( 0 ) ) )
and ChkEdge( Triangle( lp1( i ), lp1( j ), lp2( 1 ) ) )
and ChkEdge( Triangle( lp1( i ), lp1( j ), lp2( 2 ) ) )
then begin
overlap := false;
goto return
end
end for_i ;
% for each edge E of t2 %
for i := 0 until 2 do begin
integer j;
j := ( i + 1 ) rem 3;
% Check all points of t1 lay on the external side of edge E. %
% if they do, the triangles do not overlap. %
if ChkEdge( Triangle( lp2( i ), lp2( j ), lp1( 0 ) ) )
and ChkEdge( Triangle( lp2( i ), lp2( j ), lp1( 1 ) ) )
and ChkEdge( Triangle( lp2( i ), lp2( j ), lp1( 2 ) ) )
then begin
overlap := false;
goto return
end
end for_i;
% if we get here, The triangles overlap %
return: overlap
end TriTri2D ;
procedure CheckOverlap( reference(Triangle) value t1, t2
; real value eps
; logical value allowReversed, onBoundary
) ;
begin
write( "Triangles " );
WriteTriangle( t1 );
writeon( " and " );
WriteTriangle( t2 );
writeon( if TriTri2D( t1, t2, eps, allowReversed, onBoundary ) then " overlap" else " do not overlap" );
end CheckOverlap ;
begin % main %
reference(Triangle) t1, t2;
t1 := Triangle( Point( 0.0, 0.0 ), Point( 5.0, 0.0 ), Point( 0.0, 5.0 ) );
t2 := Triangle( Point( 0.0, 0.0 ), Point( 5.0, 0.0 ), Point( 0.0, 6.0 ) );
CheckOverlap( t1, t2, 0.0, false, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 0.0, 5.0 ), Point( 5.0, 0.0 ) );
t2 := Triangle( Point( 0.0, 0.0 ), Point( 0.0, 5.0 ), Point( 5.0, 0.0 ) );
CheckOverlap(t1, t2, 0.0, true, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 5.0, 0.0 ), Point( 0.0, 5.0 ) );
t2 := Triangle( Point( -10.0, 0.0 ), Point( -5.0, 0.0 ), Point( -1.0, 6.0 ) );
CheckOverlap( t1, t2, 0.0, false, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 5.0, 0.0 ), Point( 2.5, 5.0 ) );
t2 := Triangle( Point( 0.0, 4.0 ), Point( 2.5, -1.0 ), Point( 5.0, 4.0 ) );
CheckOverlap( t1, t2, 0.0, false, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 1.0, 1.0 ), Point( 0.0, 2.0 ) );
t2 := Triangle( Point( 2.0, 1.0 ), Point( 3.0, 0.0 ), Point( 3.0, 2.0 ) );
CheckOverlap( t1, t2, 0.0, false, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 1.0, 1.0 ), Point( 0.0, 2.0 ) );
t2 := Triangle( Point( 2.0, 1.0 ), Point( 3.0, -2.0 ), Point( 3.0, 4.0 ) );
CheckOverlap( t1, t2, 0.0, false, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 1.0, 0.0 ), Point( 0.0, 1.0 ) );
t2 := Triangle( Point( 1.0, 0.0 ), Point( 2.0, 0.0 ), Point( 1.0, 1.1 ) );
CheckOverlap( t1, t2, 0.0, false, true );
t1 := Triangle( Point( 0.0, 0.0 ), Point( 1.0, 0.0 ), Point( 0.0, 1.0 ) );
t2 := Triangle( Point( 1.0, 0.0 ), Point( 2.0, 0.0 ), Point( 1.0, 1.1 ) );
CheckOverlap( t1, t2, 0.0, false, false );
end
end.</syntaxhighlight>
{{out}}
<pre>
Triangles (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and (0.0, 0.0), (5.0, 0.0), (0.0, 6.0) overlap
Triangles (0.0, 0.0), (0.0, 5.0), (5.0, 0.0) and (0.0, 0.0), (0.0, 5.0), (5.0, 0.0) overlap
Triangles (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and (-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0) do not overlap
Triangles (0.0, 0.0), (5.0, 0.0), (2.5, 5.0) and (0.0, 4.0), (2.5, -1.0), (5.0, 4.0) overlap
Triangles (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and (2.0, 1.0), (3.0, 0.0), (3.0, 2.0) do not overlap
Triangles (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and (2.0, 1.0), (3.0, -2.0), (3.0, 4.0) do not overlap
Triangles (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and (1.0, 0.0), (2.0, 0.0), (1.0, 1.1) overlap
Triangles (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and (1.0, 0.0), (2.0, 0.0), (1.0, 1.1) do not overlap
</pre>
=={{header|ATS}}==
<syntaxhighlight lang="ATS">
(* Given that the context is collision detection, we will consider
containment of one triangle entirely inside the other as ‘overlap’
and test for that, as well as for overlap of the triangle sides
themselves. One must agree that, if one triangle has become buried
entirely inside another, then the two have collided. There are
consequences for the conservation of momentum.
Besides, the full set of overlap tests, INCLUDING containment of
one polygonal hull inside another, is relevant to the problem of
finding intersections of Bézier curves. See
https://rosettacode.org/wiki/B%C3%A9zier_curves/Intersections
This code specifically tests for overlapping vertices, in case the
main tests fail to catch such overlaps. Approximate equality is
employed rather than exact floating-point equality. *)
#include "share/atspre_staload.hats"
%{^
#include <math.h>
#include <float.h>
%}
macdef dbl_epsilon = $extval (double, "DBL_EPSILON")
(* We will use some simple homogeneous geometric algebra. *)
typedef point =
@{e1 = double,
e2 = double,
e0 = double}
macdef Pt (x, y) = (* Shorthand for creating a normalized point. *)
@{e1 = ,(x),
e2 = ,(y),
e0 = 1.0} : point
typedef line =
@{e0_e1 = double,
e0_e2 = double,
e1_e2 = double}
typedef triangle = @(point, point, point)
fn
outer_product_point_point (a : point, b : point) : line =
@{e0_e1 = ~(~a.e0 * b.e1 + a.e1 * b.e0),
e0_e2 = ~(~a.e0 * b.e2 + a.e2 * b.e0),
e1_e2 = (a.e1 * b.e2 - a.e2 * b.e1)}
fn
left_contraction_point_line (a : point, b : line) : point =
@{e1 = (a.e0 * b.e0_e1 - a.e2 * b.e1_e2),
e2 = (a.e0 * b.e0_e2 + a.e1 * b.e1_e2),
e0 = (~a.e1 * b.e0_e1 - a.e2 * b.e0_e2)}
fn
left_contraction_point_point (a : point, b : point) : double =
(* This is the same as the scalar product but saves us having to add
an operator for which I cannot think of a good symbol. *)
(a.e1 * b.e1) + (a.e2 * b.e2) + (a.e0 * b.e0)
fn
dual_line (a : line) : point =
@{e1 = ~a.e0_e2,
e2 = a.e0_e1,
e0 = a.e1_e2}
overload outer_product with outer_product_point_point
overload left_contraction with left_contraction_point_line
overload left_contraction with left_contraction_point_point
overload dual with dual_line (* Orthogonal complement. *)
infixl ( * ) ^ .|
overload ^ with outer_product
overload .| with left_contraction
fn
intersection_line_line (a : line, b : line) : point =
let
val p = dual a .| b
in
if p.e0 = 0.0 then
(* The lines are parallel (or coincident, if p is all zeros). *)
p
else
(* Normalize the intersection point. *)
@{e1 = p.e1 / p.e0,
e2 = p.e2 / p.e0,
e0 = 1.0}
end
fn
which_side_point_line (a : point, b : line) : Sgn =
(* 1 = left, 0 = lies on the line, ~1 = right *)
let
val x = dual b .| a
in
if x < 0.0 then
~1
else if x > 0.0 then
1
else
0
end
overload intersection with intersection_line_line
overload which_side with which_side_point_line
fn
orientation_triangle (t : triangle) : Sgn =
(* 1 = counterclockwise, 0 = collinear, ~1 = clockwise *)
which_side (t.2, t.0 ^ t.1)
overload orientation with orientation_triangle
fn
set_orientation_triangle {s : int | abs s == 1}
(t : triangle, s : int s) : triangle =
(* 1 = counterclockwise, ~1 = clockwise. If the triangle is
collinear, leave it unchanged. If the triangle does need
rearrangement, do so by swapping vertices t.1 and t.2. *)
let
val s0 = orientation t
in
if (s = 0) + (s = s0) then
t
else
@(t.0, t.2, t.1)
end
overload set_orientation with set_orientation_triangle
fn
overlap_triangle_triangle (t1 : triangle, t2 : triangle) : bool =
let
val t1 = set_orientation (t1, 1)
and t2 = set_orientation (t2, 1)
(* The lines that form the sides of the triangles. *)
val s1 = @(t1.0 ^ t1.1, t1.1 ^ t1.2, t1.2 ^ t1.0)
val s2 = @(t2.0 ^ t2.1, t2.1 ^ t2.2, t2.2 ^ t2.0)
fn
sides_intersect (pa : point, pb : point, ln_p : line,
qa : point, qb : point, ln_q : line) : bool =
let
val x = intersection (ln_p, ln_q)
in
if x.e0 <> 0.0 then
let
val px_min = min (pa.e1, pb.e1)
and px_max = max (pa.e1, pb.e1)
and py_min = min (pa.e2, pb.e1)
and py_max = max (pa.e2, pb.e1)
val px_min2 = px_min + px_min
and px_max2 = px_max + px_max
and py_min2 = py_min + py_min
and py_max2 = py_max + py_max
val px_min_eps = abs (px_min) * dbl_epsilon
and px_max_eps = abs (px_max) * dbl_epsilon
val py_min_eps = abs (py_min) * dbl_epsilon
and py_max_eps = abs (py_max) * dbl_epsilon
in
if px_min2 - px_min_eps <= x.e1 + x.e1
&& x.e1 + x.e1 <= px_max2 + px_max_eps
&& py_min2 - py_min_eps <= x.e2 + x.e2
&& x.e2 + x.e2 <= py_max2 + py_max_eps then
let
val qx_min = min (qa.e1, qb.e1)
and qx_max = max (qa.e1, qb.e1)
and qy_min = min (qa.e2, qb.e1)
and qy_max = max (qa.e2, qb.e1)
val qx_min2 = qx_min + qx_min
and qx_max2 = qx_max + qx_max
and qy_min2 = qy_min + qy_min
and qy_max2 = qy_max + qy_max
val qx_min_eps = abs (qx_min) * dbl_epsilon
and qx_max_eps = abs (qx_max) * dbl_epsilon
val qy_min_eps = abs (qy_min) * dbl_epsilon
and qy_max_eps = abs (qy_max) * dbl_epsilon
in
qx_min2 - qx_min_eps <= x.e1 + x.e1
&& x.e1 + x.e1 <= qx_max2 + qx_max_eps
&& qy_min2 - qy_min_eps <= x.e2 + x.e2
&& x.e2 + x.e2 <= qy_max2 + qy_max_eps
end
else
false
end
else if x.e1 = 0.0 && x.e2 = 0.0 then
(* The lines are coincident *)
~(max (qa.e1, qb.e1) < min (pa.e1, pb.e1)
|| max (pa.e1, pb.e1) < min (qa.e1, qb.e1))
&& ~(max (qa.e2, qb.e2) < min (pa.e2, pb.e2)
|| max (pa.e2, pb.e2) < min (qa.e2, qb.e2))
else
(* The lines are parallel. *)
false
end
fn
sides_intersection_tests () : bool =
sides_intersect (t1.0, t1.1, s1.0, t2.0, t2.1, s2.0)
|| sides_intersect (t1.0, t1.1, s1.0, t2.1, t2.2, s2.1)
|| sides_intersect (t1.0, t1.1, s1.0, t2.2, t2.0, s2.2)
|| sides_intersect (t1.1, t1.2, s1.1, t2.0, t2.1, s2.0)
|| sides_intersect (t1.1, t1.2, s1.1, t2.1, t2.2, s2.1)
|| sides_intersect (t1.1, t1.2, s1.1, t2.2, t2.0, s2.2)
|| sides_intersect (t1.2, t1.0, s1.2, t2.0, t2.1, s2.0)
|| sides_intersect (t1.2, t1.0, s1.2, t2.1, t2.2, s2.1)
|| sides_intersect (t1.2, t1.0, s1.2, t2.2, t2.0, s2.2)
fn
points_approx_equal (p : point, q : point) : bool =
let
val @{e1 = px, e2 = py, e0 = _} = p
and @{e1 = qx, e2 = qy, e0 = _} = q
val x_max_eps = max (abs px, abs qx) * dbl_epsilon
and y_max_eps = max (abs py, abs py) * dbl_epsilon
in
abs ((px + px) - (qx + qx)) <= x_max_eps
&& abs ((py + py) - (qy + qy)) <= y_max_eps
end
fn
vertex_vertex_tests () : bool =
points_approx_equal (t1.0, t2.0)
|| points_approx_equal (t1.0, t2.1)
|| points_approx_equal (t1.0, t2.2)
|| points_approx_equal (t1.1, t2.0)
|| points_approx_equal (t1.1, t2.1)
|| points_approx_equal (t1.1, t2.2)
|| points_approx_equal (t1.2, t2.0)
|| points_approx_equal (t1.2, t2.1)
|| points_approx_equal (t1.2, t2.2)
fn
is_inside (a : point, b : @(line, line, line)) : bool =
which_side (a, b.0) = 1
&& which_side (a, b.1) = 1
&& which_side (a, b.2) = 1
fn
vertex_insideness_tests () : bool =
is_inside (t1.0, s2)
|| is_inside (t1.1, s2)
|| is_inside (t1.2, s2)
|| is_inside (t2.0, s1)
|| is_inside (t2.1, s1)
|| is_inside (t2.2, s1)
in
sides_intersection_tests ()
|| vertex_vertex_tests ()
|| vertex_insideness_tests ()
end
overload overlap with overlap_triangle_triangle
fn
println_triangle (t : triangle) : void =
println! ("(", t.0.e1, ",", t.0.e2, ")--(",
t.1.e1, ",", t.1.e2, ")--(",
t.2.e1, ",", t.2.e2, ")--cycle")
fn
test_triangles (t1 : triangle, t2 : triangle) : void =
begin
println_triangle t1;
println_triangle t2;
println! (" overlap: ", overlap (t1, t2))
end
implement
main () =
begin
println! ();
test_triangles (@(Pt (0.0, 0.0),
Pt (5.0, 0.0),
Pt (0.0, 5.0)),
@(Pt (0.0, 0.0),
Pt (5.0, 0.0),
Pt (0.0, 6.0)));
test_triangles (@(Pt (0.0, 0.0),
Pt (0.0, 5.0),
Pt (5.0, 0.0)),
@(Pt (0.0, 0.0),
Pt (0.0, 5.0),
Pt (5.0, 0.0)));
test_triangles (@(Pt (0.0, 0.0),
Pt (5.0, 0.0),
Pt (0.0, 5.0)),
@(Pt (~10.0, 0.0),
Pt ( ~5.0, 0.0),
Pt ( ~1.0, 6.0)));
test_triangles (@(Pt (0.0, 0.0),
Pt (5.0, 0.0),
Pt (2.5, 5.0)),
@(Pt (0.0, 4.0),
Pt (2.5, ~1.0),
Pt (5.0, 4.0)));
test_triangles (@(Pt (0.0, 0.0),
Pt (1.0, 1.0),
Pt (0.0, 2.0)),
@(Pt (2.0, 1.0),
Pt (3.0, 0.0),
Pt (3.0, 2.0)));
test_triangles (@(Pt (0.0, 0.0),
Pt (1.0, 1.0),
Pt (0.0, 2.0)),
@(Pt (2.0, 1.0),
Pt (3.0, ~2.0),
Pt (3.0, 4.0)));
test_triangles (@(Pt (0.0, 0.0),
Pt (1.0, 0.0),
Pt (0.0, 1.0)),
@(Pt (1.0, 0.0),
Pt (2.0, 0.0),
Pt (1.0, 1.0)));
println! ();
println! ("What follows is a test where one triangle is ",
"contained entirely");
println! ("inside the other. Without such a test, our ",
"algorithm would have");
println! ("one of its features undemonstrated.");
println! ();
test_triangles (@(Pt ( 0.0, 0.0),
Pt (10.0, 0.0),
Pt ( 5.0, 10.0)),
@(Pt ( 4.0, 1.0),
Pt ( 5.0, 2.0),
Pt ( 6.0, 1.0)));
println! ();
0
end
</syntaxhighlight>
{{out}}
<pre>$ patscc -g -O3 -march=native -pipe -std=gnu2x overlapping_triangles.dats && ./a.out
(0.000000,0.000000)--(5.000000,0.000000)--(0.000000,5.000000)--cycle
(0.000000,0.000000)--(5.000000,0.000000)--(0.000000,6.000000)--cycle
overlap: true
(0.000000,0.000000)--(0.000000,5.000000)--(5.000000,0.000000)--cycle
(0.000000,0.000000)--(0.000000,5.000000)--(5.000000,0.000000)--cycle
overlap: true
(0.000000,0.000000)--(5.000000,0.000000)--(0.000000,5.000000)--cycle
(-10.000000,0.000000)--(-5.000000,0.000000)--(-1.000000,6.000000)--cycle
overlap: false
(0.000000,0.000000)--(5.000000,0.000000)--(2.500000,5.000000)--cycle
(0.000000,4.000000)--(2.500000,-1.000000)--(5.000000,4.000000)--cycle
overlap: true
(0.000000,0.000000)--(1.000000,1.000000)--(0.000000,2.000000)--cycle
(2.000000,1.000000)--(3.000000,0.000000)--(3.000000,2.000000)--cycle
overlap: false
(0.000000,0.000000)--(1.000000,1.000000)--(0.000000,2.000000)--cycle
(2.000000,1.000000)--(3.000000,-2.000000)--(3.000000,4.000000)--cycle
overlap: false
(0.000000,0.000000)--(1.000000,0.000000)--(0.000000,1.000000)--cycle
(1.000000,0.000000)--(2.000000,0.000000)--(1.000000,1.000000)--cycle
overlap: true
What follows is a test where one triangle is contained entirely
inside the other. Without such a test, our algorithm would have
one of its features undemonstrated.
(0.000000,0.000000)--(10.000000,0.000000)--(5.000000,10.000000)--cycle
(4.000000,1.000000)--(5.000000,2.000000)--(6.000000,1.000000)--cycle
overlap: true
</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">TrianglesIntersect(T1, T2){ ; T1 := [[x1,y1],[x2,y2],[x3,y3]] , T2 :=[[x4,y4],[x5,y5],[x6,y6]]
counter := 0
for i, Pt in T1
counter += PointInTriangle(Pt, T2) ; check if any coordinate of triangle 1 is inside triangle 2
for i, Pt in T2
counter += PointInTriangle(Pt, T1) ; check if any coordinate of triangle 2 is inside triangle 1
; check if sides of triangle 1 intersect with sides of triangle 2
counter += LinesIntersect([t1.1,t1.2],[t2.1,t2.2]) ? 1 : 0
counter += LinesIntersect([t1.1,t1.3],[t2.1,t2.2]) ? 1 : 0
counter += LinesIntersect([t1.2,t1.3],[t2.1,t2.2]) ? 1 : 0
counter += LinesIntersect([t1.1,t1.2],[t2.1,t2.3]) ? 1 : 0
counter += LinesIntersect([t1.1,t1.3],[t2.1,t2.3]) ? 1 : 0
counter += LinesIntersect([t1.2,t1.3],[t2.1,t2.3]) ? 1 : 0
counter += LinesIntersect([t1.1,t1.2],[t2.2,t2.3]) ? 1 : 0
counter += LinesIntersect([t1.1,t1.3],[t2.2,t2.3]) ? 1 : 0
counter += LinesIntersect([t1.2,t1.3],[t2.2,t2.3]) ? 1 : 0
return (counter>3) ; 3 points inside or 1 point inside and 2 lines intersect or 3 lines intersect
}
PointInTriangle(pt, Tr){ ; pt:=[x,y] , Tr := [[x1,y1],[x2,y2],[x3,y3]]
v1 := Tr.1, v2 := Tr.2, v3 := Tr.3
d1 := sign(pt, v1, v2)
d2 := sign(pt, v2, v3)
d3 := sign(pt, v3, v1)
has_neg := (d1 < 0) || (d2 < 0) || (d3 < 0)
has_pos := (d1 > 0) || (d2 > 0) || (d3 > 0)
return !(has_neg && has_pos)
}
sign(p1, p2, p3){
return (p1.1 - p3.1) * (p2.2 - p3.2) - (p2.1 - p3.1) * (p1.2 - p3.2)
}
LinesIntersect(L1, L2){ ; L1 := [[x1,y1],[x2,y2]] , L2 := [[x3,y3],[x4,y4]]
x1 := L1[1,1], y1 := L1[1,2]
x2 := L1[2,1], y2 := L1[2,2]
x3 := L2[1,1], y3 := L2[1,2]
x4 := L2[2,1], y4 := L2[2,2]
x := ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4)) / ((x1-x2)*(y3-y4) - (y1-y2)*(x3-x4))
y := ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4)) / ((x1-x2)*(y3-y4) - (y1-y2)*(x3-x4))
if (x<>"" && y<>"") && isBetween(x, x1, x2) && isBetween(x, x3, x4) && isBetween(y, y1, y2) && isBetween(y, y3, y4)
return 1
}
isBetween(x, p1, p2){
return !((x>p1 && x>p2) || (x<p1 && x<p2))
}</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">result := ""
result .= TrianglesIntersect([[0,0],[5,0],[0,5]], [[0,0],[5,0],[0,6]]) "`n"
result .= TrianglesIntersect([[0,0],[0,5],[5,0]], [[0,0],[0,5],[5,0]]) "`n"
result .= TrianglesIntersect([[0,0],[5,0],[0,5]], [[-10,0],[-5,0],[-1,6]])"`n"
result .= TrianglesIntersect([[0,0],[5,0],[2.5,5]], [[0,4],[2.5,-1],[5,4]]) "`n"
result .= TrianglesIntersect([[0,0],[1,1],[0,2]], [[2,1],[3,0],[3,2]]) "`n"
result .= TrianglesIntersect([[0,0],[1,1],[0,2]], [[2,1],[3,-2],[3,4]]) "`n"
result .= TrianglesIntersect([[0,0],[1,0],[0,1]], [[1,0],[2,0],[1,1]]) "`n"
MsgBox % result
return</syntaxhighlight>
Outputs:<pre>1
1
0
1
0
0
1</pre>
=={{header|C}}==
{{trans|C++}}
<
#include <stdbool.h>
#include <stdio.h>
Line 218 ⟶ 1,092:
return EXIT_SUCCESS;
}</
{{out}}
<pre>1,true
Line 229 ⟶ 1,103:
0,false</pre>
=={{header|C
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
Line 514 ⟶ 1,256:
}
}
}</
{{out}}
<pre>Triangle: (0, 0), (5, 0), (0, 5) and
Line 549 ⟶ 1,291:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|C++}}==
<syntaxhighlight 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;}
}</syntaxhighlight>
{{out}}
<pre>1,1
1,1
0,0
1,1
0,0
0,0
1,1
0,0</pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.typecons;
Line 692 ⟶ 1,566:
writeln("which have only a single corner in contact, if boundary points do not collide");
overlap(t1, t2, 0.0, false, false);
}</
{{out}}
Line 728 ⟶ 1,602:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Determine_if_two_triangles_overlap#Pascal Pascal].
=={{header|
{{trans|C#}}
<syntaxhighlight>
func det2d t[][] .
return t[1][1] * (t[2][2] - t[3][2]) + t[2][1] * (t[3][2] - t[1][2]) + t[3][1] * (t[1][2] - t[2][2])
.
proc triwind . t[][] .
det = det2d t[][]
if det < 0
swap t[1][] t[2][]
.
.
func overlap t1[][] t2[][] .
triwind t1[][]
triwind t2[][]
for t to 2
for i to 3
j = (i + 1) mod1 3
for k to 3
if det2d [ t1[i][] t1[j][] t2[k][] ] >= 0
break 1
.
.
if k = 4
return 0
.
.
swap t1[][] t2[][]
.
return 1
.
print overlap [ [ 0 0 ] [ 5 0 ] [ 0 5 ] ] [ [ 0 0 ] [ 5 0 ] [ 0 6 ] ]
print overlap [ [ 0 0 ] [ 0 5 ] [ 5 0 ] ] [ [ 0 0 ] [ 0 5 ] [ 5 0 ] ]
print overlap [ [ 0 0 ] [ 5 0 ] [ 0 5 ] ] [ [ -10 0 ] [ -5 0 ] [ -1 6 ] ]
print overlap [ [ 0 0 ] [ 5 0 ] [ 2.5 5 ] ] [ [ 0 4 ] [ 2.5 -1 ] [ 5 4 ] ]
print overlap [ [ 0 0 ] [ 1 1 ] [ 0 2 ] ] [ [ 2 1 ] [ 3 0 ] [ 3 2 ] ]
print overlap [ [ 0 0 ] [ 1 1 ] [ 0 2 ] ] [ [ 2 1 ] [ 3 -2 ] [ 3 4 ] ]
</syntaxhighlight>
{{out}}
<pre>
1
1
0
1
0
0
</pre>
=={{header|F Sharp|F#}}==
{{trans|Kotlin}}
<
type Point = double * double
Line 829 ⟶ 1,753:
Console.WriteLine("{0} and\n{1}\nwhich have only a single corner in contact, if boundary points do not collide\n{2}", t11, t12, if TriTri2D 0.0 false false t11 t12 then "overlap" else "do not overlap")
0 // return an integer exit code</
{{out}}
<pre>((0, 0), (5, 0), (0, 5)) and
Line 864 ⟶ 1,788:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">#macro min(x,y)
Iif(x>y,y,x)
#endmacro
#macro max(x,y)
Iif(x>y,x,y)
#endmacro
type pnt 'typedef for a point
x as double
y as double
end type
type edg 'typedef for an edge
p1 as pnt
p2 as pnt
end type
function point_in_tri( r as pnt, a as pnt, b as pnt, c as pnt ) as boolean
'uses barycentric coordinates to determine whether point r is in the triangle defined by a, b, c
dim as double k = ((b.y - c.y)*(a.x - c.x) + (c.x - b.x)*(a.y - c.y))
dim as double v = ((b.y - c.y)*(r.x - c.x) + (c.x - b.x)*(r.y - c.y)) / k
dim as double w = ((c.y - a.y)*(r.x - c.x) + (a.x - c.x)*(r.y - c.y)) / k
dim as double z = 1 - v- w
if v<0 or v>1 then return false
if w<0 or w>1 then return false
if z<0 or z>1 then return false
return true
end function
function bbox_overlap( a1 as pnt, a2 as pnt, b1 as pnt, b2 as pnt) as boolean
dim as double a1x = min(a1.x, a2.x), a1y = min(a1.y, a2.y)
dim as double a2x = max(a1.x, a2.x), a2y = max(a1.y, a2.y)
dim as double b1x = min(b1.x, b2.x), b1y = min(b1.y, b2.y)
dim as double b2x = max(b1.x, b2.x), b2y = max(b1.y, b2.y)
if a1x > b2x or b1x > a2x then return false
if a1y > b2y or b2y > a2y then return false
return true
end function
function ccw( a as pnt, b as pnt, c as pnt) as double
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
end function
function line_intersect( a as edg, b as edg ) as boolean
if ccw(a.p1, a.p2, b.p1)*ccw(a.p1, a.p2, b.p2) > 0 then return false
if ccw(b.p1, b.p2, a.p1)*ccw(b.p1, b.p2, a.p2) > 0 then return false
if not bbox_overlap( a.p1, a.p2, b.p1, b.p2 ) then return false
return true
end function
function triangle_overlap( a() as pnt, b() as pnt ) as boolean
'if two triangles overlap then either a corner of one triangle is inside
'the other OR an edge of one triangle intersects an edge of the other.
dim as uinteger i, j
dim as edg c, d
for i = 0 to 2
if point_in_tri( a(i), b(0), b(1), b(2) ) then return true
if point_in_tri( b(i), a(0), a(1), a(2) ) then return true
c.p1.x = a(i).x
c.p1.y = a(i).y
c.p2.x = a((i+1) mod 3).x
c.p2.y = a((i+1) mod 3).y
for j = 0 to 2
d.p1.x = b(i).x
d.p1.y = b(i).y
d.p2.x = b((i+1) mod 3).x
d.p2.y = b((i+1) mod 3).y
if line_intersect( c, d ) then return true
next j
next i
return 00
end function
data 0,0 , 5,0 , 0,5 , 0,0 , 5,0 , 0,6
data 0,0 , 0,5 , 5,0 , 0,0 , 0,5 , 5,0
data 0,0 , 5,0 , 0,5 , -10,0 , -5,0 , -1,6
data 0,0 , 5,0 , 2.5,5 , 0,4 , 2.5,-1 , 5,4
data 0,0 , 1,1 , 0,2 , 2,1 , 3,0 , 3,2
data 0,0 , 1,1 , 0,2 , 2,1 , 3,-2 , 3,4
data 0,0 , 1,0 , 0,1 , 1,0 , 2,0 , 1,1
dim as uinteger t, i
dim as pnt a(0 to 2), b(0 to 2)
for t = 1 to 7
for i = 0 to 2
read a(i).x, a(i).y
next i
for i = 0 to 2
read b(i).x, b(i).y
next i
print triangle_overlap( a(), b() )
next t
</syntaxhighlight>
{{out}}
<pre>
true
true
false
true
false
false
true
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<
import "fmt"
Line 1,014 ⟶ 2,044:
overlapping = triTri2D(t1, t2, 0.0, false, false)
fmt.Println(iff(overlapping, "overlap", "do not overlap"))
}</
{{out}}
Line 1,020 ⟶ 2,050:
Same as Kotlin entry.
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">import java.util.function.BiFunction
class TriangleOverlap {
private static class Pair {
double first
double second
Pair(double first, double second) {
this.first = first
this.second = second
}
@Override
String toString() {
return String.format("(%s, %s)", first, second)
}
}
private static class Triangle {
Pair p1, p2, p3
Triangle(Pair p1, Pair p2, Pair p3) {
this.p1 = p1
this.p2 = p2
this.p3 = p3
}
@Override
String toString() {
return String.format("Triangle: %s, %s, %s", p1, p2, p3)
}
}
private static double det2D(Triangle t) {
Pair p1 = t.p1
Pair p2 = t.p2
Pair p3 = t.p3
return p1.first * (p2.second - p3.second) + p2.first * (p3.second - p1.second) + p3.first * (p1.second - p2.second)
}
private static void checkTriWinding(Triangle t, boolean allowReversed) {
double detTri = det2D(t)
if (detTri < 0.0) {
if (allowReversed) {
Pair a = t.p3
t.p3 = t.p2
t.p2 = a
} else throw new RuntimeException("Triangle has wrong winding direction")
}
}
private static boolean boundaryCollideChk(Triangle t, double eps) {
return det2D(t) < eps
}
private static boolean boundaryDoesntCollideChk(Triangle t, double eps) {
return det2D(t) <= eps
}
private static boolean triTri2D(Triangle t1, Triangle t2) {
return triTri2D(t1, t2, 0.0, false, true)
}
private static boolean triTri2D(Triangle t1, Triangle t2, double eps, boolean allowedReversed) {
return triTri2D(t1, t2, eps, allowedReversed, true)
}
private static boolean triTri2D(Triangle t1, Triangle t2, double eps, boolean allowedReversed, boolean onBoundary) {
// Triangles must be expressed anti-clockwise
checkTriWinding(t1, allowedReversed)
checkTriWinding(t2, allowedReversed)
// 'onBoundary' determines whether points on boundary are considered as colliding or not
BiFunction<Triangle, Double, Boolean> chkEdge = onBoundary ? TriangleOverlap.&boundaryCollideChk : TriangleOverlap.&boundaryDoesntCollideChk
Pair[] lp1 = [t1.p1, t1.p2, t1.p3]
Pair[] lp2 = [t2.p1, t2.p2, t2.p3]
// for each edge E of t1
for (int i = 0; i < 3; ++i) {
int j = (i + 1) % 3
// Check all points of t2 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (chkEdge.apply(new Triangle(lp1[i], lp1[j], lp2[0]), eps) &&
chkEdge.apply(new Triangle(lp1[i], lp1[j], lp2[1]), eps) &&
chkEdge.apply(new Triangle(lp1[i], lp1[j], lp2[2]), eps)) return false
}
// for each edge E of t2
for (int i = 0; i < 3; ++i) {
int j = (i + 1) % 3
// Check all points of t1 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (chkEdge.apply(new Triangle(lp2[i], lp2[j], lp1[0]), eps) &&
chkEdge.apply(new Triangle(lp2[i], lp2[j], lp1[1]), eps) &&
chkEdge.apply(new Triangle(lp2[i], lp2[j], lp1[2]), eps)) return false
}
// The triangles overlap
return true
}
static void main(String[] args) {
Triangle t1 = new Triangle(new Pair(0.0, 0.0), new Pair(5.0, 0.0), new Pair(0.0, 5.0))
Triangle t2 = new Triangle(new Pair(0.0, 0.0), new Pair(5.0, 0.0), new Pair(0.0, 6.0))
printf("%s and\n%s\n", t1, t2)
if (triTri2D(t1, t2)) {
println("overlap")
} else {
println("do not overlap")
}
// need to allow reversed for this pair to avoid exception
t1 = new Triangle(new Pair(0.0, 0.0), new Pair(0.0, 5.0), new Pair(5.0, 0.0))
t2 = t1
printf("\n%s and\n%s\n", t1, t2)
if (triTri2D(t1, t2, 0.0, true)) {
println("overlap (reversed)")
} else {
println("do not overlap")
}
t1 = new Triangle(new Pair(0.0, 0.0), new Pair(5.0, 0.0), new Pair(0.0, 5.0))
t2 = new Triangle(new Pair(-10.0, 0.0), new Pair(-5.0, 0.0), new Pair(-1.0, 6.0))
printf("\n%s and\n%s\n", t1, t2)
if (triTri2D(t1, t2)) {
println("overlap")
} else {
println("do not overlap")
}
t1.p3 = new Pair(2.5, 5.0)
t2 = new Triangle(new Pair(0.0, 4.0), new Pair(2.5, -1.0), new Pair(5.0, 4.0))
printf("\n%s and\n%s\n", t1, t2)
if (triTri2D(t1, t2)) {
println("overlap")
} else {
println("do not overlap")
}
t1 = new Triangle(new Pair(0.0, 0.0), new Pair(1.0, 1.0), new Pair(0.0, 2.0))
t2 = new Triangle(new Pair(2.0, 1.0), new Pair(3.0, 0.0), new Pair(3.0, 2.0))
printf("\n%s and\n%s\n", t1, t2)
if (triTri2D(t1, t2)) {
println("overlap")
} else {
println("do not overlap")
}
t2 = new Triangle(new Pair(2.0, 1.0), new Pair(3.0, -2.0), new Pair(3.0, 4.0))
printf("\n%s and\n%s\n", t1, t2)
if (triTri2D(t1, t2)) {
println("overlap")
} else {
println("do not overlap")
}
t1 = new Triangle(new Pair(0.0, 0.0), new Pair(1.0, 0.0), new Pair(0.0, 1.0))
t2 = new Triangle(new Pair(1.0, 0.0), new Pair(2.0, 0.0), new Pair(1.0, 1.1))
printf("\n%s and\n%s\n", t1, t2)
println("which have only a single corner in contact, if boundary points collide")
if (triTri2D(t1, t2)) {
println("overlap")
} else {
println("do not overlap")
}
printf("\n%s and\n%s\n", t1, t2)
println("which have only a single corner in contact, if boundary points do not collide")
if (triTri2D(t1, t2, 0.0, false, false)) {
println("overlap")
} else {
println("do not overlap")
}
}
}</syntaxhighlight>
{{out}}
<pre>Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 6.0)
overlap
Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0) and
Triangle: (0.0, 0.0), (0.0, 5.0), (5.0, 0.0)
overlap (reversed)
Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle: (-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0)
do not overlap
Triangle: (0.0, 0.0), (5.0, 0.0), (2.5, 5.0) and
Triangle: (0.0, 4.0), (2.5, -1.0), (5.0, 4.0)
overlap
Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, 0.0), (3.0, 2.0)
do not overlap
Triangle: (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle: (2.0, 1.0), (3.0, -2.0), (3.0, 4.0)
do not overlap
Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points collide
overlap
Triangle: (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle: (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|Haskell}}==
Uses the solution of the task [[Find_if_a_point_is_within_a_triangle#Haskell]]
<syntaxhighlight lang="haskell">isOverlapping :: Triangle Double -> Triangle Double -> Bool
isOverlapping t1 t2 = vertexInside || midLineInside
where
vertexInside =
any (isInside t1) (vertices t2) ||
any (isInside t2) (vertices t1)
isInside t = (Outside /=) . overlapping t
midLineInside =
any (\p -> isInside t1 p && isInside t2 p) midPoints
midPoints =
[ intersections l1 l2 | l1 <- midLines t1
, l2 <- midLines t2 ]
intersections (a1,b1,c1) (a2,b2,c2) =
( -(-b2*c1+b1*c2)/(a2*b1-a1*b2)
, -(a2*c1-a1*c2)/(a2*b1-a1*b2) )
midLines (Triangle a b c) =
[line a b c, line b c a, line c a b]
line (x,y) (ax, ay) (bx, by) =
(ay+by-2*y, -ax-bx+2*x, -ay*x-by*x+ax*y+bx*y)
test = map (uncurry isOverlapping)
[ (Triangle (0,0) (5,0) (0,5), Triangle (0,0) (5,0) (0,6))
, (Triangle (0,0) (0,5) (5,0), Triangle (0,0) (0,5) (5,0))
, (Triangle (0,0) (5,0) (0,5), Triangle (-10,0) (-5,0) (-1,6))
, (Triangle (0,0) (5,0) (2.5,5), Triangle (0,4) (2.5,-1) (5,4))
, (Triangle (0,0) (1,1) (0,2), Triangle (2,1) (3,0) (3,2))
, (Triangle (0,0) (1,1) (0,2), Triangle (2,1) (3,-2) (3,4))
, (Triangle (0,0) (1,0) (0,1), Triangle (1,0) (2,0) (1,1))]</syntaxhighlight>
<pre>λ> test
[True,True,False,True,False,False,True]</pre>
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|8}}
<
public class TriangleOverlap {
Line 1,199 ⟶ 2,481:
}
}
}</
{{out}}
<pre>Triangle: (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Line 1,234 ⟶ 2,516:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight 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 ;</syntaxhighlight>
'''The Task'''
<syntaxhighlight 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</syntaxhighlight>
{{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}}==
{{trans|Python}}
'''Module''':
<
using LinearAlgebra
Line 1,289 ⟶ 2,728:
end
end # module Triangles</
'''Main''':
<
t1 = [0 0; 5 0; 0 5]
Line 1,326 ⟶ 2,765:
t1 = [0 0; 1 0; 0 1]
t2 = [1 0; 2 0; 1 1]
@show Triangles.overlap(t1, t2, MildCheck())</
{{out}}
Line 1,340 ⟶ 2,779:
=={{header|Kotlin}}==
{{trans|C++}}
<
typealias Point = Pair<Double, Double>
Line 1,445 ⟶ 2,884:
println("which have only a single corner in contact, if boundary points do not collide")
println(if (triTri2D(t1, t2, 0.0, false, false)) "overlap" else "do not overlap")
}</
{{out}}
Line 1,483 ⟶ 2,922:
do not overlap
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
Here we present a rasterized version based on a single function "isInside".
1) isInside
Given A, B, C, P is in the triangle ABC if the three cross-products
PA^PB, PB^PC and PC^PA are of equal sign.
{def isInside
{lambda {:a :b :c :p}
{let { {:ax {car :a}} {:ay {cdr :a}}
{:bx {car :b}} {:by {cdr :b}}
{:cx {car :c}} {:cy {cdr :c}}
{:px {car :p}} {:py {cdr :p}}
} {let { {:w1 {- {* {- :px :ax} {- :cy :ay}}
{* {- :cx :ax} {- :py :ay}} }}
{:w2 {- {* {- :px :bx} {- :ay :by}}
{* {- :ax :bx} {- :py :by}} }}
{:w3 {- {* {- :px :cx} {- :by :cy}}
{* {- :bx :cx} {- :py :cy}} }}
} {or {and {>= :w1 0} {>= :w2 0} {>= :w3 0}}
{and {< :w1 0} {< :w2 0} {< :w3 0}}} }}}}
-> isInside
2) overlapping
For every points in the rectangle surrounding two given triangles
we compute the number of points inside both. If it is null they don't overlap.
{def overlap
{def overlap.row
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h :y}
{S.map {{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :qp}
{if {and {isInside :p0 :p1 :p2 :qp}
{isInside :q0 :q1 :q2 :qp}}
then x else}} :p0 :p1 :p2 :q0 :q1 :q2}
{S.map {{lambda {:y :x} {cons :x :y}} :y}
{S.serie :w :h} }}}}
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.length {S.map {overlap.row :p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.serie :w :h}} }}}
-> overlap
Given coordonnees will just be scaled to become integers, here miltiplied by 10
{overlap {cons 0 0} {cons 50 0} {cons 0 50}
{cons 0 0} {cons 50 0} {cons 0 60} 0 60} -> 1326
{overlap {cons 0 0} {cons 0 50} {cons 50 0}
{cons 0 0} {cons 0 50} {cons 50 0} 0 50} -> 1176
{overlap {cons 0 0} {cons 50 0} {cons 0 50}
{cons -100 0} {cons -50 0} {cons -10 60} 100 60} -> 0
{overlap {cons 0 0} {cons 50 0} {cons 25 50}
{cons 0 40} {cons 25 -10} {cons 50 40} -10 50} -> 831
{overlap {cons 0 0} {cons 10 10} {cons 0 20}
{cons 20 10} {cons 30 0} {cons 30 20} 0 20} -> 0
{overlap {cons 0 0} {cons 10 10} {cons 0 20}
{cons 20 10} {cons 30 -20} {cons 40 40} -20 40} -> 0
{overlap {cons 0 0} {cons 10 0} {cons 0 10}
{cons 10 0} {cons 20 0} {cons 10 10} 0 20} -> 1
3) plot
The first triangle is plotted with 1s, the second with 2s,
the intersection with 3s, else with dots.
{def plot
{def plot.row
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h :y}
{br}{S.replace \s by in
{S.map {{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :qp}
{let { {:isinp {isInside :p0 :p1 :p2 :qp}}
{:isinq {isInside :q0 :q1 :q2 :qp}}
} {if {and :isinp :isinq} then 3
else {if :isnp then 1
else {if :isnq then 2
else .}}} }} :p0 :p1 :p2 :q0 :q1 :q2}
{S.map {{lambda {:y :x} {cons :x :y}} :y}
{S.serie :w :h} }}} }}
{lambda {:p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.map {plot.row :p0 :p1 :p2 :q0 :q1 :q2 :w :h}
{S.serie :w :h}} }}
-> plot
{plot {cons 0 0} {cons 30 0} {cons 30 30}
{cons 5 10} {cons 25 10} {cons 5 25} 0 30}
->
1111111111111111111111111111111
.111111111111111111111111111111
..11111111111111111111111111111
...1111111111111111111111111111
....111111111111111111111111111
.....11111111111111111111111111
......1111111111111111111111111
.......111111111111111111111111
........11111111111111111111111
.........1111111111111111111111
.....22222333333333333333311111
.....22222233333333333331111111
.....22222223333333333311111111
.....22222222333333333111111111
.....22222222233333311111111111
.....22222222223333111111111111
.....22222222222331111111111111
.....22222222222.11111111111111
.....2222222222...1111111111111
.....222222222.....111111111111
.....2222222........11111111111
.....222222..........1111111111
.....22222............111111111
.....222...............11111111
.....22.................1111111
.....2...................111111
..........................11111
...........................1111
............................111
.............................11
..............................1
</syntaxhighlight>
=={{header|Lua}}==
{{trans|C++}}
<
return p1.x * (p2.y - p3.y)
+ p2.x * (p3.y - p1.y)
Line 1,625 ⟶ 3,193:
print(formatTri(t1).." and")
print(formatTri(t2))
print(overlap(t1,t2,0.0,false,false))</
{{out}}
<pre>Triangle: (0, 0), (5, 0), (0, 5) and
Line 1,658 ⟶ 3,226:
Triangle: (1, 0), (2, 0), (1, 1)
overlap</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">p1 = Polygon@{{0, 0}, {5, 0}, {0, 5}};
p2 = Polygon@{{0, 0}, {5, 0}, {0, 6}};
! RegionDisjoint[p1, p2]
p1 = Polygon@{{0, 0}, {0, 5}, {5, 0}};
p2 = Polygon@{{0, 0}, {0, 5}, {5, 0}};
! RegionDisjoint[p1, p2]
p1 = Polygon@{{0, 0}, {5, 0}, {0, 5}};
p2 = Polygon@{{-10, 0}, {-5, 0}, {-1, 6}};
! RegionDisjoint[p1, p2]
p1 = Polygon@{{0, 0}, {5, 0}, {2.5, 5}};
p2 = Polygon@{{0, 4}, {2.5, -1}, {5, 4}};
! RegionDisjoint[p1, p2]
p1 = Polygon@{{0, 0}, {1, 1}, {0, 2}};
p2 = Polygon@{{2, 1}, {3, 0}, {3, 2}};
! RegionDisjoint[p1, p2]
p1 = Polygon@{{0, 0}, {1, 1}, {0, 2}};
p2 = Polygon@{{2, 1}, {3, -2}, {3, 4}};
! RegionDisjoint[p1, p2]
p1 = Polygon@{{0, 0}, {1, 0}, {0, 1}};
p2 = Polygon@{{1, 0}, {2, 0}, {1, 1}};
! RegionDisjoint[p1, p2]</syntaxhighlight>
{{out}}
<pre>True
True
False
True
False
False
True</pre>
=={{header|Modula-2}}==
<
FROM EXCEPTIONS IMPORT AllocateSource,ExceptionSource,GetMessage,RAISE;
FROM LongStr IMPORT RealToFixed;
Line 1,845 ⟶ 3,451:
ReadChar
END Overlap.</
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import strformat
type Point = tuple[x, y: float]
type Triangle = array[3, Point]
func `$`(p: Point): string =
fmt"({p.x:.1f}, {p.y:.1f})"
func `$`(t: Triangle): string =
fmt"Triangle {t[0]}, {t[1]}, {t[2]}"
func det2D(t: Triangle): float =
t[0].x * (t[1].y - t[2].y) +
t[1].x * (t[2].y - t[0].y) +
t[2].x * (t[0].y - t[1].y)
func checkTriWinding(t: var Triangle; allowReversed: bool) =
let det = t.det2D()
if det < 0:
if allowReversed:
swap t[1], t[2]
else:
raise newException(ValueError, "Triangle has wrong winding direction.")
func boundaryCollideChk(t: Triangle; eps: float): bool =
t.det2D() < eps
func boundaryDoesntCollideChk(t: Triangle; eps: float): bool =
t.det2D() <= eps
func triTri2D(t1, t2: var Triangle; eps = 0.0;
allowReversed = false; onBoundary = true): bool =
# Triangles must be expressed anti-clockwise.
t1.checkTriWinding(allowReversed)
t2.checkTriWinding(allowReversed)
# "onBoundary" determines whether points on boundary are considered as colliding or not.
let chkEdge = if onBoundary: boundaryCollideChk else: boundaryDoesntCollideChk
# For each edge E of t1.
for i in 0..2:
let j = (i + 1) mod 3
# Check that all points of t2 lay on the external side of edge E.
# If they do, the triangles do not overlap.
if chkEdge([t1[i], t1[j], t2[0]], eps) and
chkEdge([t1[i], t1[j], t2[1]], eps) and
chkEdge([t1[i], t1[j], t2[2]], eps):
return false
# For each edge E of t2.
for i in 0..2:
let j = (i + 1) mod 3
# Check that all points of t1 lay on the external side of edge E.
# If they do, the triangles do not overlap.
if chkEdge([t2[i], t2[j], t1[0]], eps) and
chkEdge([t2[i], t2[j], t1[1]], eps) and
chkEdge([t2[i], t2[j], t1[2]], eps):
return false
# The triangles overlap.
result = true
when isMainModule:
var t1: Triangle = [(0.0, 0.0), (5.0, 0.0), (0.0, 5.0)]
var t2: Triangle = [(0.0, 0.0), (5.0, 0.0), (0.0, 6.0)]
echo t1, " and\n", t2
var overlapping = triTri2D(t1, t2, 0, false, true)
echo if overlapping: "overlap\n" else: "do not overlap\n"
# Need to allow reversed for this pair to avoid exception.
t1 = [(0.0, 0.0), (5.0, 0.0), (5.0, 0.0)]
t2 = t1
echo t1, " and\n", t2
overlapping = triTri2D(t1, t2, 0, true, true)
echo if overlapping: "overlap (reversed)\n" else: "do not overlap\n"
t1 = [(0.0, 0.0), (5.0, 0.0), (0.0, 5.0)]
t2 = [(-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0)]
echo t1, " and\n", t2
overlapping = triTri2D(t1, t2, 0, false, true)
echo if overlapping: "overlap\n" else: "do not overlap\n"
t1[2] = (2.5, 5.0)
t2 = [(0.0, 4.0), (2.5, -1.0), (5.0, 4.0)]
echo t1, " and\n", t2
overlapping = triTri2D(t1, t2, 0, false, true)
echo if overlapping: "overlap\n" else: "do not overlap\n"
t1 = [(0.0, 0.0), (1.0, 1.0), (0.0, 2.0)]
t2 = [(2.0, 1.0), (3.0, 0.0), (3.0, 2.0)]
echo t1, " and\n", t2
overlapping = triTri2D(t1, t2, 0, false, true)
echo if overlapping: "overlap\n" else: "do not overlap\n"
t2 = [(2.0, 1.0), (3.0, -2.0), (3.0, 4.0)]
echo t1, " and\n", t2
overlapping = triTri2D(t1, t2, 0, false, true)
echo if overlapping: "overlap\n" else: "do not overlap\n"
t1 = [(0.0, 0.0), (1.0, 0.0), (0.0, 1.0)]
t2 = [(1.0, 0.0), (2.0, 0.0), (1.0, 1.1)]
echo t1, " and\n", t2
echo "which have only a single corner in contact, if boundary points collide"
overlapping = triTri2D(t1, t2, 0, false, true)
echo if overlapping: "overlap\n" else: "do not overlap\n"
echo t1, " and\n", t2
echo "which have only a single corner in contact, if boundary points do not collide"
overlapping = triTri2D(t1, t2, 0, false, false)
echo if overlapping: "overlap\n" else: "do not overlap\n"</syntaxhighlight>
{{out}}
<pre>Triangle (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle (0.0, 0.0), (5.0, 0.0), (0.0, 6.0)
overlap
Triangle (0.0, 0.0), (5.0, 0.0), (5.0, 0.0) and
Triangle (0.0, 0.0), (5.0, 0.0), (5.0, 0.0)
overlap (reversed)
Triangle (0.0, 0.0), (5.0, 0.0), (0.0, 5.0) and
Triangle (-10.0, 0.0), (-5.0, 0.0), (-1.0, 6.0)
do not overlap
Triangle (0.0, 0.0), (5.0, 0.0), (2.5, 5.0) and
Triangle (0.0, 4.0), (2.5, -1.0), (5.0, 4.0)
overlap
Triangle (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle (2.0, 1.0), (3.0, 0.0), (3.0, 2.0)
do not overlap
Triangle (0.0, 0.0), (1.0, 1.0), (0.0, 2.0) and
Triangle (2.0, 1.0), (3.0, -2.0), (3.0, 4.0)
do not overlap
Triangle (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points collide
overlap
Triangle (0.0, 0.0), (1.0, 0.0), (0.0, 1.0) and
Triangle (1.0, 0.0), (2.0, 0.0), (1.0, 1.1)
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|ooRexx}}==
<
* Determine if two triangles overlap
* Fully (?) tested with integer coordinates of the 6 corners
* This was/is an exercise with ooRexx
* Removed the fraction arithmetic
* add test for triangles' validity
*-------------------------------------------------------------------*/
Parse Version v
oid='trioo.txt'; 'erase' oid
Call o v
Line 1,871 ⟶ 3,629:
Call trio_test '0 0 1 1 0 2 2 1 3 -2 3 4'
Call trio_test '0 0 1 0 0 1 1 0 2 0 1 1'
Call trio_test '0 0 0 0 2 2 1 1 2 1 1 2' -- two points are identical
Call trio_test '0 0 0 3 2 2 1 1 2 2 3 3' -- three points on a line
Exit
/* Other test cases */
Line 1,904 ⟶ 3,664:
tlist=space(tlist)
tl1=tlist ; Call trio_t tl1
If result=-1 Then Return
tl2=reversex(tlist) ; Call trio_t tl2
tl3=''
Line 1,914 ⟶ 3,675:
tl4=reversex(tl3) ; Call trio_t tl4
tl5=subword(tl4,7) subword(tl4,1,6) ; Call trio_t tl5
tl6=''
tl=tlist
Do While tl<>''
Parse Var tl x y tl
tl6=tl6 y x
End
Call trio_t tl6
Return
Line 1,920 ⟶ 3,687:
Parse Arg tlist
tlist=space(tlist)
Say '>' tlist
case+=1
Parse Arg ax ay bx by cx cy dx dy ex ey fx fy
Line 1,928 ⟶ 3,695:
a=.point~new(ax,ay); b=.point~new(bx,by); c=.point~new(cx,cy)
d=.point~new(dx,dy); e=.point~new(ex,ey); f=.point~new(fx,fy)
If area(a,b,c)=0 Then Do
Say a b c 'is not a valid triangle'
Return -1
End
If area(d,e,f)=0 Then Do
Say d e f 'is not a valid triangle'
Return -1
End
abc=.triangle~new(a,b,c)
def=.triangle~new(d,e,f)
Line 2,132 ⟶ 3,907:
expose point edge
use arg p1,p2,p3
If area(p1,p2,p3)=0 Then Do
Say p1 p2 p3 'is not a valid triangle!'
Return .nil
End
point=.array~new
point[1]=p1
Line 2,394 ⟶ 4,173:
res=res word(list,i)
End
Return res
::ROUTINE distpp PUBLIC --Compute the distance between the points A and B
/***********************************************************************
* Compute the distance between the points A and B
***********************************************************************/
Use Arg A,B
ax=A~x; ay=A~y; bx=B~x; by=B~y
res=rxCalcsqrt((bx-ax)**2+(by-ay)**2)
Return res
::ROUTINE area PUBLIC --Compute the area of the triangla A B C
/***********************************************************************
* Compute the area of the triangla A B C
***********************************************************************/
Use Arg A,B,C
ax=A~x; ay=A~y; bx=B~x; by=B~y; cx=C~x; cy=C~y
ab=distpp(A,B)
bc=distpp(B,C)
ca=distpp(C,A)
s=(ab+bc+ca)/2
area=rxCalcsqrt(s*(s-ab)*(s-bc)*(s-ca))
Return area
::REQUIRES rxMath Library</syntaxhighlight>
{{out}}
<pre> 0 0 4 0 0 4 1 1 2 1 1 2
Triangle: ABC: (0,0) (4,0) (0,4)
Triangle: DEF: (1,1) (2,1) (1,2)
(1,1) (2,1) (1,2) is fully contained in (0,0) (4,0) (0,4)
> 2 1 1 2 1 1 4 0 0 4 0 0
Triangle: ABC: (2,1) (1,2) (1,1)
Triangle: DEF: (4,0) (0,4) (0,0)
(2,1) (1,2) (1,1) is fully contained in (4,0) (0,4) (0,0)
> 1 2 2 1 1 1 0 4 4 0 0 0
Triangle: ABC: (1,2) (2,1) (1,1)
Triangle: DEF: (0,4) (4,0) (0,0)
(1,2) (2,1) (1,1) is fully contained in (0,4) (4,0) (0,0)
> 0 0 0 4 4 0 1 1 1 2 2 1
Triangle: ABC: (0,0) (0,4) (4,0)
Triangle: DEF: (1,1) (1,2) (2,1)
(1,1) (1,2) (2,1) is fully contained in (0,0) (0,4) (4,0)
> 1 1 1 2 2 1 0 0 0 4 4 0
Triangle: ABC: (1,1) (1,2) (2,1)
Triangle: DEF: (0,0) (0,4) (4,0)
(1,1) (1,2) (2,1) is fully contained in (0,0) (0,4) (4,0)
Triangle: ABC: (
Triangle: DEF: (
(1,1) (
> 0 0 0 6 8 3 8 0 8 8 0 3
Triangle: ABC: (0,0) (0,6) (8,3)
Triangle: DEF: (8,0) (8,8) (0,3)
Corner(s) that touch the other triangle: (0,3) (8,3)
Triangles overlap and touch on (0,3) (8,3)
> 3 0 8 8 0 8 3 8 6 0 0 0
Triangle: ABC: (3,0) (8,8) (0,8)
Triangle: DEF: (3,8) (6,0) (0,0)
Corner(s) that touch the other triangle: (3,8) (3,0)
Triangles overlap and touch on (3,8) (3,0)
> 0 3 8 8 8 0 8 3 0 6 0 0
Triangle: ABC: (0,3) (8,8) (8,0)
Triangle: DEF: (8,3) (0,6) (0,0)
Corner(s) that touch the other triangle: (8,3) (0,3)
Triangles overlap and touch on (8,3) (0,3)
> 0 0 6 0 3 8 0 8 8 8 3 0
Triangle: ABC: (0,0) (6,0) (3,8)
Triangle: DEF: (0,8) (8,8) (3,0)
Corner(s) that touch the other triangle: (3,0) (3,8)
Triangles overlap and touch on (3,0) (3,8)
> 0 8 8 8 3 0 0 0 6 0 3 8
Triangle: ABC: (0,8) (8,8) (3,0)
Triangle: DEF: (0,0) (6,0) (3,8)
Corner(s) that touch the other triangle: (3,8) (3,0)
Triangles overlap and touch on (3,8) (3,0)
Triangle: ABC: (
Triangle: DEF: (0,
Corner(s) that touch the other triangle: (
Triangles overlap and touch on (
> 0 0 0 2 2 0 0 0 4 0 0 6
Triangle: ABC: (0,0) (0,2) (2,0)
Triangle: DEF: (0,0) (4,0) (0,6)
Line 2,462 ⟶ 4,264:
Triangles overlap and touch on (0,0) (0,2) (2,0)
> 6 0 0 4 0 0 0 2 2 0 0 0
Triangle: ABC: (6,0) (0,4) (0,0)
Triangle: DEF: (0,2) (2,0) (0,0)
Line 2,468 ⟶ 4,270:
Triangles overlap and touch on (0,2) (2,0) (0,0)
> 0 6 4 0 0 0 2 0 0 2 0 0
Triangle: ABC: (0,6) (4,0) (0,0)
Triangle: DEF: (2,0) (0,2) (0,0)
Line 2,474 ⟶ 4,276:
Triangles overlap and touch on (2,0) (0,2) (0,0)
> 0 0 2 0 0 2 0 0 0 4 6 0
Triangle: ABC: (0,0) (2,0) (0,2)
Triangle: DEF: (0,0) (0,4) (6,0)
Line 2,480 ⟶ 4,282:
Triangles overlap and touch on (0,0) (2,0) (0,2)
> 0 0 0 4 6 0 0 0 2 0 0 2
Triangle: ABC: (0,0) (0,4) (6,0)
Triangle: DEF: (0,0) (2,0) (0,2)
Line 2,486 ⟶ 4,288:
Triangles overlap and touch on (0,0) (2,0) (0,2)
> 0 0
Triangle: ABC: (0,0) (
Triangle: DEF: (0,0) (0,
Corner(s) that touch the other triangle: (0,0) (
Triangles overlap and touch on (0,0) (
> 0 0 5 0 0 5 0 0 5 0 0 6
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (0,0) (5,0) (0,6)
Line 2,498 ⟶ 4,300:
Triangles have an edge in common: (0,0) (5,0)
> 6 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC: (6,0) (0,5) (0,0)
Triangle: DEF: (5,0) (0,5) (0,0)
Line 2,504 ⟶ 4,306:
Triangles have an edge in common: (0,5) (0,0)
> 0 6 5 0 0 0 0 5 5 0 0 0
Triangle: ABC: (0,6) (5,0) (0,0)
Triangle: DEF: (0,5) (5,0) (0,0)
Line 2,510 ⟶ 4,312:
Triangles have an edge in common: (5,0) (0,0)
> 0 0 0 5 5 0 0 0 0 5 6 0
Triangle: ABC: (0,0) (0,5) (5,0)
Triangle: DEF: (0,0) (0,5) (6,0)
Line 2,516 ⟶ 4,318:
Triangles have an edge in common: (0,0) (0,5)
> 0 0 0 5 6 0 0 0 0 5 5 0
Triangle: ABC: (0,0) (0,5) (6,0)
Triangle: DEF: (0,0) (0,5) (5,0)
Line 2,522 ⟶ 4,324:
Triangles have an edge in common: (0,0) (0,5)
Triangle: ABC: (0,0) (5,0
Triangle: DEF: (0,0) (
Corner(s) that touch the other triangle: (0,0) (
Triangles have an edge in common: (0,0) (
> 0 0 0 5 5 0 0 0 0 5 5 0
Triangle: ABC: (0,0) (0,5) (5,0)
Triangle: DEF: (0,0) (0,5) (5,0)
Line 2,534 ⟶ 4,336:
Triangles are identical
> 0 5 5 0 0 0 0 5 5 0 0 0
Triangle: ABC: (0,5) (5,0) (0,0)
Triangle: DEF: (0,5) (5,0) (0,0)
Line 2,540 ⟶ 4,342:
Triangles are identical
> 5 0 0 5 0 0 5 0 0 5 0 0
Triangle: ABC: (5,0) (0,5) (0,0)
Triangle: DEF: (5,0) (0,5) (0,0)
Line 2,546 ⟶ 4,348:
Triangles are identical
> 0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (0,0) (5,0) (0,5)
Line 2,552 ⟶ 4,354:
Triangles are identical
> 0 0 5 0 0 5 0 0 5 0 0 5
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (0,0) (5,0) (0,5)
Line 2,558 ⟶ 4,360:
Triangles are identical
Triangle: ABC: (0,0) (
Triangle: DEF: (0,0) (
Corner(s) that touch the other triangle: (0,0) (
Triangles are identical
> 0 0 5 0 0 5 -10 0 -5 0 -1 6
Triangle: ABC: (0,0) (5,0) (0,5)
Triangle: DEF: (-10,0) (-5,0) (-1,6)
(0,0) (5,0) (0,5) and (-10,0) (-5,0) (-1,6) don't overlap
> 6 -1 0 -5 0 -10 5 0 0 5 0 0
Triangle: ABC: (6,-1) (0,-5) (0,-10)
Triangle: DEF: (5,0) (0,5) (0,0)
(6,-1) (0,-5) (0,-10) and (5,0) (0,5) (0,0) don't overlap
> -1 6 -5 0 -10 0 0 5 5 0 0 0
Triangle: ABC: (-1,6) (-5,0) (-10,0)
Triangle: DEF: (0,5) (5,0) (0,0)
(-1,6) (-5,0) (-10,0) and (0,5) (5,0) (0,0) don't overlap
> 0 0 0 5 5 0 0 -10 0 -5 6 -1
Triangle: ABC: (0,0) (0,5) (5,0)
Triangle: DEF: (0,-10) (0,-5) (6,-1)
(0,0) (0,5) (5,0) and (0,-10) (0,-5) (6,-1) don't overlap
> 0 -10 0 -5 6 -1 0 0 0 5 5 0
Triangle: ABC: (0,-10) (0,-5) (6,-1)
Triangle: DEF: (0,0) (0,5) (5,0)
(0,-10) (0,-5) (6,-1) and (0,0) (0,5) (5,0) don't overlap
Triangle: ABC: (
Triangle: DEF: (0,
(
> 0 0 5 0 2.5 5 0 4 2.5 -1 5 4
Triangle: ABC: (0,0) (5,0) (2.5,5)
Triangle: DEF: (0,4) (2.5,-1) (5,4)
(0,0) (5,0) (2.5,5) and (0,4) (2.5,-1) (5,4) overlap
> 4 5 -1 2.5 4 0 5 2.5 0 5 0 0
Triangle: ABC: (4,5) (-1,2.5) (4,0)
Triangle: DEF: (5,2.5) (0,5) (0,0)
(4,5) (-1,2.5) (4,0) and (5,2.5) (0,5) (0,0) overlap
> 5 4 2.5 -1 0 4 2.5 5 5 0 0 0
Triangle: ABC: (5,4) (2.5,-1) (0,4)
Triangle: DEF: (2.5,5) (5,0) (0,0)
(5,4) (2.5,-1) (0,4) and (2.5,5) (5,0) (0,0) overlap
> 0 0 0 5 5 2.5 4 0 -1 2.5 4 5
Triangle: ABC: (0,0) (0,5) (5,2.5)
Triangle: DEF: (4,0) (-1,2.5) (4,5)
(0,0) (0,5) (5,2.5) and (4,0) (-1,2.5) (4,5) overlap
> 4 0 -1 2.5 4 5 0 0 0 5 5 2.5
Triangle: ABC: (4,0) (-1,2.5) (4,5)
Triangle: DEF: (0,0) (0,5) (5,2.5)
(4,0) (-1,2.5) (4,5) and (0,0) (0,5) (5,2.5) overlap
Triangle: ABC: (0,
Triangle: DEF: (
(0,
> 0 0 1 1 0 2 2 1 3 0 3 2
Triangle: ABC: (0,0) (1,1) (0,2)
Triangle: DEF: (2,1) (3,0) (3,2)
(0,0) (1,1) (0,2) and (2,1) (3,0) (3,2) don't overlap
> 2 3 0 3 1 2 2 0 1 1 0 0
Triangle: ABC: (2,3) (0,3) (1,2)
Triangle: DEF: (2,0) (1,1) (0,0)
(2,3) (0,3) (1,2) and (2,0) (1,1) (0,0) don't overlap
> 3 2 3 0 2 1 0 2 1 1 0 0
Triangle: ABC: (3,2) (3,0) (2,1)
Triangle: DEF: (0,2) (1,1) (0,0)
(3,2) (3,0) (2,1) and (0,2) (1,1) (0,0) don't overlap
> 0 0 1 1 2 0 1 2 0 3 2 3
Triangle: ABC: (0,0) (1,1) (2,0)
Triangle: DEF: (1,2) (0,3) (2,3)
(0,0) (1,1) (2,0) and (1,2) (0,3) (2,3) don't overlap
> 1 2 0 3 2 3 0 0 1 1 2 0
Triangle: ABC: (1,2) (0,3) (2,3)
Triangle: DEF: (0,0) (1,1) (2,0)
(1,2) (0,3) (2,3) and (0,0) (1,1) (2,0) don't overlap
Triangle: ABC: (
Triangle: DEF: (
(
> 0 0 1 1 0 2 2 1 3 -2 3 4
Triangle: ABC: (0,0) (1,1) (0,2)
Triangle: DEF: (2,1) (3,-2) (3,4)
(0,0) (1,1) (0,2) and (2,1) (3,-2) (3,4) don't overlap
> 4 3 -2 3 1 2 2 0 1 1 0 0
Triangle: ABC: (4,3) (-2,3) (1,2)
Triangle: DEF: (2,0) (1,1) (0,0)
(4,3) (-2,3) (1,2) and (2,0) (1,1) (0,0) don't overlap
> 3 4 3 -2 2 1 0 2 1 1 0 0
Triangle: ABC: (3,4) (3,-2) (2,1)
Triangle: DEF: (0,2) (1,1) (0,0)
(3,4) (3,-2) (2,1) and (0,2) (1,1) (0,0) don't overlap
> 0 0 1 1 2 0 1 2 -2 3 4 3
Triangle: ABC: (0,0) (1,1) (2,0)
Triangle: DEF: (1,2) (-2,3) (4,3)
(0,0) (1,1) (2,0) and (1,2) (-2,3) (4,3) don't overlap
> 1 2 -2 3 4 3 0 0 1 1 2 0
Triangle: ABC: (1,2) (-2,3) (4,3)
Triangle: DEF: (0,0) (1,1) (2,0)
(1,2) (-2,3) (4,3) and (0,0) (1,1) (2,0) don't overlap
Triangle: ABC: (
Triangle: DEF: (
(
> 0 0 1 0 0 1 1 0 2 0 1 1
Triangle: ABC: (0,0) (1,0) (0,1)
Triangle: DEF: (1,0) (2,0) (1,1)
Line 2,692 ⟶ 4,494:
(0,0) (1,0) (0,1) and (1,0) (2,0) (1,1) don't overlap but touch on (1,0)
> 1 1 0 2 0 1 1 0 0 1 0 0
Triangle: ABC: (1,1) (0,2) (0,1)
Triangle: DEF: (1,0) (0,1) (0,0)
Line 2,700 ⟶ 4,502:
(1,1) (0,2) (0,1) and (1,0) (0,1) (0,0) don't overlap but touch on (0,1)
> 1 1 2 0 1 0 0 1 1 0 0 0
Triangle: ABC: (1,1) (2,0) (1,0)
Triangle: DEF: (0,1) (1,0) (0,0)
Line 2,708 ⟶ 4,510:
(1,1) (2,0) (1,0) and (0,1) (1,0) (0,0) overlap and touch on (1,0)
> 0 0 0 1 1 0 0 1 0 2 1 1
Triangle: ABC: (0,0) (0,1) (1,0)
Triangle: DEF: (0,1) (0,2) (1,1)
Line 2,716 ⟶ 4,518:
(0,0) (0,1) (1,0) and (0,1) (0,2) (1,1) don't overlap but touch on (0,1)
> 0 1 0 2 1 1 0 0 0 1 1 0
Triangle: ABC: (0,1) (0,2) (1,1)
Triangle: DEF: (0,0) (0,1) (1,0)
Line 2,724 ⟶ 4,526:
(0,1) (0,2) (1,1) and (0,0) (0,1) (1,0) don't overlap but touch on (0,1)
Triangle: ABC: (
Triangle: DEF: (0,
Corner(s) that touch the other triangle: (
Triangles touch on (
we analyze further
(
> 0 0 0 0 2 2 1 1 2 1 1 2
(0,0) (0,0) (2,2) is not a valid triangle
> 0 0 0 3 2 2 1 1 2 2 3 3
(1,1) (2,2) (3,3) is not a valid triangle</pre>
=={{header|Pascal}}==
A console application in Free Pascal, created with the Lazarus IDE. It recognizes three possible outcomes: disjoint, positive overlap, and borderline (overlap at a point or line segment).
<syntaxhighlight lang="pascal">
program TrianglesOverlap;
{
The program looks for a separating line between the triangles. It's known that
only the triangle sides (produced) need to be considered as possible separators
(except in the degenerate case when both triangles are reduced to a point).
If there's a strong separator, i.e. one that is disjoint from at least one
of the triangles, then the triangles are disjoint. If there's only a weak
separator, i.e. one that intersects both triangles, then the triangles intersect
in a point or a line segment (this program doesn't work out which).
If there's no separator, then the triangles have an overlap of positive area.
}
{$IFDEF FPC}
{$mode objfpc}{$H+}
{$ENDIF}}
uses Math, SysUtils;
{$DEFINE USE_FP}
{$IFDEF USE_FP}
type TCoordinate = double;
const TOLERANCE = 1.0E-6;
{$ELSE}
type TCoordinate = integer;
const TOLERANCE = 0;
{$ENDIF}
type TVertex = record
x, y : TCoordinate;
end;
function Vertex( x_in, y_in : TCoordinate) : TVertex;
begin
result.x := x_in;
result.y := y_in;
end;
// Result of testing sides of a triangle for separator.
// Values are arbitrary but must be in this numerical order
const
SEP_NO_TEST = -1; // triangle is a single point, no sides to be tested
SEP_NONE = 0; // didn't find a separator
SEP_WEAK = 1; // found a weak separator only
SEP_STRONG = 2; // found a strong separator
function EqualVertices( V, W : TVertex) : boolean;
begin
result := (Abs(V.x - W.x) <= TOLERANCE)
and (Abs(V.y - W.y) <= TOLERANCE);
end;
// Determinant: twice the signed area of triangle PQR.
function Det( P, Q, R : TVertex) : TCoordinate;
begin
result := Q.x*R.y - R.x*Q.y + R.x*P.y - P.x*R.y + P.x*Q.y - Q.x*P.y;
end;
// Get result of trying sides of LMN as separators.
function TrySides( L, M, N, P, Q, R : TVertex) : integer;
var
s, sMin, sMax: TCoordinate;
H, K : TVertex;
function TestSide( V, W : TVertex) : integer;
var
detP, detQ, detR, tMin, tMax : TCoordinate;
begin
result := SEP_NONE;
detP := Det( V, W, P);
detQ := Det( V, W, Q);
detR := Det( V, W, R);
tMin := Math.Min( Math.Min( detP, detQ), detR);
tMax := Math.Max( Math.Max( detP, detQ), detR);
if (tMin - sMax > TOLERANCE) or (sMin - tMax > TOLERANCE) then
result := SEP_STRONG
else if (tMin - sMax >= -TOLERANCE) or (sMin - tMax >= -TOLERANCE) then
result := SEP_WEAK;
end;
begin
sMin := 0;
sMax := 0;
s := Det( L, M, N);
if (s <> 0) then begin // L, M, N are not collinear
if (s < 0) then sMin := s else sMax := s;
// Once we've found a strong separator, there's no need for further testing
result := TestSide( M, N);
if (result < SEP_STRONG) then result := Math.Max( result, TestSide( N, L));
if (result < SEP_STRONG) then result := Math.Max( result, TestSide( L, M));
end
else begin // s = 0 so L, M, N are collinear
// Look for distinct vertices from among L, M, N
H := L;
K := M;
if EqualVertices( H, K) then K := N;
if EqualVertices( H, K) then result := SEP_NO_TEST // L = M = N
else result := TestSide( H, K);
end;
end;
function Algo_5( A, B, C, D, E, F : TVertex) : integer;
begin
result := TrySides( A, B, C, D, E, F);
if (result < SEP_STRONG) then begin
result := Math.Max( result, TrySides( D, E, F, A, B, C));
if (result = SEP_NO_TEST) then begin // A = B = C and D = E = F
if EqualVertices( A, D) then result := SEP_WEAK
else result := SEP_STRONG;
end;
end;
end;
procedure TestTrianglePair (Ax, Ay, Bx, By, Cx, Cy,
Dx, Dy, Ex, Ey, Fx, Fy : TCoordinate);
var
ovStr : string;
begin
case Algo_5( Vertex(Ax, Ay), Vertex(Bx, By), Vertex(Cx, Cy),
Vertex(Dx, Dy), Vertex(Ex, Ey), Vertex(Fx, Fy)) of
SEP_STRONG : ovStr := 'Disjoint';
SEP_NONE : ovStr := 'Overlap';
else ovStr := 'Borderline';
end;
WriteLn( SysUtils.Format(
'(%g,%g),(%g,%g),(%g,%g) and (%g,%g),(%g,%g),(%g,%g): %s',
[Ax, Ay, Bx, By, Cx, Cy, Dx, Dy, Ex, Ey, Fx, Fy, ovStr]));
end;
// Main routine
begin
TestTrianglePair( 0,0,5,0,0,5, 0,0,5,0,0,6);
TestTrianglePair( 0,0,0,5,5,0, 0,0,0,5,5,0);
TestTrianglePair( 0,0,5,0,0,5, -10,0,-5,0,-1,6);
TestTrianglePair( 0,0,5,0,2.5,5, 0,4,2.5,-1,5,4);
TestTrianglePair( 0,0,1,1,0,2, 2,1,3,0,3,2);
TestTrianglePair( 0,0,1,1,0,2, 2,1,3,-2,3,4);
TestTrianglePair( 0,0,1,0,0,1, 1,0,2,0,1,1);
end.
</syntaxhighlight>
{{out}}
<pre>
(0,0),(5,0),(0,5) and (0,0),(5,0),(0,6): Overlap
(0,0),(0,5),(5,0) and (0,0),(0,5),(5,0): Overlap
(0,0),(5,0),(0,5) and (-10,0),(-5,0),(-1,6): Disjoint
(0,0),(5,0),(2.5,5) and (0,4),(2.5,-1),(5,4): Overlap
(0,0),(1,1),(0,2) and (2,1),(3,0),(3,2): Disjoint
(0,0),(1,1),(0,2) and (2,1),(3,-2),(3,4): Disjoint
(0,0),(1,0),(0,1) and (1,0),(2,0),(1,1): Borderline
</pre>
=={{header|Perl}}==
===Port of Lua===
<
use warnings;
Line 2,895 ⟶ 4,854:
@t1 = ({x=>0, y=>0}, {x=>1, y=>0}, {x=>0, y=>1});
@t2 = ({x=>1, y=>0}, {x=>2, y=>0}, {x=>1, y=>1});
print formatTri(\@t1), " and\n", formatTri(\@t2), "\n", overlap(\@t1, \@t2, 0.0, 0, 0), "\n";</
{{out}}
<pre>Triangle: (0, 0), (5, 0), (0, 5) and
Line 2,930 ⟶ 4,889:
===More Idiomatic===
<
use warnings;
use feature 'say';
Line 3,014 ⟶ 4,973:
);
say overlap(\$_->[0], \$_->[1], $_->[2], $_->[3], $_->[4]) for @tests;</
{{out}}
<pre> overlap: (0,0), (5,0), (0,5) and (0,0), (5,0), (0,6)
Line 3,023 ⟶ 4,982:
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}}==
{{libheader|Phix/pGUI}}
{{trans|zkl}}
Plus draw all eight pairs of triangles for visual confirmation.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\Determine_if_two_triangles_overlap.exw
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">pGUI</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">Ihandle</span> <span style="color: #000000;">dlg</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">canvas</span>
<span style="color: #004080;">cdCanvas</span> <span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">triangles</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{-</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2.5</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}},</span>
<span style="color: #0000FF;">{{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}}}</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">draw_triangle</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">cx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasBegin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_CLOSED_LINES</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">cdCanvasVertex</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cy</span><span style="color: #0000FF;">+</span><span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">cdCanvasEnd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">det2D</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">triangle</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">p1x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p1y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">p2x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2y</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">p3x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p3y</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">triangle</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">p1x</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">p2y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p3y</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">p2x</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">p3y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p1y</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">p3x</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">p1y</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p2y</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">bReversed</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">checkWinding</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">allowReversed</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">detTri</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">det2D</span><span style="color: #0000FF;">(</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">);</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">detTri</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0.0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">allowReversed</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">bReversed</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #000000;">triangle</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">throw</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"triangle has wrong winding direction"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">triangle</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">overlap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">epsilon</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0.0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">allowReversed</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">onBoundary</span><span style="color: #0000FF;">=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Trangles must be expressed anti-clockwise</span>
<span style="color: #000000;">bReversed</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">checkWinding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">allowReversed</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">checkWinding</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">allowReversed</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- check t1 then t2</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">edge</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- check each edge</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">edge</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">p2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t1</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edge</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000080;font-style:italic;">-- Check all points of trangle 2 lay on the external side
-- of the edge E. If they do, the triangles do not collide.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">onside</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">det2D</span><span style="color: #0000FF;">({</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]}),</span><span style="color: #000000;">epsilon</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">onBoundary</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- -- (the following incomprehensible one-liner is equivalent:)
-- if compare(det2D({p1,p2,t2[k]}),epsilon)>-onBoundary then exit end if</span>
<span style="color: #000000;">onside</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">onside</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">onBoundary</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"no overlap"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"no overlap (no boundary)"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- flip and re-test</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bReversed</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"overlap (reversed)"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"overlap"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">redraw_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000080;font-style:italic;">/*ih*/</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasActivate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">cy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">200</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">triangles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">triangles</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">draw_triangle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_RED</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (smudge tests[1..2] by one
-- pixel to show them better)</span>
<span style="color: #000000;">draw_triangle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">+</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #004600;">CD_BLUE</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasSetForeground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_BLACK</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasText</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">-</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">overlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">8</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">cy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span>
<span style="color: #000000;">cx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">cx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">300</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">cdCanvasFlush</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">map_cb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">Ihandle</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cdcanvas</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">cdCreateCanvas</span><span style="color: #0000FF;">(</span><span style="color: #004600;">CD_IUP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ih</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cddbuffer</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">cdCreateCanvas</span><span style="color: #0000FF;">(</span><span style="color: #004600;">CD_DBUFFER</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cdcanvas</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">cdCanvasSetBackground</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cddbuffer</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">CD_WHITE</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">IUP_DEFAULT</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupOpen</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">canvas</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupCanvas</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"RASTERSIZE=1250x300"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetCallbacks</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"MAP_CB"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"map_cb"</span><span style="color: #0000FF;">),</span>
<span style="color: #008000;">"ACTION"</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">Icallback</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"redraw_cb"</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">dlg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">IupDialog</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span><span style="color: #008000;">`RESIZE=NO, TITLE="Triangle overlap"`</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupShow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dlg</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">IupSetAttribute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">canvas</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"RASTERSIZE"</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">IupMainLoop</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">IupClose</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
=={{header|Python}}==
{{libheader|NumPy}}
Using numpy:
<syntaxhighlight lang="python">from __future__ import print_function
import numpy as np
Line 3,339 ⟶ 5,202:
t1 = [[0,0],[1,0],[0,1]]
t2 = [[1,0],[2,0],[1,1]]
print (TriTri2D(t1, t2, onBoundary = False), False)</
{{out}}
Line 3,350 ⟶ 5,213:
True True
/False False</pre>
{{libheader|Shapely}}
Using shapely:
<syntaxhighlight lang="python">from __future__ import print_function
from shapely.geometry import Polygon
Line 3,389 ⟶ 5,251:
t1 = [[0,0],[1,0],[0,1]]
t2 = [[1,0],[2,0],[1,1]]
print (PolyOverlaps(t1, t2), "?")</
{{out}}
Line 3,401 ⟶ 5,263:
=={{header|QB64}}==
<syntaxhighlight lang="qb64">
DATA 0,0,5,0,0,5,0,0,5,0,0,6
DATA 0,0,0,5,5,0,0,0,0,5,5,0
Line 3,479 ⟶ 5,341:
p.y = (10 + p.y) * 30
END SUB
</syntaxhighlight>
=={{header|Racket}}==
{{trans|Zkl}}
<
;; A triangle is a list of three pairs of points: '((x . y) (x . y) (x . y))
Line 3,547 ⟶ 5,409:
(check-true (tri-tri-2d? c1 c2 #:on-boundary? #t))
(check-false (tri-tri-2d? c1 c2 #:on-boundary? #f))))
</syntaxhighlight>
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])
<syntaxhighlight lang="raku" line># 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/
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 = sign (pt, Y[0], Y[1]);
my $d2 = sign (pt, Y[1], Y[2]);
my $d3 = sign (pt, Y[2], Y[0]);
my $has_neg = [or] $d1 < 0, $d2 < 0, $d3 < 0;
my $has_pos = [or] $d1 > 0, $d2 > 0, $d3 > 0;
return not ($has_neg and $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]) 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;
o1 != o2 and o3 != o4
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 {
{ $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.gist} and {B.gist} do{' NOT' unless $result} 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 ;</syntaxhighlight>
{{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}}==
Note: The triangles must be real triangles (no edge of length 0)
<
Signal On Halt
Signal On Novalue
Line 4,129 ⟶ 6,081:
Nop
End
Exit 12</
{{out}}
<pre>ABC: (0/0) (5/0) (0/5)
Line 4,202 ⟶ 6,154:
Triangles overlap
</pre>
=={{header|Ruby}}==
{{trans|C}}
<syntaxhighlight lang="ruby">require "matrix"
def det2D(p1, p2, p3)
return p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1])
end
def checkTriWinding(p1, p2, p3, allowReversed)
detTri = det2D(p1, p2, p3)
if detTri < 0.0 then
if allowReversed then
p2[0], p3[0] = p3[0], p2[0]
p2[1], p3[1] = p3[1], p2[1]
else
raise "Triangle has incorrect winding"
end
end
end
def boundaryCollideChk(p1, p2, p3, eps)
return det2D(p1, p2, p3) < eps
end
def boundaryDoesntCollideChk(p1, p2, p3, eps)
return det2D(p1, p2, p3) <= eps
end
def triTri2D(t1, t2, eps, allowReversed, onBoundary)
# Triangles must be expressed anti-clockwise
checkTriWinding(t1[0], t1[1], t1[2], allowReversed)
checkTriWinding(t2[0], t2[1], t2[2], allowReversed)
if onBoundary then
# Points on the boundary are considered as colliding
chkEdge = -> (p1, p2, p3, eps) { boundaryCollideChk(p1, p2, p3, eps) }
else
# Points on the boundary are not considered as colliding
chkEdge = -> (p1, p2, p3, eps) { boundaryDoesntCollideChk(p1, p2, p3, eps) }
end
# For edge E of triangle 1
for i in 0..2 do
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) and chkEdge.(t1[i], t1[j], t2[1], eps) and chkEdge.(t1[i], t1[j], t2[2], eps) then
return false
end
end
# For edge E of triangle 2
for i in 0..2 do
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) and chkEdge.(t2[i], t2[j], t1[1], eps) and chkEdge.(t2[i], t2[j], t1[2], eps) then
return false
end
end
# The triangles collide
return true
end
def main
t1 = [Vector[0,0], Vector[5,0], Vector[0,5]]
t2 = [Vector[0,0], Vector[5,0], Vector[0,6]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
t1 = [Vector[0,0], Vector[0,5], Vector[5,0]]
t2 = [Vector[0,0], Vector[0,5], Vector[5,0]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, true, true)]
t1 = [Vector[ 0,0], Vector[ 5,0], Vector[ 0,5]]
t2 = [Vector[-10,0], Vector[-5,0], Vector[-1,6]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
t1 = [Vector[0,0], Vector[ 5, 0], Vector[2.5,5]]
t2 = [Vector[0,4], Vector[2.5,-1], Vector[ 5,4]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
t1 = [Vector[0,0], Vector[1,1], Vector[0,2]]
t2 = [Vector[2,1], Vector[3,0], Vector[3,2]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
t1 = [Vector[0,0], Vector[1, 1], Vector[0,2]]
t2 = [Vector[2,1], Vector[3,-2], Vector[3,4]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
# Barely touching
t1 = [Vector[0,0], Vector[1,0], Vector[0,1]]
t2 = [Vector[1,0], Vector[2,0], Vector[1,1]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, true)]
# Barely touching
t1 = [Vector[0,0], Vector[1,0], Vector[0,1]]
t2 = [Vector[1,0], Vector[2,0], Vector[1,1]]
print "Triangle: ", t1, "\n"
print "Triangle: ", t2, "\n"
print "overlap: %s\n\n" % [triTri2D(t1, t2, 0.0, false, false)]
end
main()</syntaxhighlight>
{{out}}
<pre>Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 5]]
Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 6]]
overlap: true
Triangle: [Vector[0, 0], Vector[0, 5], Vector[5, 0]]
Triangle: [Vector[0, 0], Vector[0, 5], Vector[5, 0]]
overlap: true
Triangle: [Vector[0, 0], Vector[5, 0], Vector[0, 5]]
Triangle: [Vector[-10, 0], Vector[-5, 0], Vector[-1, 6]]
overlap: false
Triangle: [Vector[0, 0], Vector[5, 0], Vector[2.5, 5]]
Triangle: [Vector[0, 4], Vector[2.5, -1], Vector[5, 4]]
overlap: true
Triangle: [Vector[0, 0], Vector[1, 1], Vector[0, 2]]
Triangle: [Vector[2, 1], Vector[3, 0], Vector[3, 2]]
overlap: false
Triangle: [Vector[0, 0], Vector[1, 1], Vector[0, 2]]
Triangle: [Vector[2, 1], Vector[3, -2], Vector[3, 4]]
overlap: false
Triangle: [Vector[0, 0], Vector[1, 0], Vector[0, 1]]
Triangle: [Vector[1, 0], Vector[2, 0], Vector[1, 1]]
overlap: true
Triangle: [Vector[0, 0], Vector[1, 0], Vector[0, 1]]
Triangle: [Vector[1, 0], Vector[2, 0], Vector[1, 1]]
overlap: false</pre>
=={{header|Scala}}==
{{trans|Kotlin}}
<
type Point = (Double, Double)
Line 4,308 ⟶ 6,413:
println(if (triTri2D(t1, t2, onBoundary = false)) "overlap" else "do not overlap")
}
}</
{{out}}
<pre>Triangle: (0.0,0.0), (5.0,0.0), (0.0,5.0) and
Line 4,346 ⟶ 6,451:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Class Triangle
Line 4,494 ⟶ 6,599:
End Sub
End Module</
{{out}}
<pre>Triangle: (0, 0), (5, 0), (0, 5) and
Line 4,529 ⟶ 6,634:
which have only a single corner in contact, if boundary points do not collide
do not overlap</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">struct Point {
x f64
y f64
}
fn (p Point) str() string {
return "(${p.x:.1f}, ${p.y:.1f})"
}
struct Triangle {
mut:
p1 Point
p2 Point
p3 Point
}
fn (t Triangle) str() string {
return "Triangle $t.p1, $t.p2, $t.p3"
}
fn (t Triangle) det_2d() f64 {
return t.p1.x * (t.p2.y - t.p3.y) +
t.p2.x * (t.p3.y - t.p1.y) +
t.p3.x * (t.p1.y - t.p2.y)
}
fn (mut t Triangle) check_tri_winding(allow_reversed bool) {
det_tri := t.det_2d()
if det_tri < 0.0 {
if allow_reversed {
a := t.p3
t.p3 = t.p2
t.p2 = a
} else {
panic("Triangle has wrong winding direction.")
}
}
}
fn boundary_collide_chk(t Triangle, eps f64, does bool) bool {
if does {
return t.det_2d() < eps
}
return t.det_2d() <= eps
}
fn tri_tri_2d(mut t1 Triangle, mut t2 Triangle, eps f64, allow_reversed bool, on_boundary bool) bool {
// Triangles must be expressed anti-clockwise.
t1.check_tri_winding(allow_reversed)
t2.check_tri_winding(allow_reversed)
lp1 := [t1.p1, t1.p2, t1.p3]
lp2 := [t2.p1, t2.p2, t2.p3]
// for each edge E of t1
for i in 0..3 {
j := (i + 1) % 3
// Check all Points of t2 lay on the external side of edge E.
// If they do, the Triangles do not overlap.
tri1 := Triangle{lp1[i], lp1[j], lp2[0]}
tri2 := Triangle{lp1[i], lp1[j], lp2[1]}
tri3 := Triangle{lp1[i], lp1[j], lp2[2]}
if boundary_collide_chk(tri1, eps,on_boundary) && boundary_collide_chk(tri2, eps,on_boundary) && boundary_collide_chk(tri3, eps,on_boundary) {
return false
}
}
// for each edge E of t2
for i in 0..3 {
j := (i + 1) % 3
// Check all Points of t1 lay on the external side of edge E.
// If they do, the Triangles do not overlap.
tri1 := Triangle{lp2[i], lp2[j], lp1[0]}
tri2 := Triangle{lp2[i], lp2[j], lp1[1]}
tri3 := Triangle{lp2[i], lp2[j], lp1[2]}
if boundary_collide_chk(tri1, eps,on_boundary) && boundary_collide_chk(tri2, eps,on_boundary) && boundary_collide_chk(tri3, eps,on_boundary) {
return false
}
}
// The Triangles overlap.
return true
}
fn iff(cond bool, s1 string, s2 string) string {
if cond {
return s1
}
return s2
}
fn main() {
mut t1 := Triangle{Point{0.0, 0.0}, Point{5.0, 0.0}, Point{0.0, 5.0}}
mut t2 := Triangle{Point{0.0, 0.0}, Point{5.0, 0.0}, Point{0.0, 6.0}}
println("\n$t1 and\n$t2")
mut overlapping := tri_tri_2d(mut t1, mut t2, 0.0, false, true)
println(iff(overlapping, "overlap", "do not overlap"))
// Need to allow reversed for this pair to avoid panic.
t1 = Triangle{Point{0.0, 0.0}, Point{0.0, 5.0}, Point{5.0, 0.0}}
t2 = t1
println("\n$t1 and\n$t2")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, true, true)
println(iff(overlapping, "overlap (reversed)", "do not overlap"))
t1 = Triangle{Point{0.0, 0.0}, Point{5.0, 0.0}, Point{0.0, 5.0}}
t2 = Triangle{Point{-10.0, 0.0}, Point{-5.0, 0.0}, Point{-1.0, 6.0}}
println("\n$t1 and\n$t2")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, false, true)
println(iff(overlapping, "overlap", "do not overlap"))
t1.p3 = Point{2.5, 5.0}
t2 = Triangle{Point{0.0, 4.0}, Point{2.5, -1.0}, Point{5.0, 4.0}}
println("\n$t1 and\n$t2")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, false, true)
println(iff(overlapping, "overlap", "do not overlap"))
t1 = Triangle{Point{0.0, 0.0}, Point{1.0, 1.0}, Point{0.0, 2.0}}
t2 = Triangle{Point{2.0, 1.0}, Point{3.0, 0.0}, Point{3.0, 2.0}}
println("\n$t1 and\n$t2")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, false, true)
println(iff(overlapping, "overlap", "do not overlap"))
t2 = Triangle{Point{2.0, 1.0}, Point{3.0, -2.0}, Point{3.0, 4.0}}
println("\n$t1 and\n$t2")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, false, true)
println(iff(overlapping, "overlap", "do not overlap"))
t1 = Triangle{Point{0.0, 0.0}, Point{1.0, 0.0}, Point{0.0, 1.0}}
t2 = Triangle{Point{1.0, 0.0}, Point{2.0, 0.0}, Point{1.0, 1.1}}
println("\n$t1 and\n$t2")
println("which have only a single corner in contact, if boundary Points collide")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, false, true)
println(iff(overlapping, "overlap", "do not overlap"))
println("\n$t1 and\n$t2")
println("which have only a single corner in contact, if boundary Points do not collide")
overlapping = tri_tri_2d(mut t1, mut t2, 0.0, false, false)
println(iff(overlapping, "overlap", "do not overlap"))
}</syntaxhighlight>
{{out}}
<pre>Same as Kotlin Entry</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="wren">import "./dynamic" for Tuple, Struct
var Point = Tuple.create("Point", ["x", "y"])
var Triangle = Struct.create("Triangle", ["p1", "p2", "p3"])
var det2D = Fn.new { |t|
return t.p1.x * (t.p2.y - t.p3.y) +
t.p2.x * (t.p3.y - t.p1.y) +
t.p3.x * (t.p1.y - t.p2.y)
}
var checkTriWinding = Fn.new { |t, allowReversed|
var detTri = det2D.call(t)
if (detTri < 0) {
if (allowReversed) {
var a = t.p3
t.p3 = t.p2
t.p2 = a
} else Fiber.abort("Triangle has wrong winding direction")
}
}
var boundaryCollideChk = Fn.new { |t, eps| det2D.call(t) < eps }
var boundaryDoesntCollideChk = Fn.new { |t, eps| det2D.call(t) <= eps }
var triTri2D = Fn.new { |t1, t2, eps, allowReversed, onBoundary|
// Triangles must be expressed anti-clockwise
checkTriWinding.call(t1, allowReversed)
checkTriWinding.call(t2, allowReversed)
// 'onBoundary' determines whether points on boundary are considered as colliding or not
var chkEdge = onBoundary ? boundaryCollideChk : boundaryDoesntCollideChk
var lp1 = [t1.p1, t1.p2, t1.p3]
var lp2 = [t2.p1, t2.p2, t2.p3]
// for each edge E of t1
for (i in 0..2) {
var j = (i + 1) % 3
// Check all points of t2 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (chkEdge.call(Triangle.new(lp1[i], lp1[j], lp2[0]), eps) &&
chkEdge.call(Triangle.new(lp1[i], lp1[j], lp2[1]), eps) &&
chkEdge.call(Triangle.new(lp1[i], lp1[j], lp2[2]), eps)) return false
}
// for each edge E of t2
for (i in 0..2) {
var j = (i + 1) % 3
// Check all points of t1 lay on the external side of edge E.
// If they do, the triangles do not overlap.
if (chkEdge.call(Triangle.new(lp2[i], lp2[j], lp1[0]), eps) &&
chkEdge.call(Triangle.new(lp2[i], lp2[j], lp1[1]), eps) &&
chkEdge.call(Triangle.new(lp2[i], lp2[j], lp1[2]), eps)) return false
}
// The triangles overlap
return true
}
var tr = "Triangle: "
var printTris = Fn.new { |t1, t2, nl| System.print("%(nl)%(tr)%(t1) and\n%(tr)%(t2)") }
var t1 = Triangle.new(Point.new(0, 0), Point.new(5, 0), Point.new(0, 5))
var t2 = Triangle.new(Point.new(0, 0), Point.new(5, 0), Point.new(0, 6))
printTris.call(t1, t2, "")
System.print(triTri2D.call(t1, t2, 0, false, true) ? "overlap" : "do not overlap")
// need to allow reversed for this pair to avoid exception
t1 = Triangle.new(Point.new(0, 0), Point.new(0, 5), Point.new(5, 0))
t2 = t1
printTris.call(t1, t2, "\n")
System.print(triTri2D.call(t1, t2, 0, true, true) ? "overlap (reversed)" : "do not overlap")
t1 = Triangle.new(Point.new(0, 0), Point.new(5, 0), Point.new(0, 5))
t2 = Triangle.new(Point.new(-10, 0), Point.new(-5, 0), Point.new(-1, 6))
printTris.call(t1, t2, "\n")
System.print(triTri2D.call(t1, t2, 0, false, true) ? "overlap" : "do not overlap")
t1.p3 = Point.new(2.5, 5)
t2 = Triangle.new(Point.new(0, 4), Point.new(2.5, -1), Point.new(5, 4))
printTris.call(t1, t2, "\n")
System.print(triTri2D.call(t1, t2, 0, false, true) ? "overlap" : "do not overlap")
t1 = Triangle.new(Point.new(0, 0), Point.new(1, 1), Point.new(0, 2))
t2 = Triangle.new(Point.new(2, 1), Point.new(3, 0), Point.new(3, 2))
printTris.call(t1, t2, "\n")
System.print(triTri2D.call(t1, t2, 0, false, true) ? "overlap" : "do not overlap")
t2 = Triangle.new(Point.new(2, 1), Point.new(3, -2), Point.new(3, 4))
printTris.call(t1, t2, "\n")
System.print(triTri2D.call(t1, t2, 0, false, true) ? "overlap" : "do not overlap")
t1 = Triangle.new(Point.new(0, 0), Point.new(1, 0), Point.new(0, 1))
t2 = Triangle.new(Point.new(1, 0), Point.new(2, 0), Point.new(1, 1.1))
printTris.call(t1, t2, "\n")
System.print("which have only a single corner in contact, if boundary points collide")
System.print(triTri2D.call(t1, t2, 0, false, true) ? "overlap" : "do not overlap")
printTris.call(t1, t2, "\n")
System.print("which have only a single corner in contact, if boundary points do not collide")
System.print(triTri2D.call(t1, t2, 0, false, false) ? "overlap" : "do not overlap")</syntaxhighlight>
{{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|zkl}}==
{{trans|C++}}
<
fcn det2D(triangle){
Line 4,571 ⟶ 6,965:
}
True // The triangles collide
}</
<
vm.arglist.apply("toFloat").pump(List,Void.Read)
}
Line 4,596 ⟶ 6,990:
c1,c2 := toTri(0,0, 1,0, 0,1), toTri(1,0, 2,0, 1,1);
println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,True)); // True
println("Corner case (barely touching): ",triTri2D(c1,c2,0.0,False,False)); // False</
{{out}}
<pre>
| |||