Find if a point is within a triangle: Difference between revisions
Find if a point is within a triangle (view source)
Revision as of 21:44, 22 August 2023
, 9 months ago→{{header|Evaldraw}}: add solution for point in tri
m (→{{header|ATS}}) |
(→{{header|Evaldraw}}: add solution for point in tri) |
||
Line 1,162:
print('');
}</syntaxhighlight>
=={{header|Evaldraw}}==
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.
<syntaxhighlight lang="c">struct vec2{x,y;};
struct line_t{a,b,c;};
// Our triangle defined by 3 points in the cartesian 2D plane.
static vec2 vertices[3] = {0,-2, -2,2, 4,0};
//static vec2 vertices[3] = {0,-2, 4,0, -2,2};
enum{WIND_ANTI_CLOCKWISE=-1, WIND_CLOCKWISE=1}
static winding_dir = -1; // +1 if clockwise (positive angle) -1 if negative.
static line_t line0, line1, line2;
static areaSq;
(x,y,t,&r,&g,&b)
{
if (numframes==0) {
// 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.
makeLine(line0, vertices[0], vertices[1]);
makeLine(line1, vertices[1], vertices[2]);
makeLine(line2, vertices[2], vertices[0]);
areaSq = areaTriangleSquare(vertices[0], vertices[1], vertices[2]);
winding_dir = sgn(areaSq);
}
vec2 screenPoint = {x,y};
d0 = d1 = d2 = 0;
if ( isPointInside( screenPoint, line0, line1, line2, d0, d1, d2) ) {
if (winding_dir == -1) {
swap(d0,d2);
}
r = 255*( d1 / areaSq);
g = 255*( d2 / areaSq);
b = 255*( d0 / areaSq);
if (d0==0) {r=255; g=0; }
if (d1==0) {r=255; g=0; }
if (d2==0) {r=255; g=0; }
return 1;
}
r=0; g=0; b=0; return 0; // Set color to 0 if outside.
}
isPointInside(vec2 p, line_t line0, line_t line1, line_t line2, &d0,&d1,&d2) {
d0 = lineDist( line0, p.x, p.y);
if ( winding_dir*sgn(d0) <= 0 ) return 0;
d1 = lineDist( line1, p.x, p.y);
if ( winding_dir*sgn(d1) <= 0 ) return 0;
d2 = lineDist( line2, p.x, p.y);
if ( winding_dir*sgn(d2) <= 0 ) return;
return 1; // We are on the right side.
// If we wanted to find the exact distance the point is
// to any line we could the min of d0,d1,d2.
}
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) {
x*line.a + y*line.b + line.c;
}
areaTriangleSquare(vec2 a, vec2 b, vec2 c) { // Same as the determinant
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>
=={{header|Factor}}==
| |||