Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!haven!udel!princeton!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <2018@idunno.Princeton.EDU>
Date: 22 Aug 90 16:31:19 GMT
References: <5990@milton.u.washington.edu> <1990Aug22.022743.4139@twinsun.com>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU (Mark VandeWettering)
Distribution: comp.graphics
Organization: Princeton University
Lines: 38

In article <1990Aug22.022743.4139@twinsun.com> rusmin@twinsun.com (Rusmin Dirgantoro) writes:
>In article <5990@milton.u.washington.edu> benson@blake.acs.washington.edu (Dan Benson) writes:
>> [ ask for points in polygon algorithms ]
> [ responds with an "almost right" algorithm ] 

The solution proposed by rusmin@twinsun.com was based upon the Jordan Curve
theorem: any ray from inside a polygon crosses an odd number of edges on its
way to infinity.  He chose a random ray that began at the point in question,
and counted the number of intersections.  Problem: if you intersected a vertex
you were kind of clueless.  Solution, fire another ray.

You solve these problems by simplifying everything.  The ray you shoot should
go to the positive X axis.  Assume without loss of generality that your 
point is the origin.  Now: if you are going to intersect a vertex, its because
the y component of an edge endpoint is == 0.  Well, decide whether you want
to count this as positive or negative.  Assume positive (I always do).  It 
turns out you get the right answer anyway.  For example

      origin         ^
		     | 
	o            o			counts as one intersection
		     | 
		     v

      origin         ^ ^
		     |/
	o            o			counts as zero or two intersections

      origin   
		     
	o            o			counts as zero or two intersections
		     |\
		     v v
	

Voila!  C'est explique!

mark