Point-in-Polygon and Polygon Touches Predicates

In a live air-routing system we must constantly answer queries such as: does a waypoint lie inside a restricted-airspace polygon? Such Boolean queries on geometric configurations are called spatial predicates.

The point-in-polygon (PIP) predicate decides whether a point $P$ lies inside a closed simple polygon $\Omega$. The standard algorithm is ray casting (a.k.a. the parity test):

1. Cast a ray from $P$ in some direction (commonly $+x$).
2. Count the number $k$ of polygon edges the ray crosses.
3. If $k$ is odd, $P$ is inside; if $k$ is even, $P$ is outside.

To test whether a horizontal $+x$ ray from $P=(P_x,P_y)$ crosses the edge from $A=(A_x,A_y)$ to $B=(B_x,B_y)$, we require:

(i) $P_y$ strictly between $A_y$ and $B_y$: $\min(A_y,B_y) < P_y < \max(A_y,B_y)$.

(ii) The edge's $x$-coordinate at height $P_y$,

$$x^* = A_x + \dfrac{P_y - A_y}{B_y - A_y}\,(B_x - A_x),$$

satisfies $x^* > P_x$.

Illustration: triangle $(0,0),(4,0),(2,4)$ with $P=(2,1)$.

• Edge $(0,0)\!\to\!(4,0)$: $A_y=B_y=0$, ray at $y=1$ is not strictly between. Skip.
• Edge $(4,0)\!\to\!(2,4)$: $0<1<4$ ✓. $x^* = 4 + \tfrac{1-0}{4-0}(2-4) = 3.5 > 2$ ✓. Cross.
• Edge $(2,4)\!\to\!(0,0)$: $0<1<4$ ✓. $x^* = 2 + \tfrac{1-4}{0-4}(0-2) = 0.5 < 2$. No.

Total crossings $k=1$ (odd), so $P$ is inside the triangle.