Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!vax5!cnsy
From: cnsy@vax5.CIT.CORNELL.EDU
Newsgroups: comp.graphics
Subject: Re: Computational geometry
Summary: One more time
Message-ID: <18516@vax5.CIT.CORNELL.EDU>
Date: 1 May 89 16:01:57 GMT
References: <2053@incas.UUCP>
Sender: news@vax5.CIT.CORNELL.EDU
Reply-To: cnsy@vax5.cit.cornell.edu (Eric Haines, actually)
Organization: 3D/Eye Inc
Lines: 37

In article <2053@incas.UUCP> mdoerr@incas.UUCP (Michael Doerr) writes:

[ ...much about the summation of angles test for calculating the winding
      number deleted...]

>	3. If questions 1 can be answered with YES:
>		How could the algorithm be improved, so that less
>		expensive operations are required?

Michael,

	Simply use the most popular inside outside test: move your test point
to the origin (along with the polygon, of course), shoot a ray along the
+X axis, and count the intersections of this ray with the polygon's line
segments.  One important case is to consider all vertices with a Y component
of zero (after the transform to the origin) to be ABOVE the +X axis: this
gets rid of all the special cases where the vertices are on the axis, and
still gives the right answer.  Comparing line segments is much faster than
doing angle summations (are both of the y components of the line segment the
same sign? If so, then we know that it won't cross the +X axis.  Then, are
both of the x components negative?  If so, again it won't cross.  If both
these quick tests fail, then you have to do a little work to get the
intersection).

	Now, about extending this to get the winding number.  Marching along
the vertex list we look at the sign of the Y component whenever we find that
a segment crosses +X.  Add this sign to a running total.  At the end, if the
sum is even, the test point is outside the polygon, else inside.  However,
the sum is also the winding number, and the sign tells the direction!  For
example, if you use the usually +X is pointing right, +Y pointing up, then
a winding number of +3 would mean three winds in a clockwise direction.

	For a complete description, see my section in the "Introduction to
Ray Tracing" course notes, SIGGRAPH '88, or wait until August for the book
by Academic Press.

Eric Haines