Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!princeton!allegra!ulysses!faline!thumper!sdh
From: sdh@thumper.UUCP
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <790@thumper.UUCP>
Date: Tue, 16-Jun-87 09:44:22 EDT
Article-I.D.: thumper.790
Posted: Tue Jun 16 09:44:22 1987
Date-Received: Thu, 18-Jun-87 04:09:14 EDT
References: <948@elrond.CalComp.COM>
Lines: 26
Keywords: ray tracing, graphics, polygon intersection
Summary: a solution

In article <948@elrond.CalComp.COM>, amamaral@elrond.UUCP 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)?

Here's a way around your problem:
pick a ray that doesn't cause the problem you described.
You said the ray is arbitrary, so use that fact to your advantage.
The most effective way to do this is to make sure that every point on the
polygonis not on the ray.  The problem with this is that you have to check
every point.  Too slow.
A somewhat better (but still fallable) way than arbitrarily picking a ray,
is to use a vector that is defined by the given point and the midpoint
of a particular edge.  The only reasone for this is that it will be fast,
and only less fallable in the sense that you know it will definitely cross
ONE edge without intersecting a point.

Any other suggestions?

Steve Hawley