Find if a point is within a triangle: Difference between revisions
Content added Content deleted
(add RPL) |
(→{{header|Evaldraw}}: fix bug where point in tri wouldnt work if point in negative quadrant) |
||
Line 1,171: | Line 1,171: | ||
<syntaxhighlight lang="c">struct vec2{x,y;}; |
<syntaxhighlight lang="c">struct vec2{x,y;}; |
||
struct line_t{a,b,c;}; |
struct line_t{a,b,c;}; |
||
struct triangle_calc_t{ |
|||
vec2 origin; |
|||
// Our triangle defined by 3 points in the cartesian 2D plane. |
|||
line_t lines[3]; |
|||
vec2 vertices[3]; |
|||
enum{WIND_ANTI_CLOCKWISE=-1, WIND_CLOCKWISE=1} |
|||
double area2; |
|||
winding_dir; // +1 if clockwise (positive angle) -1 if negative. |
|||
static line_t line0, line1, line2; |
|||
⚫ | |||
static area2; // 2x tri area |
|||
⚫ | |||
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) |
(x,y,t,&r,&g,&b) |
||
{ |
{ |
||
if (numframes==0) |
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 screenPoint = {x,y}; |
|||
d0 = d1 = d2 = 0; |
d0 = d1 = d2 = 0; |
||
side = isPointInsideTriangle(x,y,tri,d0,d1,d2); |
|||
if (side == TRI_EDGE) { |
|||
r=255; g=255; b=0; |
|||
return 1; |
|||
⚫ | |||
else if (side == TRI_INSIDE) { |
|||
if (tri.winding_dir == -1) { |
|||
swap(d0,d1); |
swap(d0,d1); |
||
} |
} |
||
factor = 255; |
|||
r = 255*( d1 / area2); // RGB only within 0-255 range if tri verts in positive cartesian quadrant |
|||
div = tri.winding_dir * tri.area2; |
|||
r = factor*( d1 / div); |
|||
g = factor*( d2 / div); |
|||
b = factor*( d0 / div); |
|||
return 1; |
return 1; |
||
} |
} |
||
Line 1,211: | Line 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]; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
⚫ | |||
⚫ | |||
} |
|||
isPointInsideTriangle(x,y, triangle_calc_t t, &d0,&d1,&d2) { |
|||
vec2 p = {x + t.origin.x, y + t.origin.y }; |
|||
⚫ | |||
if (d0==0) { return TRI_EDGE; }else if ( sgn(d0) < 0 ) return TRI_OUT; |
|||
d1 = lineDist( |
d1 = t.winding_dir * lineDist( t.lines[1], p.x, p.y); |
||
if ( |
if (d1==0) { return TRI_EDGE; } else if ( sgn(d1) < 0 ) return TRI_OUT; |
||
d2 = lineDist( |
d2 = t.winding_dir * lineDist( t.lines[2], p.x, p.y); |
||
if ( |
if (d2==0) { return TRI_EDGE; } else if ( sgn(d2) < 0 ) return TRI_OUT; |
||
return |
return TRI_INSIDE; // on 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: | Line 1,245: | ||
lineDist(line_t line, x,y) { |
lineDist(line_t line, x,y) { |
||
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> |
swap(&a,&b) {tmp = a; a=b; b=tmp; }</syntaxhighlight> |