Path: utzoo!utgpu!water!watmath!clyde!rutgers!rochester!cornell!batcomputer!saponara
From: saponara@batcomputer.tn.cornell.edu (John Saponara)
Newsgroups: comp.graphics
Subject: Re: polygons and points
Summary: A quick summary of yesterday's posting, for those in the know
Keywords: computer graphics, polygons and points
Message-ID: <3365@batcomputer.tn.cornell.edu>
Date: 13 Jan 88 14:19:53 GMT
References: <506UD138985@NDSUVM1> <22564@ucbvax.BERKELEY.EDU>
Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines)
Organization: 3D/Eye Inc, Ithaca, NY
Lines: 41

In article <22564@ucbvax.BERKELEY.EDU> bsmith@postgres.berkeley.edu (Brian Smith) writes:
>I had a hell-of-a-time finding it, but the algorithm for testing 
>if a point is in a polygon can be found in
>
>Robert Sedgewick, "Algorithms", Addison-Wesley, 1984, pp 315-317.
>
>The basic idea is to draw a line from the point to infinity and
>count how many intersections it makes with the polygon. If it 
>crosses an odd number of times, then it's inside, otherwise it's
>outside. Usually a horizontal line is chosen for efficiency, and
>intersections of the line with vertices have to be handled
>specially.
>
>	Brian Smith

	Thanks, I've been wanting a source to cite for this procedure.  Since
people already in the know may not have plowed through my longwinded
explanation of basically the same algorithm, which I posted yesterday, I
thought I'd point out the nice addition to Sedgewick's explanation which makes
all the "vertex on the testing ray" special cases go away.  We used the basic
algorithm outlined by Sedgewick for years at Cornell and then at 3D/Eye.  About
two years ago I found yet another bug in this darn routine, one of those "if
the first vertex starts on the ray and a second vertex touches the ray when..."
type obscure cases that come up once in a million polygons.  (Berlin talks
about similar problems in "Efficiency Considerations in Image Synthesis"
SIGGRAPH Course Notes, Vol. 11, 1985.  By the way, this article gives three
methods for doing point/polygon comparisons.  Avoid his method, though - it is
slower.  Sedgewick with the modification outlined below is the way to go).
After some frustration with getting rid of all those special cases, I happened
upon a simplification which is very useful. 

	Anyway, the modification is that the ray traced along the horizontal
axis should not be considered a set of points at all, but rather is simply a
dividing line between zero and the negative numbers along the Y axis.  This
change leads to a wonderful simplification:  there are now no vertices which
are intersected by the ray, i.e. no special cases!  Now all polygon vertices
are either above or below this new sort of ray (which is really just a boundary
instead of a true ray).  This change made for faster, simpler, and correct
code.  Try it - it works!

Eric Haines, 3D/Eye Inc (borrowing John Saponara's account)