NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/sci/math/10635

Text File | 1992-08-27 | 2.0 KB | 44 lines

Newsgroups: sci.math
Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!sgiblab!news.cs.indiana.edu!umn.edu!thompson
From: [e-mail] (T. Scott Thompson)
Subject: Re: Polygon point enclosure
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News Administration)
Nntp-Posting-Host: daphne.socsci.umn.edu
Reply-To: [e-mail]
Organization: Economics Department, University of Minnesota
References: <[e-mail]> <[e-mail]>
Date: Thu, 27 Aug 1992 16:48:34 GMT
Lines: 30

[e-mail] (G.J. McCaughan) writes:

>In article <[e-mail]>, [e-mail] (Mark Stockley) writes:

>> I'm looking for a method to determine if a point is enclosed
>> by a polygon. Any help would be greatly appreciated.

>Well, here's one approach. Imagine a ray (=half-line) coming off from the point
>in some direction. Count how many of the sides of the polygon it goes through.
>(If it goes *along* any of those sides you're in trouble and should try another
>direction.) If it's an odd number the point is inside the polygon; if it's an
>even number the point is outside the polygon.

This algorithm is in _Algorithms_ by Robert Sedgewick, Addison-Wesley
(1983), pp 315-318.  (I believe there is a second edition out, but I
don't have it.)  Sedgewick also gives some pseudo-code for the
algorithm that takes into account some other nasty special cases, as
well as the one where the ray includes one of the connecting line
segments.  For example, you must allow for the case where the ray
enters or leaves the polygon at a vertex properly in order for the
method to work.

The strategy of choosing a new direction when the ray goes along a
side is not efficient since there are ways of fixing up the count to
allow for this.  Sedgewick's algorithm provides the details.

--
T. Scott Thompson              email:  [e-mail]
Department of Economics        phone:  [phone]
University of Minnesota        fax:    [phone]