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

8,056 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
m (→‎{{header|Evaldraw}}: dist0 considered inside. add comment about positive quadrant)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(10 intermediate revisions by 5 users not shown)
Line 802:
 
=={{header|D}}==
 
{{trans|C++}}
<syntaxhighlight lang="d">import std.algorithm; //.comparison for min and max
import std.algorithm;
import std.stdio;
 
Line 884 ⟶ 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 893 ⟶ 898:
test(0.1, 0.1111111111111111, 12.5, 33.333333333333336, -12.5, 16.666666666666668, 5.414285714285714, 14.349206349206348);
writeln;
}
}</syntaxhighlight>
</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 906 ⟶ 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}}==
Line 1,165 ⟶ 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,171 ⟶ 1,183:
<syntaxhighlight lang="c">struct vec2{x,y;};
struct line_t{a,b,c;};
struct triangle_calc_t{
 
vec2 origin;
// Our triangle defined by 3 points in the cartesian 2D plane.
static vec2 verticesline_t lines[3];
vec2 min,max;
enum{WIND_ANTI_CLOCKWISE=-1, WIND_CLOCKWISE=1}
double area2;
static winding_dir = -1; // +1 if clockwise (positive angle) -1 if negative.
winding_dir; // +1 if clockwise (positive angle) -1 if negative.
static line_t line0, line1, line2;
};
static area2; // 2x tri area
//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);
// Three line equations of the form a+b+c=0
// This can be set up one and reused for all points
// we may want to test for a given triangle.
// In a real program, you may want to store this with the triangle.
vec2 dat[3] = {0,-2, -2,2, 4,0};
for(i=0; i<3; i++) {
vertices[i].x = dat[i].x + 2;
vertices[i].y = dat[i].y + 2;
}
makeLine(line0, vertices[0], vertices[1]);
makeLine(line1, vertices[1], vertices[2]);
makeLine(line2, vertices[2], vertices[0]);
area2 = areaTriangleX2(vertices[0], vertices[1], vertices[2]);
winding_dir = sgn(area2);
}
d0 = d1 = d2 = 0; // Distances of point to lines
vec2 screenPointpoint = {x, y};
side = isPointInsideTriangle(point,triangle,d0,d1,d2);
d0 = d1 = d2 = 0;
if (side == TRI_INSIDE) {
if ( isPointInside( screenPoint, line0, line1, line2, d0, d1, d2) ) {
if (triangle.winding_dir == -1) {
swap(d0,d1,d2);
swap(d1,d0);
}
r_area = 1.0 / (triangle.winding_dir * triangle.area2);
r = 255*( d1 / area2); // RGB only within 0-255 range if tri verts in positive cartesian quadrant
gr = 255 *( d2r_area /* area2)d2;
bg = 255 *( d0r_area /* area2)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]) {
isPointInside(vec2 p, line_t line0, line_t line1, line_t line2, &d0,&d1,&d2) {
t.area2 = triangleAreaTimes2(verts[0], verts[1], verts[2]);
d0 = lineDist( line0, p.x, p.y);
if (t.area2 winding_dir*sgn(d0) <== 0 ) return 0;
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( line1t.lines[1], p.x, p.y);
if (d1==0) { return TRI_EDGE; } else if ( winding_dir*sgn(d1) <= 0 ) return 0TRI_OUT;
d2 = t.winding_dir * lineDist( line2t.lines[2], p.x, p.y);
if (d2==0) { return TRI_EDGE; } else if ( winding_dir*sgn(d2) <= 0 ) return TRI_OUT;
return 1TRI_INSIDE; // We are on the right side.inside
// If we wanted to find the exact distance the point is
// to any line we could the min of d0,d1,d2.
}
 
Line 1,231 ⟶ 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;
}
areaTriangleX2(vec2 a, vec2 b, vec2 c) { // Same as the determinant, but dont div by 2
( a.x*(b.y - c.y) + b.x*(c.y - b.y) + c.x*(a.y - b.y) );
}
swap(&a,&b) {tmp = a; a=b; b=tmp; }</syntaxhighlight>
 
Line 1,418 ⟶ 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 )
'~'1
WindowCenter(_window)
window _window, @"Find if a point is within a triangle", (0, 0, 340, 360 )
WindowCenter WindowSubclassContentView(_window)
ViewSetFlipped( _windowContentViewTag, YES )
WindowSubclassContentView(_window)
ViewSetFlipped ViewSetNeedsDisplay( _windowContentViewTag, YES )
ViewSetNeedsDisplay( _windowContentViewTag )
subclass textLabel _textLabel, @"", ( 20, 320, 300, 20 ), _window
 
subclass textLabel _textLabel, @"", ( 20, 320, 300, 20 ), _window
end fn
 
void local fn DrawInView( tag as NSInteger )
BezierPathRef path = fn BezierPathInit
'~'1
BezierPathMoveToPoint( path, fn CGPointMake( 30, 300 ) )
BezierPathRef path = fn BezierPathInit
BezierPathMoveToPoint BezierPathLineToPoint( path, fn CGPointMake( 30300, 300 ) )
BezierPathLineToPoint( path, fn CGPointMake( 300150, 300 30 ) )
BezierPathClose( path )
BezierPathLineToPoint( path, fn CGPointMake( 150, 30 ) )
BezierPathStrokeFill( path, 3.0, fn ColorBlack, fn ColorGreen )
BezierPathClose( path )
AppSetProperty( @"path", 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 )
'~'1
if ( fn BezierPathContainsPoint( fn AppProperty( @"path" ), pt ) )
CGPoint pt = fn EventLocationInView( tag )
ControlSetStringValue( _textLabel, fn StringWithFormat( @"Inside triangle: x = %.f y = %.f", pt.x, pt.y ) )
if ( fn BezierPathContainsPoint( fn AppProperty( @"path" ), pt ) )
else
ControlSetStringValue( _textLabel, fn StringWithFormat( @"Inside triangle: x = %.f y = %.f", pt.x, pt.y ) )
ControlSetStringValue( _textLabel, fn StringWithFormat( @"Outside triangle: x = %.f y = %.f", pt.x, pt.y ) )
else
end if
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 )
'~'1
case _viewDrawRect : fn DrawInView(tag)
select ( ev )
case _viewDrawRect case _viewMouseDown : fn DrawInViewDoMouse( tag )
case _viewMouseDown case _viewMouseMoved : fn DoMouse( tag )
end select
case _viewMouseMoved : fn DoMouse( tag )
end select
end fn
 
Line 1,470 ⟶ 1,494:
{{output}}
[[File:FB Find Point in a Triangle.png]]
 
 
 
=={{header|Go}}==
Line 1,879 ⟶ 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,673 ⟶ 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,776 ⟶ 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,883 ⟶ 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/354347...354358"