Re: Proceeding apace...
- Posted by Matthew Lewis <MatthewL at KAPCOUSA.COM> Mar 23, 2000
- 540 views
> -----Original Message----- > Jeff Zeitlin > What I need now is a way to unambiguously determine a point which > lies within the shape that is being drawn, so that the fill > routine can be used. Every intuitive method I've come up with, > I've been able to draw a figure that breaks the rule. Funny you should ask. I was working on this problem a while ago (had to write something in Visual Basic, tho). I came up with an algorithm that worked (fast enough for what I needed, but doesn't really touch the speed or elegance fo this), but then I found this on the web: <C Code> int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol-1; i < npol; j = i++) { if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) && (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } </C Code> The heuristics of the test are as follows: Draw a ray from the point in some direction. Then count the number of intersections with the polygon. Even means you're outside, odd means you're inside. This one works for all sorts of polygons. The web reference has some more detail on the mathematics. There are other references out on the web for more well behaved polygons (regular, convex, etc), but this routine will work with arbitrary shapes. So in Euphoria: -- Untested code. Watch for typos!! -- poly = { {x1,y1}, {x2,y2},...,{xn,yn},{x1,y1} } -- point = {x_point, y_point} funciton pnpoly( sequence poly, sequence point ) atom x, y, c c = 0 x = point[1] y = point[2] for i = 1 to length(poly)-1 do if ((poly[i][2] <= y and poly[i+1][2] < y) or (poly[i][2] <= y and poly[i+1][2] < y)) and ( x < (poly[i+1][1] - poly[i][1]) * (y - poly[i][2]) ; ( poly[i+1][2] - poly[i][2] ) + poly[i][1])) then c = (c=0) end if end for return c end function It might be possible to optimize within the if statement, but this should do the trick. Matthew W Lewis