Path: utzoo!attcan!uunet!snorkelwacker!usc!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.graphics
Subject: Re: Algorithm needed to determine if a point is inside a polygon
Keywords: polygon
Message-ID: <6974@helios.TAMU.EDU>
Date: 30 Jul 90 17:22:53 GMT
References: <46093@brunix.UUCP> <6951@helios.TAMU.EDU> <6952@helios.TAMU.EDU>
Sender: usenet@helios.TAMU.EDU
Distribution: na
Organization: Computer Science Department, Texas A&M University
Lines: 60

Subject: Re:: Algorithm needed to determine if a point is inside a polygon

>> I forgot to mention...
>> works only for convex polygons.

>You also forgot to mention the name of the algorithm and where to obtain
>information on it.  I, for one, would be interested in finding this out.

>Thanks,
>Lem Davis
>lem@nosc.mil

Oh, dear; me and my big mouth. To begin with, turn to "Computational
Geometry" by Preparata & Shamos, Section 2.2.1. Theorem 2.2 shows how
to do it in O(logN) time using O(N) preprocessing time. The idea in
this proof is to divide the polygon into wedges and do a circular
binary search on the wedges. The division into wedges takes O(N) time,
but it is a one-time piece of work. The actual binary search, which
can be expected to be repeated many times, takes O(logN) time.

My variation on this scheme works on arrays. We assume that the 
coordinates are in arrays X[1..N], Y[1..N], with the vertices of the
polygon in circular order (clockwise or anticlockwise).

Preprocessing step: find index of vertex with maximal Y, and index 
of vertex with minimal Y.  This can be easily done in O(N) time, 
and this is probably good enough for most applications. However, 
it can also be done in O(logN) time.

Query step: Given a point (a,b), is it in the polygon? Geometrically,
this is done by the parity method: consider the horizontal line y=b.
If the line is above the maximal Y or below the minimal Y, the answer
is no. Otherwise, find the edges of the polygon which the line
intersects. Count the no. of intersections to the left of (a,b) - if
it is one, then the point is inside; otherwise (0 or 2), it is outside.

The logarithmic time is obtained by finding the edges intersecting y=b
by doing a circular binary on the array Y. Assume for simplicity that
the minimum Y is at Y[1] and the maximum is Y[m], where 1<m<=N. One
intersection is found by doing a binary search of b among Y[1..m],
and the other by doing a binary search on Y[m],Y[m+1],...,Y[N],Y[1].

                               Y[m]
                                *
                               / \
                              /   \
                             *     *
                             |      \
                --------------------------*-----------
                y=b          |        \  (a,b)
                             |         \
                         Y[2]*          *Y[N]
                              \        /
                               \      /
                                \    /
                                 \  /
                                  \*
                                  Y[1]

I hope this helps.