🚀 go-pugleaf

In article <1992Sep9.141511.23893@dutrun2.tudelft.nl> rcpshdb@dutrun2.tudelft.nl (Han de Bruijn) writes:
> In article <1992Aug25.195204.28914@eng.ufl.edu> Ed Deeters:
>> Hi, does anyone know a fast way to determine if a point(x,y) is inside
>> or outside of a polygon when the polygon is defined by n points(x,y) 
>> given in a clockwise manner?

> [...] determine the _angle_ between ai and bi (: quite expensive!).
> The sum of all these angles (FOR i=1 to N-1) divided by  2.pi  equals
> the so called "winding number" for  p . If the winding number is < 0.5
> then  p  is outside the polygon. The higher the point's winding number,
> the more it is enclosed by the polygon.

The simplest algorithm (and easiest to believe in, at least for me)
is to shoot a ray in an arbitrary direction from your point and
count the number of polygon edges you cross.

Exactly what you do with your count depends on how you want to treat
self-intersecting polygons.  If you use the even/odd rule (the polygon
cancels out XOR-fashion when it intersects itself) then you're inside
the polygon if and only if you cross an odd number of edges.  If you
use the winding-number rule (inside a self-intersecting part still
counts as inside), then count +1 for every edge that crosses going
to the right (as viewed by the ray) and -1 for every edge that crosses
going to the left; you're inside if the final count is nonzero.  It
doesn't matter which way you go around the polygon, since if you get
left and right backwards the final nonzero-ness test comes out the
same.

If you don't expect to have self-intersections, then the even/odd test
will do the job and is probably simpler.

Since this works for rays in any direction, you can choose one
of the four directions that parallel the x or y axes.  For these
directions, the math for the intersection test becomes extremely
simple and fast.

The only tricky part is, what happens if your ray goes exactly
*through* one of the points in the polygon?  There are two answers:
Either refine your test to take care of all the various tricky cases
that can arise here, or, more simply, choose another ray and hope
for better luck.  After all, if you have a finite number of points
in your polygon, there must be *some* direction you can go and not
intersect any point.

It might be easiest to try, say, east- and north-going rays in turn;
if both run into trouble, use the much slower angle-oriented test
that Han de Bruijn describes.  All these tests are quite simple to
code, and Han's computation-intensive test will only rarely need to
be used.  In C, the "atan2" library function does most of the work
of Han's test.

If for some reason Han's test is not practical, then I'd suggest
trying rays in easy directions, then in random hard directions
until you find a case where you don't run into any vertices.  The
intersection test is trickier for arbitrary rays, though, and
roundoff issues make the question of when you've hit a vertex
somewhat less clear-cut.  Another problem with trying random
directions is that there is no guaranteed upper bound on the
amount of time the algorithm takes.

								-- Dave
--
Dave Gillespie
  daveg@synaptics.com, uunet!synaptx!daveg
  or: daveg@csvax.cs.caltech.edu