\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 $m0, t0, m1, t1, m2$,$ \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 $Li(q)$ as being true if point $q$ is to the left of the line supporting move $mi$. Then we define the predicate $Si(q)$ as being $Li(q)\land L\pr{i+1}(q)$ if the turn $ti$ is a left turn, and $L\pri(q)\land L{i+1}(q)$ otherwise (where the index $i+1$ is taken modulo $n$ and ``$\null^\prime$'' denotes complementation). Intuitively, the predicate $Si(q)$ is true if $q$ is swept by the turn $ti$\foot\dag{If $q$ lies on the line of $mi$, we take $Li(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 $ti$ is null, we let $Si(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 $\swA(p)$ is $0$ or $\pm 1$. Clearly, we will have one or the other depending on whether the number of terms $Si(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
$$S0(q)\xor S1(q)\xor S2(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 $Si(q)$, as well as precompute the line equation of each side. Then the computation of $Li(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}} - yq) - x{v{i}} (y{v{i-1}} - yq) + xq (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
$$xq (y{v{i-1}} - y{v{i}}) + yq (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 $xq A{i} + yq 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$.