Xref: utzoo comp.graphics:1845 comp.sys.ibm.pc:12606
Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!mordor!sri-spam!ames!ll-xn!mit-eddie!bbn!rochester!cornell!batcomputer!saponara
From: saponara@batcomputer.tn.cornell.edu (John Saponara)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <3895@batcomputer.tn.cornell.edu>
Date: 29 Feb 88 21:10:46 GMT
References: <971@ut-emx.UUCP> <867@bingvaxu.cc.binghamton.edu>
Reply-To: saponara@tcgould.tn.cornell.edu (Eric Haines)
Organization: Cornell Theory Center, Cornell University, Ithaca NY
Lines: 41
Keywords: READ THIS ONLY IF YOUR IQ != YOUR SHOE SIZE ;^)

In article <867@bingvaxu.cc.binghamton.edu> sullivan@marge.math.binghamton.edu.cc.binghamton.edu (fred sullivan) writes:
>In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes:
>>Have a boundary defined on the screen. Boundary is composed of points
>>joined by lines... Now some random points are generated and I want to check
>>if a given point is within or outside the existing boundary. Any algorithm for
>
>See "Algorithms" by Robert Sedgewick, pp. 315-317.

This is an excellent place to go for good start on the problem.  Go read it.


Now that you've read it, forget it.  The problem with Sedgewick is that, to
quote Sedgewick, "The program assumes that p[1] [the second point in the
polygon] is the point with the smallest x coordinate among all the points with
the smallest y coordinate, so that if p[1] is on the test line, then p[0]
cannot be."  This is a pretty hefty assumption under some circumstances,
and it puts the burden of finding p[1] on the programmer.  Sedgewick's point
here is that he wants to avoid having p[0] and p[1] both start on the
horizontal ray which he shoots off from the test point.  Something unstated by
Sedgewick is that he assumes that the points are in a counter-clockwise
order (if they were clockwise, p[1] and p[0] could lie on a horizontal line
even with these funky conditions on p[1] - I leave this as an exercise for
the dedicated knurds (like me) ;^) ).

You can do away with Sedgewick's p[1] assumption and start with any vertex
you want by making one simplification: make the horizontal ray emanating from
the test point not a set of points but rather a simple dividing line, which
divides vertices into two sets: those above the horizontal X line (i.e.
those with Y >= 0) and those below (Y < 0).  You've just defined the special
case of points on the test line away: there are now NO points on the ray, as
we've defined it.  This turns out to get rid of all those nasty special
cases.  For a full explanation, see my course notes for the SIGGRAPH '87
"Introduction to Ray Tracing" tutorial (they'll be in this year's tutorial
notes, too, whatever good that'll do you right now).

A problem with both of these methods, by the way, is that points exactly on
the edge of the polygon will sometimes be considered inside, sometimes outside
the polygon.  This can be easily solved in theory (with precision error
creeping in and messing things up), and for applications like ray-tracing it's
almost always irrelevant.
 
Eric Haines (not John Saponara)