Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!gatech!hubcap!ncrcae!ncr-sd!hp-sdd!hplabs!hplabsz!dleigh
From: dleigh@hplabsz.HPL.HP.COM (Darren Leigh)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited... A NEW APPROACH
Message-ID: <538@hplabsz.HPL.HP.COM>
Date: Thu, 18-Jun-87 20:28:50 EDT
Article-I.D.: hplabsz.538
Posted: Thu Jun 18 20:28:50 1987
Date-Received: Mon, 22-Jun-87 00:58:09 EDT
References: <948@elrond.CalComp.COM> <790@thumper.UUCP> <284@louie.udel.EDU>
Organization: Hewlett-Packard Laboratories
Lines: 22
Keywords: ray tracing, graphics, polygon intersection
Summary: Very nice, but . . .

In article <284@louie.udel.EDU>, klaiber@udel.EDU (Alexander Klaiber) writes:
> 
> Any other suggestions?  Well, there IS another way, which requires a little
> preprocessing, but otherwise is quite efficient: (concave polygons only)
                                                   ^^^^^^^^^^^^^^^^^^^^^^^

I really like your solution.  It's neat and tidy.  I guess you mean
convex polygons, not concave.  This algorithm won't work for concave
polygons because one part of the polygon might be on one side of a
particular bounding plane while another part would be on the other side.

The other solutions suggested before also work well and efficiently
for convex polygons.  Using the original method of counting the number
of edge intersections between a known inside point and a known outside
point can be simplified, too.  We no longer have to count the number of
intersections:  if there is at least one, then the point is inside 
the polygon.

Darren Leigh
dlleigh@media-lab.mit.edu
or
dleigh@hplabs.hp.com