OpenEuphoria

Re: Proceeding apace...

• Posted by Matthew Lewis <MatthewL at KAPCOUSA.COM> Mar 23, 2000
• 720 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