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 22:59, 29 August 2023

15 bytes added ,  9 months ago
→‎{{header|Evaldraw}}: fix bug where point in tri wouldnt work if point in negative quadrant
(add RPL)
(→‎{{header|Evaldraw}}: fix bug where point in tri wouldnt work if point in negative quadrant)
Line 1,171:
<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 vertices[3];
enum{WIND_ANTI_CLOCKWISE=-1, WIND_CLOCKWISE=1}
double area2;
static winding_dir = -1; // +1 if clockwise (positive angle) -1 if negative.
static line_t line0, line1, line2;
};▼
static area2; // 2x tri area
//static vec2 dat[3] = {0,-2, -2,2, 4,0};▼
static vec2 dat[3] = {-3,7, -6,-5, 2,2};
static triangle_calc_t tri;
enum{TRI_OUT=0, TRI_EDGE=1, TRI_INSIDE=2}
(x,y,t,&r,&g,&b)
{
if (numframes==0) {
{▼
// Three line equations of the form a+b+c=0
precalc_tri( tri, dat);
// 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);▼
}
 
▲
vec2 screenPoint = {x,y};
d0 = d1 = d2 = 0;
ifside (= isPointInsideisPointInsideTriangle( screenPointx, line0y, line1tri, line2, d0, d1, d2) ) {;
if (winding_dirside == -1TRI_EDGE) {
r=255; g=255; b=0;
return 1;
▲ }
else if (side == TRI_INSIDE) {
if (tri.winding_dir == -1) {
swap(d0,d1);
}
factor = 255;
r = 255*( d1 / area2); // RGB only within 0-255 range if tri verts in positive cartesian quadrant
gdiv = 255tri.winding_dir *( d2 / tri.area2);
br = 255factor*( d0d1 / area2div);
g = factor*( d2 / div);
b = factor*( d0 / div);
return 1;
}
Line 1,211 ⟶ 1,209:
}
 
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.origin = verts[0];
d0 = lineDist( line0, p.x, p.y);▼
▲ for(i=0; i<3; i++) {
▲ if ( winding_dir*sgn(d0) <= 0 ) return 0;
▲ t.vertices[i].x = datverts[i].x + 2t.origin.x;
▲ t.vertices[i].y = datverts[i].y + 2t.origin.y;
}
▲ makeLine(line0t.lines[0], t.vertices[0], t.vertices[1]);
▲ makeLine(line1t.lines[1], t.vertices[1], t.vertices[2]);
▲ makeLine(line2t.lines[2], t.vertices[2], t.vertices[0]);
▲ t.area2 = areaTriangleX2(t.vertices[0], t.vertices[1], t.vertices[2]);
▲ t.winding_dir = sgn(tri.area2);
}
areaTriangleX2(vec2 a, vec2 b, vec2 c) { // Same as the determinant, but dont div by 2▼
(s a= c.x*(ba.y - cb.y) + ba.x*(cb.y - bc.y) + cb.x*(-a.y - b+c.y) );▼
}
isPointInsideTriangle(x,y, triangle_calc_t t, &d0,&d1,&d2) {
vec2 p = {x + t.origin.x, y + t.origin.y };
▲ d0 = t.winding_dir * lineDist( line0t.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,233 ⟶ 1,245:
lineDist(line_t line, x,y) {
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>
Torbjoern
63

edits

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