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,326 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(6 intermediate revisions by 3 users not shown)
Line 801:
</pre>
 
=={{header|RustD}}==
{{trans|D}}
 
<syntaxhighlight lang="rustd">
import std.algorithm;
const EPS: f64 = 0.001;
import std.stdio;
const EPS_SQUARE: f64 = EPS * EPS;
 
immutable EPS = 0.001;
fn side(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> f64 {
immutable EPS_SQUARE = EPS * EPS;
(y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1)
 
double side(double x1, double y1, double x2, double y2, double x, double y) {
return (y2 - y1) * (x - x1) + (-x2 + x1) * (y - y1);
}
 
fnbool naive_point_in_trianglenaivePointInTriangle(double x1: f64, double y1: f64, double x2: f64, double y2: f64, double x3: f64, y3:double f64y3, x:double f64x, double y: f64) -> bool {
letdouble check_side1checkSide1 = side(x1, y1, x2, y2, x, y) >= 0.0;
letdouble check_side2checkSide2 = side(x2, y2, x3, y3, x, y) >= 0.0;
letdouble check_side3checkSide3 = side(x3, y3, x1, y1, x, y) >= 0.0;
check_side1return checkSide1 && check_side2checkSide2 && check_side3checkSide3;
}
 
bool pointInTriangleBoundingBox(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
fn point_in_triangle_bounding_box(x1: f64, y1: f64, x2: f64, y2: f64, x3: f64, y3: f64, x: f64, y: f64) -> bool {
letdouble x_minxMin = f64::min(x1, f64::min(x2, x3)) - EPS;
letdouble x_maxxMax = f64::max(x1, f64::max(x2, x3)) + EPS;
letdouble y_minyMin = f64::min(y1, f64::min(y2, y3)) - EPS;
letdouble y_maxyMax = f64::max(y1, f64::max(y2, y3)) + EPS;
return !(x < x_minxMin || x_maxxMax < x || y < y_minyMin || y_maxyMax < y);
}
 
double distanceSquarePointToSegment(double x1, double y1, double x2, double y2, double x, double y) {
fn distance_square_point_to_segment(x1: f64, y1: f64, x2: f64, y2: f64, x: f64, y: f64) -> f64 {
letdouble p1_p2_square_lengthp1_p2_squareLength = (x2 - x1).powi * (2x2 - x1) + (y2 - y1).powi * (2y2 - y1);
letdouble dot_productdotProduct = ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) / p1_p2_square_lengthp1_p2_squareLength;
if dot_product(dotProduct < 0.0) {
return (x - x1).powi * (2x - x1) + (y - y1).powi * (2y - y1);
} else if dot_product(dotProduct <= 1.0) {
letdouble p_p1_square_lengthp_p1_squareLength = (x1 - x).powi * (2x1 - x) + (y1 - y).powi * (2y1 - y);
return p_p1_squareLength - dotProduct * dotProduct * p1_p2_squareLength;
p_p1_square_length - dot_product.powi(2) * p1_p2_square_length
} else {
return (x - x2).powi * (2x - x2) + (y - y2).powi * (2y - y2);
}
}
 
bool accuratePointInTriangle(double x1, double y1, double x2, double y2, double x3, double y3, double x, double y) {
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_boxpointInTriangleBoundingBox(x1, y1, x2, y2, x3, y3, x, y)) {
return false;
}
if naive_point_in_triangle(naivePointInTriangle(x1, y1, x2, y2, x3, y3, x, y)) {
return true;
}
if distance_square_point_to_segment(distanceSquarePointToSegment(x1, y1, x2, y2, x, y) <= EPS_SQUARE) {
return true;
}
if distance_square_point_to_segment(distanceSquarePointToSegment(x2, y2, x3, y3, x, y) <= EPS_SQUARE) {
return true;
}
if distance_square_point_to_segment(distanceSquarePointToSegment(x3, y3, x1, y1, x, y) <= EPS_SQUARE) {
return true;
}
return false;
}
 
fnvoid print_pointprintPoint(x:double f64x, y:double f64y) {
print!write("'({}', x, {})", x", y, ')');
}
 
fnvoid print_triangleprintTriangle(x1:double f64x1, y1:double f64y1, x2:double f64x2, y2:double f64y2, x3:double f64x3, y3:double f64y3) {
print!write("Triangle is [");
print_pointprintPoint(x1, y1);
print!write(", ");
print_pointprintPoint(x2, y2);
print!write(", ");
print_pointprintPoint(x3, y3);
println!writeln("']"');
}
 
fnvoid test(x1:double f64x1, y1:double f64y1, x2:double f64x2, y2:double f64y2, x3:double f64x3, y3:double f64y3, x:double f64x, y:double f64y) {
print_triangleprintTriangle(x1, y1, x2, y2, x3, y3);
print!write("Point ");
print_pointprintPoint(x, y);
print!write(" is within triangle? ");
println!writeln("{}", accurate_point_in_triangleaccuratePointInTriangle(x1, y1, x2, y2, x3, y3, x, y));
}
 
fnvoid main() {
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0.0, 0.0);
writeln;
println!();
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 0.0, 1.0);
writeln;
println!();
test(1.5, 2.4, 5.1, -3.1, -3.8, 1.2, 3.0, 1.0);
println!()writeln;
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, 25.0, 11.11111111111111, 5.414285714285714, 14.349206349206348);
println!()writeln;
 
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
println!()writeln;
}
</syntaxhighlight>
Line 910 ⟶ 912:
Point (3, 1) is within triangle? false
 
Triangle is [(0.1, 0.1111111111111111111111), (12.5, 33.3333333333333363333), (25, 11.111111111111111111)]
Point (5.41428571428571441429, 14.3492063492063483492) is within triangle? true
 
Triangle is [(0.1, 0.1111111111111111111111), (12.5, 33.3333333333333363333), (-12.5, 16.6666666666666686667)]
Point (5.41428571428571441429, 14.3492063492063483492) is within triangle? true
</pre>
 
Line 1,172 ⟶ 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,181 ⟶ 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,217 ⟶ 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,250 ⟶ 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,889 ⟶ 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,810 ⟶ 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,917 ⟶ 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/354351...354358"