Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!clyde!cbosgd!ihnp4!inuxc!iuvax!pur-ee!beatyr
From: beatyr@pur-ee.UUCP (Robert Beaty)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <6375@pur-ee.UUCP>
Date: Wed, 17-Jun-87 10:21:43 EDT
Article-I.D.: pur-ee.6375
Posted: Wed Jun 17 10:21:43 1987
Date-Received: Sun, 21-Jun-87 11:42:01 EDT
References: <948@elrond.CalComp.COM>
Reply-To: beatyr@pur-ee.UUCP (Robert Beaty)
Organization: Purdue University Engineering Computer Network
Lines: 35
Keywords: ray tracing, graphics, polygon intersection

In article <948@elrond.CalComp.COM> amamaral@elrond.CalComp.COM (Alan Amaral) writes:
>
>A while ago someone asked for a method for determining whether or not
>a point was inside or outside of a polygon. 
>
>To recap, ...
>      ...determining how many edges an arbitrary
>ray starting at the given point crossed.
>If the ray crossed an even number of edges, then the point is outside of the
>area, and it's inside if the number of crossings is odd.
>
  Boy I hope this isn't too silly, but why not do the obvious? Look in
all four (or six in 3 space) unit vectors, and their negatives. i.e.:

                    ^
                    |
                <-- x -->
                    |
                    v

Then do something simple like taking the minima, or the greatest frequency,
either odd or even. If it should work for any single ray then it should
work for any conbination of rays. If you still can't get a 3/4 ths majority
then rotate the four rays (or six rays) some angle theta ( or (theta,phi) )
and try again.
  Seems to me this should get you a simple result for all but the most
odd-ball cases. (in those cases rotate by another theta and try again)
  Oh well.. this seemed so obvious to me it might be wrong.

				Bob
----------
   ... ihnp4!pur-ee!beatyr      <- usenet
  ... beatyr@ed.ecn.purdue.edu  <- arpa-net
   ... beatyr@pur-ee.UUCP       <- UUCP
----------