Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!mit-eddie!uw-beaver!tektronix!teklds!zeus!bobr
From: bobr@zeus.UUCP
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <1868@zeus.TEK.COM>
Date: Tue, 16-Jun-87 16:37:53 EDT
Article-I.D.: zeus.1868
Posted: Tue Jun 16 16:37:53 1987
Date-Received: Thu, 18-Jun-87 04:45:53 EDT
References: <948@elrond.CalComp.COM>
Reply-To: bobr@zeus.UUCP (Robert Reed)
Organization: CAE Systems Division, Tektronix Inc., Beaverton OR
Lines: 35

In 2-space, the problem is still trivial.  Given an interior point, the
infinite ray from this interior point over which crossings are counted, and
a starting vertex on the polygon, do the following:

Create a state variable which indicates whether the last non-collinear
vertex was above or below the line containing the ray.  Initialize this with
a value appropriate for the initial polygonal point.  Walk the polygon,
examining each vertex in sequence.  If the vertex lies on the "other" side
of the line, update the state variable and determine the crossing point.  If
it lies on the ray, increment the crossing count.  If a vertex lies on the
line, no crossing has occurred.  If the next vertex is on the same side, no
crossing has occurred.  If one or more vertices lie on the line, no crossing
calculations are performed.

In your examples, case 1 counts as a single crossing.  Beginning at the
upper vertex of edge 1, the state variable ABOVE is set TRUE.  The next
vertex lies on the line, so move onto the next.  The next vertex is below
the line, so compute the intersection of edge 2, which lies on the ray.
Bump the crossing count.  ABOVE is now FALSE.  The next vertex (which
completes the loop of the polygon) is once again above the line.  Update
ABOVE and compute the intersection.  The intersection is NOT on the ray, so
at the conclusion of the algorithm, the crossing count is 1, indicating the
point is inside the polygon.

Consider case 2.  This is a little tricky because the upper vertex of edge 1
lies on the line.  The simplest solution is to therefore reject it as the
intial vertex for the test and move on to the lower vertex of edge 1.
Starting here ABOVE is FALSE.  Going to the next vertex (right end of edge
3), this is also below, so no crossing test is done.  Moving on to the next,
it lies on the line, so no crossing test is done.  Moving on to the next,
which is the final vertex, it also lies below, so no crossing test is done.
At the conclusion of the algorithm, the crossing count is 0, which is even,
indicating that the point lies in the exterior of the polygon.
-- 
Robert Reed, Tektronix CAE Systems Division, bobr@zeus.TEK