Determine if two triangles overlap: Difference between revisions

Added Easylang
(→‎{{header|Vlang}}: Rename "Vlang" in "V (Vlang)")
(Added Easylang)
 
(5 intermediate revisions by 5 users not shown)
Line 19:
Optionally, see what the result is when only a single corner is in contact (there is no definitive correct answer):
:::*   (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>
 
Line 214 ⟶ 219:
false
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>
 
Line 352 ⟶ 501:
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>
 
Line 1,075 ⟶ 1,604:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Determine_if_two_triangles_overlap#Pascal Pascal].
 
=={{header|EasyLang}}==
{{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#}}==
Line 3,034 ⟶ 3,611:
* 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 3,052 ⟶ 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 3,085 ⟶ 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 3,095 ⟶ 3,675:
tl4=reversex(tl3) ; Call trio_t tl4
tl5=subword(tl4,7) subword(tl4,1,6) ; Call trio_t tl5
tl6=''
tl6=subword(tl5,7) subword(tl5,1,6) ; Call trio_t tl6
tl=tlist
Do While tl<>''
Parse Var tl x y tl
tl6=tl6 y x
End
Call trio_t tl6
Return
 
Line 3,101 ⟶ 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 3,109 ⟶ 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 3,313 ⟶ 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 3,575 ⟶ 4,173:
res=res word(list,i)
End
Return res </syntaxhighlight>
 
::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)
 
0> 01 01 4 4 0 12 1 1 2 20 10 4 0 0 4
Triangle: ABC: (01,01) (02,41) (41,02)
Triangle: DEF: (10,10) (14,20) (20,14)
(1,1) (1,2,1) (2,1,2) is fully contained in (0,0) (0,4,0) (4,0,4)
 
> 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)
0> 8 0 68 8 0 3 80 0 80 86 8 3 0
Triangle: ABC: (08,0) (68,08) (30,83)
Triangle: DEF: (0,80) (80,86) (8,3,0)
Corner(s) that touch the other triangle: (38,03) (30,83)
Triangles overlap and touch on (38,03) (30,83)
> 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 3,643 ⟶ 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 3,649 ⟶ 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 3,655 ⟶ 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 3,661 ⟶ 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 3,667 ⟶ 4,288:
Triangles overlap and touch on (0,0) (2,0) (0,2)
 
> 0 0 24 0 0 26 0 0 0 42 62 0
Triangle: ABC: (0,0) (24,0) (0,26)
Triangle: DEF: (0,0) (0,42) (62,0)
Corner(s) that touch the other triangle: (0,0) (2,0,2) (0,2,0)
Triangles overlap and touch on (0,0) (2,0,2) (0,2,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 3,679 ⟶ 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 3,685 ⟶ 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 3,691 ⟶ 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 3,697 ⟶ 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 3,703 ⟶ 4,324:
Triangles have an edge in common: (0,0) (0,5)
 
0> 0 0 5 5 0 0 6 0 0 5 60 0 5
Triangle: ABC: (0,0) (5,0,5) (50,06)
Triangle: DEF: (0,0) (0,5,0) (6,0,5)
Corner(s) that touch the other triangle: (0,0) (0,5,0) (5,0,5)
Triangles have an edge in common: (0,0) (0,5,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 3,715 ⟶ 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 3,721 ⟶ 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 3,727 ⟶ 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 3,733 ⟶ 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 3,739 ⟶ 4,360:
Triangles are identical
 
0> 0 5 0 0 5 5 0 0 5 0 0 5 5 0
Triangle: ABC: (0,0) (5,0,5) (0,5,0)
Triangle: DEF: (0,0) (5,0,5) (0,5,0)
Corner(s) that touch the other triangle: (0,0) (5,0,5) (0,5,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
 
0> 0-10 0 5 -5 0 0 -101 6 0 0 -5 60 -10 5
Triangle: ABC: (0-10,0) (-5,0,5) (5-1,06)
Triangle: DEF: (0,-100) (0,-5,0) (60,-15)
(0-10,0) (0,-5,0) (5-1,06) and (0,-100) (0,-5,0) (60,-15) don't overlap
 
> 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
 
0> 0 04 2.5 5-1 2.5 4 0 -10 5 0 2.5 4 5
Triangle: ABC: (0,04) (02.5,5-1) (5,2.54)
Triangle: DEF: (40,0) (-1,2.5,0) (42.5,5)
(0,04) (0,2.5,-1) (5,2.54) and (40,0) (-1,2.5,0) (42.5,5) overlap
 
> 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
 
0> 02 1 13 0 3 2 0 0 1 21 0 3 2 3
Triangle: ABC: (02,01) (13,10) (3,2,0)
Triangle: DEF: (10,20) (01,31) (20,32)
(02,01) (13,10) (23,02) and (10,20) (01,31) (20,32) don't overlap
 
> 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
 
0 0 1 1> 2 0 1 23 -2 3 4 30 0 1 1 0 2
Triangle: ABC: (02,01) (13,1-2) (23,04)
Triangle: DEF: (10,20) (-21,31) (40,32)
(02,01) (13,1-2) (23,04) and (10,20) (-21,31) (40,32) don't overlap
 
> 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 3,873 ⟶ 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 3,881 ⟶ 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 3,889 ⟶ 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 3,897 ⟶ 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 3,905 ⟶ 4,526:
(0,1) (0,2) (1,1) and (0,0) (0,1) (1,0) don't overlap but touch on (0,1)
 
0> 1 0 2 0 1 1 0 0 1 0 2 10 1
Triangle: ABC: (01,0) (2,0,1) (1,01)
Triangle: DEF: (0,10) (01,20) (10,1)
Corner(s) that touch the other triangle: (0,1,0)
Triangles touch on (0,1,0)
we analyze further
(01,0) (02,10) (1,01) and (0,10) (01,20) (10,1) don't overlap but touch on (0,1,0)</pre>
 
> 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}}==
Line 6,158 ⟶ 6,784:
{{trans|Kotlin}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="ecmascriptwren">import "./dynamic" for Tuple, Struct
 
var Point = Tuple.create("Point", ["x", "y"])
2,069

edits