Path: utzoo!mnetor!uunet!husc6!uwvax!dogie!uwmcsd1!ig!jade!ucbvax!lands.ced.berkeley.edu!bsmith
From: bsmith@lands.ced.berkeley.edu (Brian Smith)
Newsgroups: comp.graphics
Subject: Re: polygons and points
Message-ID: <22564@ucbvax.BERKELEY.EDU>
Date: 13 Jan 88 04:49:09 GMT
References: <506UD138985@NDSUVM1>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: bsmith@postgres.berkeley.edu (Brian Smith)
Organization: UC Berkeley
Lines: 13
Keywords: computer graphics, polygons and points

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