Rosetta Code

Find if a point is within a triangle: Difference between revisions

Page Discussion

Find if a point is within a triangle (view source)

Revision as of 11:13, 5 December 2023

30,183 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Fortran implementation using convex hull algorithm)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(27 intermediate revisions by 12 users not shown)
Line 32:
{{trans|Kotlin}}
 
<langsyntaxhighlight lang="11l">V EPS = 0.001
V EPS_SQUARE = EPS * EPS
 
Line 104:
p3 = (-100.0 / 8, 100.0 / 6)
tri = Triangle(p1, p2, p3)
test(tri, pt)</langsyntaxhighlight>
 
{{out}}
Line 129:
It uses a generic two-dimensional geometry, that could be affine, euclidean, or a lot stranger than that. You only need to specify the type of one dimension, and the library ''should'' handle the rest. Edge cases probably exist where they shouldn't, as the area formula might add some imprecision.
 
<langsyntaxhighlight Adalang="ada">-- triangle.ads
generic
type Dimension is private;
Line 163:
with Inline;
end;
</syntaxhighlight>
</lang>
<langsyntaxhighlight Adalang="ada">-- triangle.adb
 
package body Triangle is
Line 185:
end IsPointInTriangle;
end;
</syntaxhighlight>
</lang>
<langsyntaxhighlight Adalang="ada">-- test_triangle.adb
with Ada.Text_IO;
use Ada.Text_IO;
Line 202:
Put_Line("IsPointInTriangle("&Image(origin)&", "&Image(tri2)&") yields "&IsPointInTriangle(origin,tri2)'Image);
end test_triangle;
</syntaxhighlight>
</lang>
 
{{out}}
Line 214:
With additional material
{{Trans|Wren}}
<langsyntaxhighlight lang="algol68">BEGIN # determine whether a point is within a triangle or not #
# tolerance for the accurate test #
REAL eps = 0.001;
Line 287:
, ( 0.1, 0.11111111111111 ), ( 12.5, 33.333333333333 ), ( -12.5, 16.666666666667 )
)
END</langsyntaxhighlight>
{{out}}
<pre>
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}}==
<langsyntaxhighlight AutoHotkeylang="autohotkey">T := [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]]
for i, p in [[0, 0], [0, 1], [3, 1], [5.4142857, 14.349206]]
result .= "[" p.1 ", " p.2 "] is within triangle?`t" (TriHasP(T, p) ? "ture" : "false") "`n"
Line 315 ⟶ 516:
TriArea(x1, y1, x2, y2, x3, y3){
return Abs((x1 * (y2-y3) + x2 * (y3-y1) + x3 * (y1-y2)) / 2)
}</langsyntaxhighlight>
{{out}}
<pre>[0, 0] is within triangle? ture
Line 324 ⟶ 525:
=={{header|C}}==
{{trans|Go}}
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
Line 421 ⟶ 622:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Line 438 ⟶ 639:
=={{header|C++}}==
{{trans|C}}
<langsyntaxhighlight lang="cpp">#include <iostream>
 
const double EPS = 0.001;
Line 533 ⟶ 734:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 550 ⟶ 751:
 
=={{header|Common Lisp}}==
<syntaxhighlight lang="lisp">
<lang Lisp>
; There are different algorithms to solve this problem, such as adding areas, adding angles, etc... but these
; solutions are sensitive to rounding errors intrinsic to float operations. We want to avoid these issues, therefore we
Line 581 ⟶ 782:
(- (car P) (car A)) ))))
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 601 ⟶ 802:
 
=={{header|D}}==
 
{{trans|C++}}
<syntaxhighlight lang="d">
<lang d>import std.algorithm; //.comparison for min and max
import std.algorithm;
import std.stdio;
 
Line 683 ⟶ 885:
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;
Line 692 ⟶ 898:
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
writeln;
}
}</lang>
</syntaxhighlight>
 
{{out}}
<pre>
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
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
Line 705 ⟶ 916:
 
Triangle is [(0.1, 0.111111), (12.5, 33.3333), (-12.5, 16.6667)]
Point (5.41429, 14.3492) is within triangle? true</pre>
</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{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">
{Vector structs and operations - these would normally be in}
{a library, but are produced here so everything is explicit}
 
type T2DVector=packed record
X,Y: double;
end;
 
type T2DLine = packed record
P1,P2: T2DVector;
end;
 
type T2DTriangle = record
P1,P2,P3: T2DVector;
end;
 
 
 
function MakeVector2D(const X,Y: double): T2DVector;
begin
Result.X:=X;
Result.Y:=Y;
end;
 
 
function Make2DLine(const P1,P2: T2DVector): T2DLine; overload;
begin
Result.P1:=P1;
Result.P2:=P2;
end;
 
 
 
function MakeTriangle2D(P1,P2,P3: T2DVector): T2DTriangle;
begin
Result.P1:=P1; Result.P2:=P2; Result.P3:=P3;
end;
 
 
{Point-Line position constants}
 
const RightPos = -1;
const LeftPos = +1;
const ColinearPos = 0;
 
function LinePointPosition(Line: T2DLine; Point: T2DVector): integer;
{Test the position of point relative to the line}
{Returns +1 = right side, -1 = left side, 0 = on the line}
var Side: double;
begin
{ Use the determinate to find which side of the line a point is on }
Side := (Line.P2.X - Line.P1.X) * (Point.Y - Line.P1.Y) - (Point.X - Line.P1.X) * (Line.P2.Y - Line.P1.Y);
{Return +1 = right side, -1 = left side, 0 = on the line}
if Side > 0 then Result := LeftPos
else if Side < 0 then Result := RightPos
else Result := ColinearPos;
end;
 
 
function PointInTriangle2D(P: T2DVector; Tri: T2DTriangle): boolean; overload;
{Check if specified point is inside the specified Triangle}
var Side1,Side2,Side3: integer;
var L: T2DLine;
begin
{Get the side the point falls on for the first two sides of triangle}
Side1 := LinePointPosition(Make2DLine(Tri.P1,Tri.P2),P);
Side2 := LinePointPosition(Make2DLine(Tri.P2,Tri.P3),P);
 
{If they are on different sides, the point must be outside}
if (Side1 * Side2) = -1 then Result := False
else
begin
{The point is inside the first two sides, so check the third side}
Side3 := LinePointPosition(Make2DLine(Tri.P3,Tri.P1),P);
{Use the three}
if (Side1 = Side3) or (Side3 = 0) then Result := True
else if Side1 = 0 then Result := (Side2 * Side3) >= 0
else if Side2 = 0 then Result := (Side1 * Side3) >= 0
else Result := False;
end;
end;
 
{-------------- Test routines -------------------------------------------------}
 
 
procedure DrawTriangle(Canvas: TCanvas; T: T2DTriangle);
{Draw triangles on any canvas}
begin
Canvas.Pen.Color:=clBlack;
Canvas.Pen.Mode:=pmCopy;
Canvas.Pen.Style:=psSolid;
Canvas.Pen.Width:=2;
Canvas.MoveTo(Trunc(T.P1.X),Trunc(T.P1.Y));
Canvas.LineTo(Trunc(T.P2.X),Trunc(T.P2.Y));
Canvas.LineTo(Trunc(T.P3.X),Trunc(T.P3.Y));
Canvas.LineTo(Trunc(T.P1.X),Trunc(T.P1.Y));
end;
 
 
 
procedure DrawPoint(Canvas: TCanvas; X,Y: integer; InTri: boolean);
{Draw a test point on a canvas and mark if "In" or "Out"}
begin
Canvas.Pen.Color:=clRed;
Canvas.Pen.Width:=8;
Canvas.MoveTo(X-1,Y);
Canvas.LineTo(X+1,Y);
Canvas.MoveTo(X,Y-1);
Canvas.LineTo(X,Y+1);
Canvas.Font.Size:=12;
Canvas.Font.Style:=[fsBold];
if InTri then Canvas.TextOut(X+5,Y,'In')
else Canvas.TextOut(X+5,Y,'Out');
end;
 
 
 
procedure TestPointInTriangle(Image: TImage);
{Draw triangle and display test points}
var Tri: T2DTriangle;
var P: TPoint;
begin
{Create and draw Triangle}
Tri:=MakeTriangle2D(MakeVector2D(50,50),MakeVector2D(300,80),MakeVector2D(150,250));
DrawTriangle(Image.Canvas,Tri);
 
{Draw six test points}
P:=Point(62,193);
DrawPoint(Image.Canvas,P.X,P.Y, PointInTriangle2D(MakeVector2D(P.X,P.Y),Tri));
P:=Point(100,100);
DrawPoint(Image.Canvas,P.X,P.Y, PointInTriangle2D(MakeVector2D(P.X,P.Y),Tri));
P:=Point(200,100);
DrawPoint(Image.Canvas,P.X,P.Y, PointInTriangle2D(MakeVector2D(P.X,P.Y),Tri));
P:=Point(150,30);
DrawPoint(Image.Canvas,P.X,P.Y, PointInTriangle2D(MakeVector2D(P.X,P.Y),Tri));
P:=Point(250,200);
DrawPoint(Image.Canvas,P.X,P.Y, PointInTriangle2D(MakeVector2D(P.X,P.Y),Tri));
P:=Point(150,200);
DrawPoint(Image.Canvas,P.X,P.Y, PointInTriangle2D(MakeVector2D(P.X,P.Y),Tri));
end;
 
</syntaxhighlight>
{{out}}
 
[[File:PintInTriangle.png|frame|none]]
<pre>
 
</pre>
 
 
=={{header|Dart}}==
{{trans|C++}}
<syntaxhighlight lang="dart">import 'dart:math';
 
const double EPS = 0.001;
const double 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;
if (checkSide1 >= 0 && checkSide2 >= 0 && checkSide3 >= 0) {
return true;
} else {
return false;
}
}
 
bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y) {
double xMin = min(x1, min(x2, x3)) - EPS;
double xMax = max(x1, max(x2, x3)) + EPS;
double yMin = min(y1, min(y2, y3)) - EPS;
double yMax = max(y1, max(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 printTriangle(
double x1, double y1, double x2, double y2, double x3, double y3) {
print("Triangle is [($x1, $y1), ($x2, $y2), ($x3, $y3)]");
}
 
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);
print("Point ($x, $y) is within triangle? ");
if (accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
print("true");
} else {
print("false");
}
}
 
void main() {
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);
print('');
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25, 11.11111111111111,
5.414285714285714, 14.349206349206348);
print('');
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5,
16.666666666666668, 5.414285714285714, 14.349206349206348);
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}}==
Uses the parametric equations method from [https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html].
<langsyntaxhighlight lang="factor">USING: accessors fry io kernel locals math math.order sequences ;
 
TUPLE: point x y ;
Line 734 ⟶ 1,294:
3 3 <point> 16 10 <point> 10 16 <point> <triangle> ! Make a triangle
'[ [ _ point-in-triangle? "#" "." ? write ] each nl ] each nl ! Show points inside the triangle with '#'
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 760 ⟶ 1,320:
 
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
<lang Fortran>
PROGRAM POINT_WITHIN_TRIANGLE
 
Line 819 ⟶ 1,379:
 
END PROGRAM POINT_WITHIN_TRIANGLE
</syntaxhighlight>
</lang>
{{out}}<pre>
Point ( 0.0000000000000000 , 0.0000000000000000 ) is within triangle [( 1.5000000000000000 , 2.4000000953674316 ), ( 5.0999999046325684 , -3.0999999046325684 ), ( -3.7999999523162842 , 1.2000000476837158 )].
Line 825 ⟶ 1,385:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">
type p2d
x as double 'define a two-dimensional point
Line 855 ⟶ 1,415:
print
next y
</syntaxhighlight>
</lang>
{{out}}<pre>........................................
........................................
Line 877 ⟶ 1,437:
........................................
</pre>
 
 
 
 
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_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)
WindowSubclassContentView(_window)
ViewSetFlipped( _windowContentViewTag, YES )
ViewSetNeedsDisplay( _windowContentViewTag )
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( 300, 300 ) )
BezierPathLineToPoint( path, fn CGPointMake( 150, 30 ) )
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)
case _viewMouseDown : fn DoMouse( tag )
case _viewMouseMoved : fn DoMouse( tag )
end select
end fn
 
fn BuildWindow
 
on dialog fn DoDialog
 
HandleEvents
</syntaxhighlight>
{{output}}
[[File:FB Find Point in a Triangle.png]]
 
=={{header|Go}}==
{{trans|Wren}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 971 ⟶ 1,588:
within = accuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
fmt.Println("Point", pt, "is within triangle ?", within)
}</langsyntaxhighlight>
 
{{out}}
Line 988 ⟶ 1,605:
 
=={{header|GW-BASIC}}==
<langsyntaxhighlight lang="gwbasic">10 PIT1X! = 3 : PIT1Y! = 1.3 : REM arbitrary triangle for demonstration
20 PIT2X! = 17.222 : PIT2Y! = 10
30 PIT3X! = 5.5 : PIT3Y! = 18.212
Line 1,012 ⟶ 1,629:
1110 IF PITXXS!+PITXXT!>=1 THEN RETURN
1120 PITRES% = 1
1130 RETURN</langsyntaxhighlight>
{{out}}<pre>.........................................
.........................................
Line 1,039 ⟶ 1,656:
The point to be tested is transformed by affine transformation which turns given triangle to the simplex: Triangle (0,0) (0,s) (s,0), where s is half of the triangles' area. After that criteria of overlapping become trivial. Affinity allows to avoid division, so all functions work for points on the integer, or rational, or even modular meshes as well.
 
<langsyntaxhighlight lang="haskell">type Pt a = (a, a)
 
data Overlapping = Inside | Outside | Boundary
Line 1,070 ⟶ 1,687:
(y <= s && y >= 0) &&
(x == 0 || y == 0 || y == s - x) -> Boundary
| otherwise -> Outside</langsyntaxhighlight>
 
Testing
<langsyntaxhighlight lang="haskell">tests = let
t1 = Triangle (2,0) (-1,2) (-2,-2)
bs = [(2,0), (-1,2), (-2,-2), (0,-1), (1/2,1), (-3/2,0)]
Line 1,093 ⟶ 1,710:
| i <- [-10..10] :: [Int] ]
| j <- [-5..5] :: [Int] ]
where t = Triangle (-8,-3) (8,1) (-1,4)</langsyntaxhighlight>
 
<pre>λ> tests
Line 1,113 ⟶ 1,730:
·········+···········
·····················</pre>
 
=={{header|J}}==
Implementation, using complex numbers to represent x,y coordinates:
<syntaxhighlight lang="j">area=: [:| 0.5-/ .*@,.+. NB. signed area of triangle
I3=: =i.3 NB. identity matrix
inside=: {{ (area y)=+/area"1|:(I3*x)+(1-I3)*y }}</syntaxhighlight>
 
This is based on the algorithm documented for the ada implementation: compute the area of triangles using the determinant method (we want the absolute area here), and check whether the triangles formed with the test point and the sides of the test triangle matches the area of the test triangle.
 
Examples:<syntaxhighlight lang="j"> 0j0 inside 1.5j2.4 5.1j_3.1 _3.8j1.2
1
0j1 inside 1.5j2.4 5.1j_3.1 _3.8j1.2
1
3j1 inside 1.5j2.4 5.1j_3.1 _3.8j1.2
0
5.414285714285714j14.349206349206348 inside 0.1j1r9 12.5j100r3 25j100r9
1
5.414285714285714j14.349206349206348 inside 0.1j1r9 12.5j100r3 _12.5j100r6
1</syntaxhighlight>
 
=={{header|Java}}==
{{trans|Go}}
<langsyntaxhighlight lang="java">import java.util.Objects;
 
public class FindTriangle {
Line 1,251 ⟶ 1,887:
test(tri, pt);
}
}</langsyntaxhighlight>
{{out}}
<pre>Triangle[(1.500000, 2.400000), (5.100000, -3.100000), (-3.800000, 1.200000)]
Line 1,265 ⟶ 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 1,277 ⟶ 2,027:
 
'''Preliminaries'''
<langsyntaxhighlight lang="jq">def sum_of_squares(stream): reduce stream as $x (0; . + $x * $x);
 
def distanceSquared(P1; P2): sum_of_squares(P1[0]-P2[0], P1[1]-P2[1]);
Line 1,291 ⟶ 2,041:
 
def EPS: 0.001;
def EPS_SQUARE: EPS * EPS; </langsyntaxhighlight>
<langsyntaxhighlight lang="jq">def side(P1; P2; Q):
[P1, P2, Q]
| xy
Line 1,330 ⟶ 2,080:
elif distanceSquarePointToSegment(P3; P1; Q) <= EPS_SQUARE then true
else false
end;</langsyntaxhighlight>
'''Examples'''
<langsyntaxhighlight lang="jq">def task1:
def pts: [ [0, 0], [0, 1], [3, 1]];
"Triangle is \(.)",
Line 1,351 ⟶ 2,101:
([ [3/2, 12/5], [51/10, -31/10], [-19/5, 1.2] ] | task1), "",
([ [1/10, 1/9], [100/8, 100/3], [100/4, 100/9] ] | task2), "",
([ [1/10, 1/9], [100/8, 100/3], [-100/8, 100/6] ] | task2)</langsyntaxhighlight>
{{out}}
<pre>
Line 1,369 ⟶ 2,119:
{{trans|Python}}
Using the Wren examples.
<langsyntaxhighlight lang="julia">Point(x, y) = [x, y]
Triangle(a, b, c) = [a, b, c]
LEzero(x) = x < 0 || isapprox(x, 0, atol=0.00000001)
Line 1,415 ⟶ 2,165:
end
end
</langsyntaxhighlight>{{out}}
<pre>
Using triangle [[1.5, 2.4], [0.51, -0.31], [-0.38, 1.2]]:
Line 1,438 ⟶ 2,188:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">import kotlin.math.max
import kotlin.math.min
 
Line 1,533 ⟶ 2,283:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>Triangle[(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 1,550 ⟶ 2,300:
=={{header|Lua}}==
{{trans|C++}}
<langsyntaxhighlight lang="lua">EPS = 0.001
EPS_SQUARE = EPS * EPS
 
Line 1,634 ⟶ 2,384:
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348)
print()</langsyntaxhighlight>
{{out}}
<pre>Triangle is [(1.5, 2.4), (5.1, -3.1), (-3.8, 1.2)]
Line 1,650 ⟶ 2,400:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">RegionMember[Polygon[{{1, 2}, {3, 1}, {2, 4}}], {2, 2}]</langsyntaxhighlight>
{{out}}
<pre>True</pre>
Line 1,656 ⟶ 2,406:
=={{header|Nim}}==
{{trans|Kotlin}}
<langsyntaxhighlight Nimlang="nim">import strformat
 
const
Line 1,741 ⟶ 2,491:
p3 = (-100 / 8, 100 / 6)
tri = initTriangle(p1, p2, p3)
test(tri, pt)</langsyntaxhighlight>
 
{{out}}
Line 1,759 ⟶ 2,509:
=={{header|Perl}}==
Translate the Java program at [https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html this blog post] and data set is taken from the [[Find_if_a_point_is_within_a_triangle#Raku|Raku]] entry.
<langsyntaxhighlight Perllang="perl"># 20201123 added Perl programming solution
 
use strict;
Line 1,821 ⟶ 2,571:
while ( my @vertex = $iter->()) { print '(',join(',',@vertex),') ' }
print ': ',naivePointInTriangle (@DATA, @$point) ? 'True' : 'False', "\n" ;
}</langsyntaxhighlight>
{{out}}
<pre>Point (0,0) is within triangle (1.5,2.4) (5.1,-3.1) (-3.8,0.5) : True
Line 1,831 ⟶ 2,581:
=== using convex_hull ===
Using convex_hull() from [[Convex_hull#Phix]]
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">p0</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>
Line 1,843 ⟶ 2,593:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inside</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,853 ⟶ 2,603:
===trans python===
(same output)
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">p0</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>
Line 1,888 ⟶ 2,638:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"point %v is with triangle %v?:%t\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iswithin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">triangle</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">
""" find if point is in a triangle """
 
Line 1,923 ⟶ 2,673:
isornot = "is" if iswithin(pnt, a, b, c) else "is not"
print("Point", pnt, isornot, "within the triangle", TRI)
</langsyntaxhighlight>{{out}}
<pre>
Point Point2D(0, 0) is within the triangle Triangle(Point2D(3/2, 12/5), Point2D(51/10, -31/10), Point2D(-19/5, 1/2))
Line 1,937 ⟶ 2,687:
I would probably use the dot-product version, if only because it requires less (no) division.
 
<langsyntaxhighlight lang="racket">#lang racket/base
 
(define-syntax-rule (all-between-0..1? x ...)
Line 1,984 ⟶ 2,734:
(run-tests point-in-triangle?/barycentric)
(run-tests point-in-triangle?/parametric)
(run-tests point-in-triangle?/dot-product))</langsyntaxhighlight>
 
{{out}}
Line 1,994 ⟶ 2,744:
Reusing code from the [[Convex_hull#Raku|Convex hull]] task and some logic from the [[Determine_if_two_triangles_overlap#Raku|Determine if two triangles overlap]] task.
 
<syntaxhighlight lang="raku" perl6line>class Point {
has Real $.x is rw;
has Real $.y is rw;
Line 2,021 ⟶ 2,771:
say "Point {$point.gist} is within triangle {join ', ', @triangle».gist}: ",
$point.&is-within: @triangle
}</langsyntaxhighlight>
{{out}}
<pre>Point (0, 0) is within triangle (1.5, 2.4), (5.1, -3.1), (-3.8, 0.5): True
Line 2,031 ⟶ 2,781:
 
<br>Extra certification code was added to verify that the &nbsp; '''X,Y''' &nbsp; coördinates for the points are not missing and are numeric.
<langsyntaxhighlight lang="rexx">/*REXX program determines if a specified point is within a specified triangle. */
parse arg p a b c . /*obtain optional arguments from the CL*/
if p=='' | p=="," then p= '(0,0)' /*Not specified? Then use the default.*/
Line 2,047 ⟶ 2,797:
y: procedure; parse arg ',' y ")"; return cert(y,"Y") /* " " Y " */
$: parse arg aa,bb,cc; return (x(aa)-x(cc)) *(y(bb)-y(cc)) - (x(bb)-x(cc)) *(y(aa)-y(cc))
?: #1=$(p,a,b); #2=$(p,b,c); #3=$(p,c,a); return (#1>=0&#2>=0&#3>=0) | (#1<=0&#2<=0&#3<=0)</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default triangle and the point at: &nbsp; <tt> (0,0) </tt>}}
<pre>
Line 2,059 ⟶ 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>
 
=={{header|Ruby}}==
{{trans|Go}}
<langsyntaxhighlight lang="ruby">EPS = 0.001
EPS_SQUARE = EPS * EPS
 
Line 2,150 ⟶ 2,924:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>Triangle is [[1.5, 2.4], [5.1, -3.1], [-3.8, 1.2]]
Line 2,163 ⟶ 2,937:
Point [5.414285714285714, 14.349206349206348] is within triangle? true</pre>
 
=={{header|VlangRust}}==
{{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)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">import math
 
const eps = 0.001
Line 2,251 ⟶ 3,142:
within = accurate_point_in_triangle(x1, y1, x2, y2, x3, y3, x, y)
println("Point $pt is within triangle ? $within")
}</langsyntaxhighlight>
 
{{out}}
Line 2,269 ⟶ 3,160:
=={{header|Wren}}==
This is a translation of the ActionScript code for the 'accurate' method in the first referenced article above.
<langsyntaxhighlight ecmascriptlang="wren">var EPS = 0.001
var EPS_SQUARE = EPS * EPS
 
Line 2,349 ⟶ 3,240:
y3 = tri[2][1]
within = accuratePointInTriangle.call(x1, y1, x2, y2, x3, y3, x, y)
System.print("Point %(pt) is within triangle ? %(within)")</langsyntaxhighlight>
 
{{out}}
Line 2,366 ⟶ 3,257:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">func real Dot(W,X,Y,Z); \Return the dot product of two 2D vectors
real W,X,Y,Z; \ (W-X) dot (Y-Z)
real WX(2), YZ(2);
Line 2,389 ⟶ 3,280:
Text(0, if PointInTri([-5.0,-2.2]) then "inside" else "outside"); CrLf(0);
Text(0, if PointInTri([10.5, 6.3]) then "inside" else "outside"); CrLf(0);
]</langsyntaxhighlight>
 
{{out}}
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/303888...354358"