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

7,300 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
No edit summary
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(4 intermediate revisions by 3 users not shown)
Line 799:
(point-inside-triangle '(5.414286 . 14.349206) '(0.1 . 0.111111) '(12.5 . 33.333333) '(-12.5 . 16.666667))
NIL
</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>
 
Line 1,056 ⟶ 1,174:
=={{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;
This solution makes use of the x,y plotting function. It allows us to plot an arbitrary function of x,y and set r,g,b colors before we return. This allows us to test all points in the cartesian space and we can pan and zoom the viewport, or mouse over an x,y position we want to see the computed RGB value for. The isPointInside function here works in similar way to many other solutions here, for the 3 points of a triangle we compute 3 line equations. The line equations when evaluated for a x,y point give the distance from the point to the line. The distance is signed. We can use this to return early from isPointInside. Only if all three lines give a result with the same sign can the point 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.
 
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]]
Line 1,065 ⟶ 1,186:
vec2 origin;
line_t lines[3];
vec2 vertices[3]min,max;
double area2;
winding_dir; // +1 if clockwise (positive angle) -1 if negative.
};
//static vec2 datvertices[3] = {0,-2, -2,2, 4,0};
static vec2 datvertices[3] = {-3,7, -6,-5, 2,2};
enum{TRI_OUT, TRI_ZERO, TRI_EDGE, TRI_INSIDE}
static triangle_calc_t tri;
static triangle_calc_t triangle;
enum{TRI_OUT=0, TRI_EDGE=1, TRI_INSIDE=2}
(x,y,t,&r,&g,&b)
{
if (numframes==0) {
precalc_tri( triangle, vertices);
{
precalc_tri( tri, dat);
}
d0 = d1 = d2 = 0; // Distances of point to lines
 
d0vec2 = d1point = d2 ={x, 0y};
side = isPointInsideTriangle(xpoint,y,tritriangle,d0,d1,d2);
if (side == TRI_EDGETRI_INSIDE) {
if (triangle.winding_dir == -1) {
r=255; g=255; b=0;
return 1 swap(d1,d2);
swap(d1,d0);
}
else if (side == TRI_INSIDE) {
if (tri.winding_dir == -1) {
swap(d0,d1);
}
r_area = 1.0 / (triangle.winding_dir * triangle.area2);
factor = 255;
divr = tri.winding_dir255 * tri.area2r_area * d2;
rg = factor255 *( d1r_area /* div)d0;
gb = factor255 * r_area *( d2d1; /return div)1;
b = factor*( d0 / div);
return 1;
}
r=0; g=0; b=0; return 0; // Set color to 0 if outside.
Line 1,101 ⟶ 1,216:
 
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.vertices[i]min.x = min(t.min.x, verts[i].x + t.origin.x);
t.vertices[i]min.y = min(t.min.y, verts[i].y + t.origin.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], t.verticesrelative_vertices[0], t.verticesrelative_vertices[1]);
makeLine(t.lines[1], t.verticesrelative_vertices[1], t.verticesrelative_vertices[2]);
makeLine(t.lines[2], t.verticesrelative_vertices[2], t.verticesrelative_vertices[0]);
t.area2 = areaTriangleX2(t.vertices[0], t.vertices[1], t.vertices[2]);
t.winding_dir = sgn(tri.area2);
}
areaTriangleX2triangleAreaTimes2(vec2 a, vec2 b, vec2 c) { // Same as the determinant, but dont div by 2
s =return c.x*(a.y-b.y)+a.x*(b.y-c.y)+b.x*(-a.y+c.y);
}
isPointInsideTriangle(x,y vec2 point, triangle_calc_t t, &d0,&d1,&d2) {
if (t.area2 == 0) return TRI_ZERO;
vec2 p = {x + t.origin.x, y + t.origin.y };
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;
Line 1,134 ⟶ 1,264:
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; }
x*line.a + y*line.b + line.c;
}
swap(&a,&b) {tmp = a; a=b; b=tmp; }</syntaxhighlight>
 
Line 1,773 ⟶ 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,918 ⟶ 3,160:
=={{header|Wren}}==
This is a translation of the ActionScript code for the 'accurate' method in the first referenced article above.
<syntaxhighlight lang="ecmascriptwren">var EPS = 0.001
var EPS_SQUARE = EPS * EPS
 
PureFox
9,476

edits

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