Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!mit-eddie!genrad!decvax!savax!elrond!amamaral
From: amamaral@elrond.CalComp.COM (Alan Amaral)
Newsgroups: comp.graphics
Subject: Point inside of polygon revisited...
Message-ID: <948@elrond.CalComp.COM>
Date: Mon, 15-Jun-87 13:34:15 EDT
Article-I.D.: elrond.948
Posted: Mon Jun 15 13:34:15 1987
Date-Received: Sun, 21-Jun-87 02:07:33 EDT
Organization: Calcomp, A Lockheed Company, Hudson, NH, USA
Lines: 54
Keywords: ray tracing, graphics, polygon intersection


A while ago someone asked for a method for determining whether or not
a point was inside or outside of a polygon.  I have the replies, and
am in the process of implementing just such a function, but have come
up against what I view as a significant problem.

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)?
Take the two following cases:

                       +
                      /|
                   1 / |
                    /  |
                   /   |
          <-------+--x | 3
                   \   |
                    \  |
                   2 \ |
                      \|
                       +

Intersection point (x) is inside of the bounded area, but there are 2 crossings.
You could count only 1 crossing at a corner (i.e. crossing is only valid if edge
T value is 0 < T <= 1) but that fails in the next case:


            <-----+--------x
                  |\
                  | \
                 1|  \2
                  |   \
                  +----+
                     3

Has anyone solved this particular problem, or do you just ignore it?
I have tried all sorts of schemes to work around this particular problem,
but have always been able to come up with some kind of pathological case
where a concave polygon will fail.

HELP!

-- 
uucp:	 ...decvax!elrond!amamaral		I would rather be a
phone:	 (603) 885-8075				fool than a king...
us mail: Calcomp/Sanders DPD (PTP2-2D01)
	 Hudson NH 	03051-0908