🚀 go-pugleaf

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?

This is a Computational Geometry question. I could direct you to the
book of Preparata and Shamos, which IMHO is not so much worth reading
after all (with exeption of the Voronoi stuff, but the latter already
belongs to classical mathematics).

What do you want? In-out algorithms are _either_ fast XOR reliable!

In article <134504@lll-winken.LLNL.GOV> Patrick Tibbits:
> Define vector ai from vertex i to the point p under consideration.
> Define vector bi from vertex i to vertex i+1.
> Then ai cross bi must be postitive for all i for p to lie within the
> polygon.

Obviously wrong in the case of non-convex polygons. Look at:
		 _______
		|	|
	IN	|	o i+1    IN
		|	|
	p o ----|-------o i    : negative, huh?
	________|  OUT	|_________

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.
-- 
* Han de Bruijn; Applications&Graphics | "A little bit of Physics * No
* TUD Computing Centre; P.O. Box 354   | would be NO idleness in  * Oil
* 2600 AJ  Delft; The Netherlands.     | Mathematics" (HdB).      * for
* E-mail: Han.deBruijn@RC.TUDelft.NL --| Fax: +31 15 78 37 87 ----* Blood