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

11,791 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(13 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,162 ⟶ 1,171:
print('');
}</syntaxhighlight>
 
=={{header|Evaldraw}}==
 
This solution makes use of the (x,y,t,&r,&g,&b) plotting function. It evaluates an function in the cartesian plane. Given x,y inputs, the function is expected to set r,g,b color channels. The program tests all points in the viewport. You may pan and zoom. The current mouse position shows the computed RGB at that point. The isPointInsideTriangle-function here works in similar way to other solutions here;
 
for the 3 points of a triangle we compute 3 line equations that will be evaluated to get the signed distance from the line to a point.
We can use this to return early from isPointInsideTriangle. Only if all three lines give a result with the point on the same side (same sign) then the point can be classified as inside the triangle. We can use this property of sidedness and sign to make the method work for both clockwise and anti-clockwise specification of the triangle vertices. If the triangle is clockwise, then the area function returns a positive value. If the triangle is anti clockwise, then the area function returns a negative value, and we can multiply the sgn checks by -1 so a point can still be considered inside. A point with distance 0 is also considered inside.
 
[[File:Evaldraw points in triangle.png|thumb|alt=A triangle with vertices set to red, green and blue with interpolation over surface.|plot mode (x,y,&r,&g,&b) allows for plotting of arbitrary functions of (x,y) and return rgb]]
 
<syntaxhighlight lang="c">struct vec2{x,y;};
struct line_t{a,b,c;};
struct triangle_calc_t{
vec2 origin;
line_t lines[3];
vec2 min,max;
double area2;
winding_dir; // +1 if clockwise (positive angle) -1 if negative.
};
//static vec2 vertices[3] = {0,-2, -2,2, 4,0};
static vec2 vertices[3] = {-3,7, -6,-5, 2,2};
enum{TRI_OUT, TRI_ZERO, TRI_EDGE, TRI_INSIDE}
static triangle_calc_t triangle;
(x,y,t,&r,&g,&b)
{
if (numframes==0) {
precalc_tri( triangle, vertices);
}
d0 = d1 = d2 = 0; // Distances of point to lines
vec2 point = {x, y};
side = isPointInsideTriangle(point,triangle,d0,d1,d2);
if (side == TRI_INSIDE) {
if (triangle.winding_dir == -1) {
swap(d1,d2);
swap(d1,d0);
}
r_area = 1.0 / (triangle.winding_dir * triangle.area2);
r = 255 * r_area * d2;
g = 255 * r_area * d0;
b = 255 * r_area * d1; return 1;
}
r=0; g=0; b=0; return 0; // Set color to 0 if outside.
}
 
precalc_tri(triangle_calc_t t, vec2 verts[3]) {
t.area2 = triangleAreaTimes2(verts[0], verts[1], verts[2]);
if (t.area2 == 0) return;
t.winding_dir = sgn(t.area2);
t.origin = verts[0];
vec2 relative_vertices[3];
t.min.x = 1e32;
t.min.y = 1e32;
t.max.x = -1e32;
t.max.y = -1e32;
for(i=0; i<3; i++) {
t.min.x = min(t.min.x, verts[i].x);
t.min.y = min(t.min.y, verts[i].y);
t.max.x = max(t.max.x, verts[i].x);
t.max.y = max(t.max.y, verts[i].y);
relative_vertices[i].x = verts[i].x + t.origin.x;
relative_vertices[i].y = verts[i].y + t.origin.y;
}
makeLine(t.lines[0], relative_vertices[0], relative_vertices[1]);
makeLine(t.lines[1], relative_vertices[1], relative_vertices[2]);
makeLine(t.lines[2], relative_vertices[2], relative_vertices[0]);
}
triangleAreaTimes2(vec2 a, vec2 b, vec2 c) { // Same as the determinant, but dont div by 2
return c.x*(a.y-b.y)+a.x*(b.y-c.y)+b.x*(-a.y+c.y);
}
isPointInsideTriangle( vec2 point, triangle_calc_t t, &d0,&d1,&d2) {
if (t.area2 == 0) return TRI_ZERO;
if (point.x < t.min.x) return TRI_OUT;
if (point.y < t.min.y) return TRI_OUT;
if (point.x > t.max.x) return TRI_OUT;
if (point.y > t.max.y) return TRI_OUT;
vec2 p = {point.x + t.origin.x, point.y + t.origin.y };
d0 = t.winding_dir * lineDist( t.lines[0], p.x, p.y);
if (d0==0) { return TRI_EDGE; }else if ( sgn(d0) < 0 ) return TRI_OUT;
d1 = t.winding_dir * lineDist( t.lines[1], p.x, p.y);
if (d1==0) { return TRI_EDGE; } else if ( sgn(d1) < 0 ) return TRI_OUT;
d2 = t.winding_dir * lineDist( t.lines[2], p.x, p.y);
if (d2==0) { return TRI_EDGE; } else if ( sgn(d2) < 0 ) return TRI_OUT;
return TRI_INSIDE; // on inside
}
 
makeLine(line_t line, vec2 a, vec2 b) { // -dy,dx,axby-aybx
line.a = -(b.y - a.y);
line.b = (b.x - a.x);
line.c = a.x*b.y - a.y*b.x;
}
lineDist(line_t line, x,y) { return x*line.a + y*line.b + line.c; }
swap(&a,&b) {tmp = a; a=b; b=tmp; }</syntaxhighlight>
 
=={{header|Factor}}==
Line 1,342 ⟶ 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,394 ⟶ 1,494:
{{output}}
[[File:FB Find Point in a Triangle.png]]
 
 
 
=={{header|Go}}==
Line 1,803 ⟶ 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,597 ⟶ 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,700 ⟶ 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,807 ⟶ 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/346037...354358"