Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!ucsd!orion.oac.uci.edu!ucivax!ucla-cs!twinsun!rusmin
From: rusmin@twinsun.com (Rusmin Dirgantoro)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon Problem
Message-ID: <1990Aug23.000651.10581@twinsun.com>
Date: 23 Aug 90 00:06:51 GMT
References: <5990@milton.u.washington.edu> <1990Aug22.022743.4139@twinsun.com> <2018@idunno.Princeton.EDU>
Sender: usenet@twinsun.com
Distribution: comp.graphics
Organization: Twin Sun, Inc
Lines: 55

In article <2018@idunno.Princeton.EDU> markv@gauss.Princeton.EDU (Mark VandeWettering) writes:
>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 ] 
>
>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
>...

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.

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?

Consider this polygon...

               +--------------------------------+
               |                                |
               |                                |
               |         D     E     F          |
y=0  - - o - - o----o----o - - o - - o----o-----o - - o - -
         A     B    C    |           |    G     H     I
                         |           |
                         |           |
                         +-----------+

A..I are checkpoints for origin or possible positions
of the point relative to the polygon.
How are we going to do it?

I believe there're solutions for this kind of glitch.
Are they simple, though? Do we really want to do them?

Ciao..


--
Rusmin Dirgantoro                     rusmin@twinsun.com
Twin Sun Inc.                         1(213)640-6885 office
El Segundo, California                1(213)837-3941 home