Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!clyde!cbosgd!ucbvax!ucsfcgl!pixar!ph
From: ph@pixar.UUCP (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited... A NEW APPROACH
Message-ID: <859@pixar.UUCP>
Date: Fri, 19-Jun-87 20:20:15 EDT
Article-I.D.: pixar.859
Posted: Fri Jun 19 20:20:15 1987
Date-Received: Mon, 22-Jun-87 06:48:45 EDT
References: <948@elrond.CalComp.COM> <790@thumper.UUCP> <284@louie.udel.EDU>
Organization: Pixar -- Marin County, California
Lines: 48
Keywords: ray tracing, graphics, polygon intersection
Summary: convex is a lot easier than concave

In article <284@louie.udel.EDU>, klaiber@udel.EDU (Alexander Klaiber) writes:
> ... there IS another way, which requires a little preprocessing,
> but otherwise is quite efficient: (concave polygons only) for n edges,
> we need 3*n multiplications and 4*n additions/subtractions/tests ...

Actually the method you describe works for convex polygons only, not concave.

There's a big difference between point-in-polygon testing for convex polyons
and for concave polygons.  It's easy to write robust software for the former
but the latter is often prone to numerical problems and special cases
(hence all the discussion here).

Here's a quick summary of some of the 2-d point-in-polygon methods I know:

POLYGON TYPE	TIME	METHOD

convex		O(n)	dot product with line equation for each edge
			(represent polygon as an intersection of half-planes)

star		O(logn)	binary search on angle from "center" of polygon, test
			inclusion in a single triangle
			(decompose polygon into triangles radiating from center)
			this method requires preprocessing.

concave		O(n)	Jordan Curve Theorem: intersect a ray out of the
			polygon with the edges, count intersections;
			odd means inside, even means outside.

concave		O(n)	winding number method
			Trace a ray out of the polygon and compute the total
			number of intersections which cross the ray going from
			right to left minus the number that cross from left to
			right.  The winding number=0 when outside the polygon.

The two concave methods work for non-simple polygons (polygons which intersect
themselves) too, although they give different results, as described in the
"PostScript Language Referance Manual".  These methods are described more fully
in Preparata & Shamos's book "Computational Geometry".

For 3d point-in-polygon testing it's cheaper to project the point and polygon
to 2d and test inclusion in the projected polygon than to test against planes,
as you did.  Project onto either the x-y, y-z, or z-x plane, use whichever one
has the largest projection.

Paul Heckbert
Pixar				415-499-3600
P.O. Box 13719			UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913		ARPA: ph%pixar.uucp@ucbv Al Al cter unn