\input TR8TwoColFormat.tex \input GeoMacros \input KineMacros

\begfile{SimPolIncl.tex of December 6, 1983 3:14 am --- Stolfi}

% Point inclusion in a simple polygon using Kinetic Framework (FOCS '83)
%  Renamed and slightly edited from [maxc]<Guibas>ConvExtra.tex

\pagetitlestuff{

\title{An Efficient Test for\cp
  Point Inclusion in a Simple Polygon}

\author{Leo Guibas and Jorge Stolfi}

}

\columntitlestuff{

\abstract{We present a simple and efficient test for deciding in $O(n)$ time whether a point of the plane is inside a given simple 
polygon. The test is based on a new theorem relating the {it sweep number}, as defined in the Kinetic Framework, to the classical 
winding number.}

}

% ADDITIONAL MACROS

% Reference tags

\def\Kin{GRS} % Guibas, Ramshaw, Stolfi (FOCS 83) 

\section{1. Point inclusion in a simple polygon}

% Begin

\note{This is a slightly edited copy of [maxc]<Guibas>ConvExtra.tex, and elaborates slightly on an item of the Kinetic Framework 
paper presented at FOCS '83 [\Kin].}

Let $P$ denote a simple polygon in the plane, no two of whose successive sides are collinear. Then $P$ can be viewed as a tracing 
under the convention that it is traversed by a car in the counterclockwise direction, and that the car at each vertex makes a turn 
that is less than $\pi$. We will call such a tracing a {\it simple polygonal tracing}.

\lemma{\Th1}{If $P$ is a simple polygonal tracing, then $\delta(P)$ is $+1$ or $-1$, depending on whether $P$ is counter- or 
clockwise oriented.}

\proof{It is well known that each simple polygon can be triangulated and that among the triangles of any triangulation there is at 
least one, two of whose sides are sides of the original polygon. Apply this to $P$ and let $T=ABC$ denote such a triangle. If $P=T$ 
then we are done. Otherwise one side, say $BC$, of $T$ is a diagonal of $P$, and the removal of $T$ from $P$ leaves another simple 
polygon $P^\prime$ with $BC$ as a side. We claim that $\delta(P) = \delta(P^\prime)$. There are four cases to consider depending on 
whether the turns of $P$ at $B$ and $C$ are left or right. See figure \Fig1.
\capfig 4cm{\hfil Figure 1.}
Using the property that in a triangle an exterior angle is equal to the sum of the opposite two interior angles, we can easily 
verify in all cases that the net change in the sum of angles between $P$ and $P^\prime$ is zero.}

Lemma \Th1 allows us to derive an efficient test for whether a point $q$ is inside a simple polygon $P$. Let $m
0, t
0, m
1, t
1, 
m
2$,$ \ldotss, t
{n-1}, m
{n-1}$ be the moves and turns of the tracing, in their order of occurrence. We define the Boolean 
predicate $L
i(q)$ as being true if point $q$ is to the left of the line supporting move $m
i$. Then we define the predicate 
$S
i(q)$ as being $L
i(q)\land L\pr
{i+1}(q)$ if the turn $t
i$ is a left turn, and $L\pr
i(q)\land L
{i+1}(q)$ otherwise (where 
the index $i+1$ is taken modulo $n$ and ``$\null^\prime$'' denotes complementation). Intuitively, the predicate $S
i(q)$ is true if 
$q$ is swept by the turn $t
i$\foot\dag{If $q$ lies on the line of $m
i$, we take $L
i(q)$ as being true or false according to 
whether we want the resulting test to exclude boundary points of the polygon or not. Either way, it is not necessary to test 
whether $q$ actually lies between the two endpoints of the move. Also, if the turn $t
i$ is null, we let $S
i(q)$ be false.}.

From theorem \Th{\Sec3.2} of [\Kin] and lemma \Th1, we conclude that the point $q$ is inside or outside $P$ depending on whether 
its sweep number $\sw
A(p)$ is $0$ or $\pm 1$. Clearly, we will have one or the other depending on whether the number of terms 
$S
i(q)$ that are true is even or odd. Therefore, we have

\theorem{\Th2}{The point $q$ is inside the simple polygon $P$ if and only if the following exclusive or yields false  
$$S
0(q)\xor S
1(q)\xor S
2(q)\xor \ldots\xor S
{n-1}(q).$$.}

In practice the typical situation will be that $P$ is fixed while $q$ is variable. Thus in the preprocessing stage we can make the 
distinction between the two forms of $S
i(q)$, as well as precompute the line equation of each side. Then the computation of 
$L
i(q)$ takes only two multiplications, two additions, and one comparison.

The predicate $L
{i}(q)$ corresponds to testing whether the following determinant is positive:
$$\detmat{\matrix3{
  x
{v
{i-1}}  y
{v
{i-1}}  1 \cr
  x
{v
{i}}  y
{v
{i}}  1 \cr
  x
{q}  y
{q}  1 \cr}}$$

Expanded by the first column, this becomes
$$x
{v
{i-1}} (y
{v
{i}} - y
q)  -  x
{v
{i}} (y
{v
{i-1}} - y
q)  +  x
q (y
{v
{i-1}} - y
{v
{i}})$$
The turn $t
{i}$ is to the left (resp. right) iff the determinant below is positive (resp. negative):
$$\detmat{\matrix3{
  x
{v
{i-1}}  y
{v
{i-1}}  1 \cr
  x
{v
{i}}  y
{v
{i}}  1 \cr
  x
{v
{i+1}}  y
{v
{i+1}}  1 \cr}}$$

Therefore, if we expand all determinants as above, the test requires $6n$ multiplications, $10n$ additions/subtractions, and $O(n)$ 
comparisions with zero and boolean operations.

It is clear that all these computations can be carried on in a single pass over the vertices, without any auxiliary arrays. In 
particular, there is no need to store the $L
{i}$'s and $S
{i}$'s.  

If we have many points to test against the same polygon, we can expand the $L
{i}(q) $ determinant by the last row as
$$x
q (y
{v
{i-1}} - y
{v
{i}})  +  y
q (x
{v
{i}} - x
{v
{i-1}})  +  (x
{v
{i-1}} y
{v
{i}} - y
{v
{i-1}} x
{v
{i}})$$

We then precompute the coefficients
$$\eqalign{
  A
{i}  = (y
{v
{i-1}} - y
{v
{i}}),\cr
  B
{i}  = (x
{v
{i}} - x
{v
{i-1}}), \hbox{\ and}\cr
  C
{i}  = (x
{v
{i-1}} y
{v
{i}} - y
{v
{i-1}} x
{v
{i}})\cr}$$
of the line $v
{i-1}v
{i}$. We also precompute (as discussed above) the boolean flags $T
{i}$ that are true iff the turn $t
{i}$ 
turns to the left. This all can be done in $5n$ multiplications, $6n$ add/subtracts, and sundry compares + booleans. Then for each 
point $q$ we compute $L
{i}(q)$ by evaluating $x
q A
{i} + y
q B
{i} + C
{i}$, and compute
$$S
{i}(q) = (T
{i}\pr \xor L
{i}(q)) \and (T
{i} \xor L
{i+1}(q))$$

This takes an additional $2n$ multiplications, $3n$ add/subtracts, $n$ compares with zero, and $4n$ boolean operations, for each 
point $q$.

\vfill\eject\end