Find if a point is within a triangle: Difference between revisions
Find if a point is within a triangle (view source)
Revision as of 11:13, 5 December 2023
, 5 months ago→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (19 intermediate revisions by 7 users not shown) | |||
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 difference 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}}==
Line 600 ⟶ 801:
</pre>
=={{header|D}}==
<syntaxhighlight lang="d">
import std.algorithm;
import std.stdio;
immutable EPS = 0.001;
immutable EPS_SQUARE = EPS * EPS;
double side(double x1, double y1, double x2, double y2, double x, double y) {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
}
bool naivePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double checkSide1 = side(x1, y1, x2, y2, x, y) >= 0;
double checkSide2 = side(x2, y2, x3, y3, x, y) >= 0;
double checkSide3 = side(x3, y3, x1, y1, x, y) >= 0;
return checkSide1 && checkSide2 && checkSide3;
}
bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
double xMin = min(x1, x2, x3) - EPS;
double xMax = max(x1, x2, x3) + EPS;
double yMin = min(y1, y2, y3) - EPS;
double yMax = max(y1, y2, y3) + EPS;
return !(x < xMin || xMax < x || y < yMin || yMax < y);
}
double distanceSquarePointToSegment(double x1, double y1, double x2, double y2, double x, double y) {
double p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
double dotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength;
if (dotProduct < 0) {
return (x - x1) * (x - x1) + (y - y1) * (y - y1);
} else if (dotProduct <= 1) {
double p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength;
} else {
return (x - x2) * (x - x2) + (y - y2) * (y - y2);
}
}
bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) {
return false;
}
if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
return true;
}
if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) {
return true;
}
if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) {
return true;
}
if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) {
return true;
}
return false;
}
void printPoint(double x, double y) {
write('(', x, ", ", y, ')');
}
void printTriangle(double x1, double y1, double x2, double y2, double x3, double y3) {
write("Triangle is [");
printPoint(x1, y1);
write(", ");
printPoint(x2, y2);
write(", ");
printPoint(x3, y3);
writeln(']');
}
void test(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
printTriangle(x1, y1, x2, y2, x3, y3);
write("Point ");
printPoint(x, y);
write(" is within triangle? ");
writeln(accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y));
}
void main() {
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0);
writeln;
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1);
writeln;
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1);
writeln;
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111, 5.414285714285714, 14.349206349206348);
writeln;
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
writeln;
}
</syntaxhighlight>
{{out}}
<pre>
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (0, 0) is within triangle? true
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (0, 1) is within triangle? true
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (3, 1) is within triangle? false
Triangle is [(0.1, 0.111111), (12.5, 33.3333), (25, 11.1111)]
Point (5.41429, 14.3492) is within triangle? true
Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)]
Point (5.41429, 14.3492) is within triangle? true
</pre>
=={{header|Delphi}}==
Line 605 ⟶ 923:
{{libheader|Types,StdCtrls,ExtCtrls,SysUtils,Graphics}}
This routine works by taking each line in the triangle and determining which side of the line the point is on. This is done using the "determinant" of the three points. If a point is on the same side of all sides in the triangle, the point is inside the triangle. Conversely, if a point isn't on the same side, it is out of side the triangle. Since there are only three points in a triangle, this applies no matter the order in which the points are presented, as long as the points are traversed in order. Points that fall on a line are treated as though they have the same "inside" sense when combined with other lines.
<syntaxhighlight lang="Delphi">
Line 751 ⟶ 1,067:
</syntaxhighlight>
{{out}}
[[File:PintInTriangle.png|frame|none]]
<pre>
</pre>
=={{header|Dart}}==
Line 959 ⟶ 1,171:
print('');
}</syntaxhighlight>
=={{header|Evaldraw}}==
This solution makes use of the (x,y,t,&r,&g,&b) plotting function. It evaluates an function in the cartesian plane. Given x,y inputs, the function is expected to set r,g,b color channels. The program tests all points in the viewport. You may pan and zoom. The current mouse position shows the computed RGB at that point. The isPointInsideTriangle-function here works in similar way to other solutions here;
for the 3 points of a triangle we compute 3 line equations that will be evaluated to get the signed distance from the line to a point.
We can use this to return early from isPointInsideTriangle. Only if all three lines give a result with the point on the same side (same sign) then the point can be classified as inside the triangle. We can use this property of sidedness and sign to make the method work for both clockwise and anti-clockwise specification of the triangle vertices. If the triangle is clockwise, then the area function returns a positive value. If the triangle is anti clockwise, then the area function returns a negative value, and we can multiply the sgn checks by -1 so a point can still be considered inside. A point with distance 0 is also considered inside.
[[File:Evaldraw points in triangle.png|thumb|alt=A triangle with vertices set to red, green and blue with interpolation over surface.|plot mode (x,y,&r,&g,&b) allows for plotting of arbitrary functions of (x,y) and return rgb]]
<syntaxhighlight lang="c">struct vec2{x,y;};
struct line_t{a,b,c;};
struct triangle_calc_t{
vec2 origin;
line_t lines[3];
vec2 min,max;
double area2;
winding_dir; // +1 if clockwise (positive angle) -1 if negative.
};
//static vec2 vertices[3] = {0,-2, -2,2, 4,0};
static vec2 vertices[3] = {-3,7, -6,-5, 2,2};
enum{TRI_OUT, TRI_ZERO, TRI_EDGE, TRI_INSIDE}
static triangle_calc_t triangle;
(x,y,t,&r,&g,&b)
{
if (numframes==0) {
precalc_tri( triangle, vertices);
}
d0 = d1 = d2 = 0; // Distances of point to lines
vec2 point = {x, y};
side = isPointInsideTriangle(point,triangle,d0,d1,d2);
if (side == TRI_INSIDE) {
if (triangle.winding_dir == -1) {
swap(d1,d2);
swap(d1,d0);
}
r_area = 1.0 / (triangle.winding_dir * triangle.area2);
r = 255 * r_area * d2;
g = 255 * r_area * d0;
b = 255 * r_area * d1; return 1;
}
r=0; g=0; b=0; return 0; // Set color to 0 if outside.
}
precalc_tri(triangle_calc_t t, vec2 verts[3]) {
t.area2 = triangleAreaTimes2(verts[0], verts[1], verts[2]);
if (t.area2 == 0) return;
t.winding_dir = sgn(t.area2);
t.origin = verts[0];
vec2 relative_vertices[3];
t.min.x = 1e32;
t.min.y = 1e32;
t.max.x = -1e32;
t.max.y = -1e32;
for(i=0; i<3; i++) {
t.min.x = min(t.min.x, verts[i].x);
t.min.y = min(t.min.y, verts[i].y);
t.max.x = max(t.max.x, verts[i].x);
t.max.y = max(t.max.y, verts[i].y);
relative_vertices[i].x = verts[i].x + t.origin.x;
relative_vertices[i].y = verts[i].y + t.origin.y;
}
makeLine(t.lines[0], relative_vertices[0], relative_vertices[1]);
makeLine(t.lines[1], relative_vertices[1], relative_vertices[2]);
makeLine(t.lines[2], relative_vertices[2], relative_vertices[0]);
}
triangleAreaTimes2(vec2 a, vec2 b, vec2 c) { // Same as the determinant, but dont div by 2
return c.x*(a.y-b.y)+a.x*(b.y-c.y)+b.x*(-a.y+c.y);
}
isPointInsideTriangle( vec2 point, triangle_calc_t t, &d0,&d1,&d2) {
if (t.area2 == 0) return TRI_ZERO;
if (point.x < t.min.x) return TRI_OUT;
if (point.y < t.min.y) return TRI_OUT;
if (point.x > t.max.x) return TRI_OUT;
if (point.y > t.max.y) return TRI_OUT;
vec2 p = {point.x + t.origin.x, point.y + t.origin.y };
d0 = t.winding_dir * lineDist( t.lines[0], p.x, p.y);
if (d0==0) { return TRI_EDGE; }else if ( sgn(d0) < 0 ) return TRI_OUT;
d1 = t.winding_dir * lineDist( t.lines[1], p.x, p.y);
if (d1==0) { return TRI_EDGE; } else if ( sgn(d1) < 0 ) return TRI_OUT;
d2 = t.winding_dir * lineDist( t.lines[2], p.x, p.y);
if (d2==0) { return TRI_EDGE; } else if ( sgn(d2) < 0 ) return TRI_OUT;
return TRI_INSIDE; // on inside
}
makeLine(line_t line, vec2 a, vec2 b) { // -dy,dx,axby-aybx
line.a = -(b.y - a.y);
line.b = (b.x - a.x);
line.c = a.x*b.y - a.y*b.x;
}
lineDist(line_t line, x,y) { return x*line.a + y*line.b + line.c; }
swap(&a,&b) {tmp = a; a=b; b=tmp; }</syntaxhighlight>
=={{header|Factor}}==
Line 1,139 ⟶ 1,446:
_window = 1
begin enum 1
_textLabel
end enum
void local fn BuildWindow
window _window, @"Find if a point is within a triangle", (0, 0, 340, 360 )
WindowCenter(_window)
ViewSetFlipped( _windowContentViewTag, YES )
subclass textLabel _textLabel, @"", ( 20, 320, 300, 20 ), _window
end fn
void local fn DrawInView( tag as NSInteger )
BezierPathRef path = fn BezierPathInit
BezierPathMoveToPoint( path, fn CGPointMake( 30, 300 ) )
BezierPathLineToPoint( path, fn CGPointMake(
BezierPathClose( path )
BezierPathStrokeFill( path, 3.0, fn ColorBlack, fn ColorGreen )
AppSetProperty( @"path", path )
end fn
void local fn DoMouse( tag as NSInteger )
CGPoint pt = fn EventLocationInView( tag )
if ( fn BezierPathContainsPoint( fn AppProperty( @"path" ), pt ) )
ControlSetStringValue( _textLabel, fn StringWithFormat( @"Inside triangle: x = %.f y = %.f", pt.x, pt.y ) )
else
ControlSetStringValue( _textLabel, fn StringWithFormat( @"Outside triangle: x = %.f y = %.f", pt.x, pt.y ) )
end if
end fn
void local fn DoDialog( ev as long, tag as long )
select ( ev )
case _viewDrawRect : fn DrawInView(tag)
end select
end fn
Line 1,191 ⟶ 1,494:
{{output}}
[[File:FB Find Point in a Triangle.png]]
=={{header|Go}}==
Line 1,600 ⟶ 1,901:
Triangle[(0.100000, 0.111111), (12.500000, 33.333333), (-12.500000, 16.666667)]
Point (5.414286, 14.349206) is within triangle? true</pre>
=={{header|JavaScript}}==
{{trans|C++}}
<syntaxhighlight lang="javascript">
const EPS = 0.001;
const EPS_SQUARE = EPS * EPS;
function side(x1, y1, x2, y2, x, y) {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
}
function naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) {
const checkSide1 = side(x1, y1, x2, y2, x, y) >= 0;
const checkSide2 = side(x2, y2, x3, y3, x, y) >= 0;
const checkSide3 = side(x3, y3, x1, y1, x, y) >= 0;
return checkSide1 && checkSide2 && checkSide3;
}
function pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y) {
const xMin = Math.min(x1, Math.min(x2, x3)) - EPS;
const xMax = Math.max(x1, Math.max(x2, x3)) + EPS;
const yMin = Math.min(y1, Math.min(y2, y3)) - EPS;
const yMax = Math.max(y1, Math.max(y2, y3)) + EPS;
return !(x < xMin || xMax < x || y < yMin || yMax < y);
}
function distanceSquarePointToSegment(x1, y1, x2, y2, x, y) {
const p1_p2_squareLength = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
const dotProduct =
((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_squareLength;
if (dotProduct < 0) {
return (x - x1) * (x - x1) + (y - y1) * (y - y1);
} else if (dotProduct <= 1) {
const p_p1_squareLength = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength;
} else {
return (x - x2) * (x - x2) + (y - y2) * (y - y2);
}
}
function accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) {
if (!pointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) {
return false;
}
if (naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
return true;
}
if (distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) {
return true;
}
if (distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) {
return true;
}
if (distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) {
return true;
}
return false;
}
function printPoint(x, y) {
return "(" + x + ", " + y + ")";
}
function printTriangle(x1, y1, x2, y2, x3, y3) {
return (
"Triangle is [" +
printPoint(x1, y1) +
", " +
printPoint(x2, y2) +
", " +
printPoint(x3, y3) +
"]"
);
}
function test(x1, y1, x2, y2, x3, y3, x, y) {
console.log(
printTriangle(x1, y1, x2, y2, x3, y3) +
"Point " +
printPoint(x, y) +
" is within triangle? " +
(accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y) ? "true" : "false")
);
}
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 0);
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0, 1);
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3, 1);
console.log();
test(
0.1,
0.1111111111111111,
12.5,
33.333333333333336,
25,
11.11111111111111,
5.414285714285714,
14.349206349206348
);
console.log();
test(
0.1,
0.1111111111111111,
12.5,
33.333333333333336,
-12.5,
16.666666666666668,
5.414285714285714,
14.349206349206348
);
console.log();
</syntaxhighlight>
=={{header|jq}}==
Line 2,394 ⟶ 2,809:
<pre>
point (3,1) isn't within the triangle (1.5,2.4) , (5.1,-3.1) , (-3.8,0.5)
</pre>
=={{header|RPL}}==
{{trans|Ada}}
{{works with|HP|48G}}
≪ { } → points
≪ 1 4 '''START''' C→R 1 →V3 'points' STO+ '''NEXT'''
1 3 '''FOR''' j points j GET V→ '''NEXT'''
{ 3 3 } →ARRY DET ABS
1 3 '''FOR''' j
points j GET V→
points j 1 + 4 MOD 1 MAX GET V→
points 4 GET V→
{ 3 3 } →ARRY DET ABS
'''NEXT'''
+ + ==
≫ ≫ '<span style="color:blue">INTRI?</span>' STO
(1 0) (2 0) (0 2) (0 0) <span style="color:blue">INTRI?</span>
(-1 0) (-1 -1) (2 2) (0 0) <span style="color:blue">INTRI?</span>
{{out}}
<pre>
2: 0
1: 1
</pre>
Line 2,497 ⟶ 2,936:
Triangle is [[0.1, 0.1111111111111111], [12.5, 33.333333333333336], [-12.5, 16.666666666666668]]
Point [5.414285714285714, 14.349206349206348] is within triangle? true</pre>
=={{header|Rust}}==
{{works with|Rust|1.7.3}}
{{trans|D}}
<syntaxhighlight lang="rust">
const EPS: f64 = 0.001;
const EPS_SQUARE: f64 = EPS * EPS;
fn side(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> f64 {
(y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1)
}
fn naive_point_in_triangle(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
let check_side1 = side(x1, y1, x2, y2, x, y) >= 0.0;
let check_side2 = side(x2, y2, x3, y3, x, y) >= 0.0;
let check_side3 = side(x3, y3, x1, y1, x, y) >= 0.0;
check_side1 && check_side2 && check_side3
}
fn point_in_triangle_bounding_box(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
let x_min = f64::min(x1, f64::min(x2, x3)) - EPS;
let x_max = f64::max(x1, f64::max(x2, x3)) + EPS;
let y_min = f64::min(y1, f64::min(y2, y3)) - EPS;
let y_max = f64::max(y1, f64::max(y2, y3)) + EPS;
!(x < x_min || x_max < x || y < y_min || y_max < y)
}
fn distance_square_point_to_segment(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> f64 {
let p1_p2_square_length = (x2 - x1).powi(2) + (y2 - y1).powi(2);
let dot_product = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_square_length;
if dot_product < 0.0 {
(x - x1).powi(2) + (y - y1).powi(2)
} else if dot_product <= 1.0 {
let p_p1_square_length = (x1 - x).powi(2) + (y1 - y).powi(2);
p_p1_square_length - dot_product.powi(2) * p1_p2_square_length
} else {
(x - x2).powi(2) + (y - y2).powi(2)
}
}
fn accurate_point_in_triangle(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
if !point_in_triangle_bounding_box(x1, y1, x2, y2, x3, y3, x, y) {
return false;
}
if naive_point_in_triangle(x1, y1, x2, y2, x3, y3, x, y) {
return true;
}
if distance_square_point_to_segment(x1, y1, x2, y2, x, y) <= EPS_SQUARE {
return true;
}
if distance_square_point_to_segment(x2, y2, x3, y3, x, y) <= EPS_SQUARE {
return true;
}
if distance_square_point_to_segment(x3, y3, x1, y1, x, y) <= EPS_SQUARE {
return true;
}
false
}
fn print_point(x: f64, y: f64) {
print!("({}, {})", x, y);
}
fn print_triangle(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64) {
print!("Triangle is [");
print_point(x1, y1);
print!(", ");
print_point(x2, y2);
print!(", ");
print_point(x3, y3);
println!("]");
}
fn test(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) {
print_triangle(x1, y1, x2, y2, x3, y3);
print!("Point ");
print_point(x, y);
print!(" is within triangle? ");
println!("{}", accurate_point_in_triangle(x1, y1, x2, y2, x3, y3, x, y));
}
fn main() {
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0.0, 0.0);
println!();
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0.0, 1.0);
println!();
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3.0, 1.0);
println!();
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25.0, 11.11111111111111, 5.414285714285714, 14.349206349206348);
println!();
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
println!();
}
</syntaxhighlight>
{{out}}
<pre>
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (0, 0) is within triangle? true
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (0, 1) is within triangle? true
Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Point (3, 1) is within triangle? false
Triangle is [(0.1, 0.1111111111111111), (12.5, 33.333333333333336), (25, 11.11111111111111)]
Point (5.414285714285714, 14.349206349206348) is within triangle? true
Triangle is [(0.1, 0.1111111111111111), (12.5, 33.333333333333336), (-12.5, 16.666666666666668)]
Point (5.414285714285714, 14.349206349206348) is within triangle? true
</pre>
=={{header|V (Vlang)}}==
Line 2,604 ⟶ 3,160:
=={{header|Wren}}==
This is a translation of the ActionScript code for the 'accurate' method in the first referenced article above.
<syntaxhighlight lang="
var EPS_SQUARE = EPS * EPS
| |||