🚀 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?
|> 
|> [.....]
|> 
|> What do you want? In-out algorithms are _either_ fast XOR reliable!
|> 
|> [.....]
|> 
|> Reliable algorithm (NOT cheap):
|> ------------------
|> Instead, 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.

According to conventional wisdom the ray crossing method (see Preparata
and Shamos for the general idea) is faster (I've never checked this myself)
and is also reliable. The details of the special cases can be a little messy
but there is a trick, which I don't remember right now, which makes for clean,
fast, reliable code (if you are desperate, e-mail me and I'll take a look at
the code to refresh my memory). This should be in the FAQ(s) since this is
asked every month or two.

Larry Edwards
edwards@sunrise.stanford.edu