Find if a point is within a triangle: Difference between revisions
Find if a point is within a triangle (view source)
Revision as of 22:10, 7 July 2023
, 10 months agoAdded ATS.
No edit summary |
(Added ATS.) |
||
Line 298:
[ 5.4143, 14.3492] in ( [ 0.1000, 0.1111], [ 12.5000, 33.3333], [-12.5000, 16.6667]) -> false
</pre>
=={{header|ATS}}==
This is the same algorithm as the Common Lisp, although not a translation of the Common Lisp. I merely discovered the similarity while searching for Rosetta Code examples that had obtained similar outputs.
The algorithm is widely used for testing whether a point is inside a convex hull of any size. For each side of the hull, one computes the geometric product of some vectors and observes the sign of a component in the result. The test takes advantage of the sine (or cosine) being positive in two adjacent quadrants and negative in the other two. Two quadrants will represent the inside of the hull and two the outside, relative to any given side of the hull. More details are described in the comments of the program.
<syntaxhighlight lang="ats">
(* The principle employed here is to treat the triangle as a convex
hull oriented counterclockwise. Then a point is inside the hull if
it is to the left of every side of the hull.
This will prove easy to determine. Because the sine is positive in
quadrants 1 and 2 and negative in quadrants 3 and 4, the ‘sideness’
of a point can be determined by the sign of an outer product of
vectors. Or you can use any such trigonometric method, including
those that employ an inner product.
Suppose one side of the triangle goes from point p0 to point p1,
and that the point we are testing for ‘leftness’ is p2. Then we
compute the geometric outer product
(p1 - p0)∧(p2 - p0)
(or equivalently the cross product of Gibbs vector analysis) and
test the sign of its grade-2 component (or the sign of the
right-hand-rule Gibbs pseudovector along the z-axis). If the sign
is positive, then p2 is left of the side, because the sine of the
angle between the vectors is positive.
The algorithm considers the vertices and sides of the triangle as
as NOT inside the triangle.
Our algorithm is the same as that of the Common Lisp. We merely
have dressed it up in prêt-à-porter fashion and costume jewelry. *)
#include "share/atspre_staload.hats"
#define COUNTERCLOCKWISE 1
#define COLLINEAR 0
#define CLOCKWISE ~1
(* We will use some simple Euclidean geometric algebra. *)
typedef vector =
(* This type will represent either a point relative to the origin or
the different between two points. The e1 component is the x-axis
and the e2 component is the y-axis. *)
@{e1 = double, e2 = double}
typedef rotor =
(* This type is analogous to a pseudovectors, complex numbers, and
so forth. It will be used to represent the outer product. *)
@{scalar = double, e1_e2 = double}
typedef triangle = @(vector, vector, vector)
fn
vector_sub (a : vector, b : vector) : vector =
@{e1 = a.e1 - b.e1, e2 = a.e2 - b.e2}
overload - with vector_sub
fn
outer_product (a : vector, b : vector) : rotor =
@{scalar = 0.0, (* The scalar term vanishes. *)
e1_e2 = a.e1 * b.e2 - a.e2 * b.e1}
fn
is_left_of (pt : vector,
side : @(vector, vector)) =
let
val r = outer_product (side.1 - side.0, pt - side.0)
in
r.e1_e2 > 0.0
end
fn
orient_triangle {orientation : int | abs (orientation) == 1}
(t : triangle,
orientation : int orientation) : triangle =
(* Return an equivalent triangle that is definitely either
counterclockwise or clockwise, unless the original was
collinear. If the original was collinear, return it unchanged. *)
let
val @(p1, p2, p3) = t
(* If the triangle is counterclockwise, the grade-2 component of
the following outer product will be positive. *)
val r = outer_product (p2 - p1, p3 - p1)
in
if r.e1_e2 = 0.0 then
t
else
let
val sign =
(if r.e1_e2 > 0.0 then COUNTERCLOCKWISE else CLOCKWISE)
: [sign : int | abs sign == 1] int sign
in
if orientation = sign then t else @(p1, p3, p2)
end
end
fn
is_inside_triangle (pt : vector,
t : triangle) : bool =
let
val @(p1, p2, p3) = orient_triangle (t, COUNTERCLOCKWISE)
in
is_left_of (pt, @(p1, p2))
&& is_left_of (pt, @(p2, p3))
&& is_left_of (pt, @(p3, p1))
end
fn
fprint_vector (outf : FILEref,
v : vector) : void =
fprint! (outf, "(", v.e1, ",", v.e2, ")")
fn
fprint_triangle (outf : FILEref,
t : triangle) : void =
begin
fprint_vector (outf, t.0);
fprint! (outf, "--");
fprint_vector (outf, t.1);
fprint! (outf, "--");
fprint_vector (outf, t.2);
fprint! (outf, "--cycle")
end
fn
try_it (outf : FILEref,
pt : vector,
t : triangle) : void =
begin
fprint_vector (outf, pt);
fprint! (outf, " is inside ");
fprint_triangle (outf, t);
fprintln! (outf);
fprintln! (outf, is_inside_triangle (pt, t))
end
implement
main () =
let
val outf = stdout_ref
val t1 = @(@{e1 = 1.5, e2 = 2.4},
@{e1 = 5.1, e2 = ~3.1},
@{e1 = ~3.8, e2 = 1.2})
val p1 = @{e1 = 0.0, e2 = 0.0}
val p2 = @{e1 = 0.0, e2 = 1.0}
val p3 = @{e1 = 3.0, e2 = 1.0}
val p4 = @{e1 = 1.5, e2 = 2.4}
val p5 = @{e1 = 5.414286, e2 = 14.349206}
val t2 = @(@{e1 = 0.100000, e2 = 0.111111},
@{e1 = 12.500000, e2 = 33.333333},
@{e1 = 25.000000, e2 = 11.111111})
val t3 = @(@{e1 = 0.100000, e2 = 0.111111},
@{e1 = 12.500000, e2 = 33.333333},
@{e1 = ~12.500000, e2 = 16.666667})
in
try_it (outf, p1, t1);
try_it (outf, p2, t1);
try_it (outf, p3, t1);
try_it (outf, p4, t1);
fprintln! (outf);
try_it (outf, p5, t2);
fprintln! (outf);
fprintln! (outf, "Some programs are returning TRUE for ",
"the following. The Common Lisp uses");
fprintln! (outf, "the same",
" algorithm we do (presented differently),",
" and returns FALSE.");
fprintln! (outf);
try_it (outf, p5, t3);
0
end
</syntaxhighlight>
{{out}}
<pre>$ patscc -g -O3 -march=native -pipe -std=gnu2x point_inside_triangle.dats && ./a.out
(0.000000,0.000000) is inside (1.500000,2.400000)--(5.100000,-3.100000)--(-3.800000,1.200000)--cycle
true
(0.000000,1.000000) is inside (1.500000,2.400000)--(5.100000,-3.100000)--(-3.800000,1.200000)--cycle
true
(3.000000,1.000000) is inside (1.500000,2.400000)--(5.100000,-3.100000)--(-3.800000,1.200000)--cycle
false
(1.500000,2.400000) is inside (1.500000,2.400000)--(5.100000,-3.100000)--(-3.800000,1.200000)--cycle
false
(5.414286,14.349206) is inside (0.100000,0.111111)--(12.500000,33.333333)--(25.000000,11.111111)--cycle
true
Some programs are returning TRUE for the following. The Common Lisp uses
the same algorithm we do (presented differently), and returns FALSE.
(5.414286,14.349206) is inside (0.100000,0.111111)--(12.500000,33.333333)--(-12.500000,16.666667)--cycle
false</pre>
=={{header|AutoHotkey}}==
| |||