Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!ut-sally!utah-cs!shebs
From: shebs@utah-cs.UUCP (Stanley Shebs)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <4644@utah-cs.UUCP>
Date: Tue, 16-Jun-87 11:38:44 EDT
Article-I.D.: utah-cs.4644
Posted: Tue Jun 16 11:38:44 1987
Date-Received: Sun, 21-Jun-87 06:24:43 EDT
References: <948@elrond.CalComp.COM>
Reply-To: shebs@utah-cs.UUCP (Stanley Shebs)
Organization: PASS Research Group
Lines: 36
Keywords: ray tracing, graphics, polygon intersection

In article <948@elrond.CalComp.COM> amamaral@elrond.CalComp.COM (Alan Amaral) writes:

>To recap, the theorum put forth was that given a bounded area on a plane
>and a point on the plane, one could determine whether the point was inside
>the area, or outside the area by determining how many edges an arbitrary
>ray starting at the given point crossed. (and a partridge in a pear tree...)
>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.
>
>This all works well and good, EXCEPT for one particular case. What if the
>ray happens to cross 2 edges at exactly the same point (i.e. at a corner)?

I ran into this problem a few years ago while working at Boeing.  It's not
particularly important which ray you pick, so if the line did hit right
on an endpoint, I just perturbed the ray a little bit and tried again.
This takes care of every possible crossing through a vertex - no special
cases. Termination can be guaranteed by making the perturbations sufficiently
small that it would take more of them than there are vertices in the polygon
to march all the way around the point.  An easy way to do this is just to
increment the y component of the end of the ray while leaving x fixed - the
rays get more and more vertical, but each will be different...

Performance is not bad, because with floating point computation, the chances
of having to do a perturbation are 1/bits-in-a-float or thereabouts.  Also
works in 3D, assuming perturbation lies in the plane of the polygon, and
could be extended to polyhedra.  Not really workable with integer computation
though.

Alas, after I had put the algorithm together (was actually for computing
intersections of squares with polygons), proved correctness, and demonstrated
an implementation, it was discarded because it was "too general" (the polygons
supposedly had only vertical and horizontal edges).  Now you know why
I have a low opinion of military contractors and the DoD...

							stan shebs
							shebs@cs.utah.edu