Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!uupsi!njin!princeton!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <2034@idunno.Princeton.EDU>
Date: 23 Aug 90 01:54:19 GMT
References: <5990@milton.u.washington.edu> <1990Aug22.022743.4139@twinsun.com> <2018@idunno.Princeton.EDU> <1990Aug23.000651.10581@twinsun.com>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU (Mark VandeWettering)
Distribution: comp.graphics
Organization: Princeton University
Lines: 54

>Mark came up with a smart solution for the "ambiguous ray-edge intersection"
>(AREI) problem (anyone agrees with this name?). I like his article.
>But his solution has a little glitch.

Hardly my own idea.  It was shown to me by Eric Haines originally, but I 
don't think he claims credit for it either.  Any takers?  Is it patented 
by Unisys as well :-)?

But, it is stump the computer jock time, he gave a nice tough diagram, 
and its time to show that this really will work.

>Consider this case..
>
>       origin              ^              ^
>                           |              |
>         o                 o--->  or  <---o  or  o--->  or  <---o
>                                                 |              |
>                                                 v              v
>                            (1)        (2)         (3)       (4)
>
>Are we going to count (1), (2), (3), or (4) as one or zero?

Apply the rule I gave you blindly, lets assume we break ties by assuming 
they are in above the point in question.  Therfore 1 & 2 count as zero 
intersections, and 3 & 4 count as 1 intersection.  Now, on to the case
you gave:

>Consider this polygon...
>
>               +--------------------------------+
>               |                                |
>               |                                |
>               |         D     E     F          |
>y=0  - - o - - o----o----o - - o - - o----o-----o - - o - -
>         A     B    C    |           |    G     H     I
>                         |           |
>                         |           |
>                         +-----------+
>

	A, B, C, E, G, H, are all counted as zero.

	D & F are counted as one.  Therefore the total is two, and the point
	is outside.

	If we broke ties the other way, then B and H count one, and we get
	the same answer.

	Pretty damned amazing, isn't it?  

	I really do thank Eric for showing me this.  Its one of my favorite
	little snippets of code.

Mark