% SPIncl.text of December 1, 1983 3:52 am --- Stolfi

Algorithm for point inclusion in a simple polygon:

Source: "A kinetic framework for computational geometry" Leo Guibas, Lyle Ramshaw, and Jorge Stolfi. Proceedings 24th FOCS (november 1983).

Let P be a simple polygon, with vertices v[0], v[1], v[2], ..., v[n-1], and turning angles t[0], t[1], ..., t[n-1], in counterclockwise order (the turning angle at a vertex is positive if the polygon turns left at that vertex, negative if it turns right, and zero if it continues on the same line).

Define the Boolean predicate L[i](q) as being true if point q is to the left of the line v[i-1]v[i]. Then we define the predicate S[i](q) as being "L[i](q) AND NOT L[i+1](q)" if the turn t[i] is a left turn, and "NOT L[i](q) AND L[i+1](q)" otherwise. (The indices i+1 and i-1 are taken modulo n).

Intuitively, the predicate S[i](q) is true if q is swept by the turn t[i]. If q lies on the line v[i-1]v[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 (it does not matter whether q lies between the two vertices or not). Also, if the turn t[i] is null, we let S[i](q) be false.

It turns out that the point q is inside or outside P depending on whether it is swept an even or odd number of times by the turns. Therefore, the point q is inside P if and only if the exclusive or of all S[i](q),

S[0](q) XOR S[1](q) XOR S[2](q) XOR ... XOR S[n-1](q)

is false. (See the paper for a proof.)

The predicate L[i](q) corresponds to testing whether the following determinant is positive:

| xv[i-1] yv[i-1] 1 |
| |
| xv[i] yv[i] 1 |
| |
| xq yq 1 |

Expanded by the first column, this becomes

xv[i-1] (yv[i] - yq) - xv[i] (yv[i-1] - yq) + xq (yv[i-1] - yv[i])

The turn t[i] is to the left (resp. right) iff the determinant below is positive (resp. negative):

| xv[i-1] yv[i-1] 1 |
| |
| xv[i] yv[i] 1 |
| |
| xv[i+1] yv[i+1] 1 |

Therefore, if we expand all determinants as above, the test requires 6n multiplications, 10n additions/subtractions, and O(n) comparisions with zero + 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 (yv[i-1] - yv[i]) + yq (xv[i] - xv[i-1]) + (xv[i-1] yv[i] - yv[i-1] xv[i])

We then precompute the coefficients A[i] = (yv[i-1] - yv[i]), B[i] = (xv[i] - xv[i-1]), and C[i] = (xv[i-1] yv[i] - yv[i-1] xv[i]) 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) = ((NOT T[i]) 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 ops, for each point q.