Winding Numbers and Point-in-Polygon

The Problem

Given a polygon $P$ (assumed planar, closed, and simple unless stated otherwise) and a point $Q$, determine whether $Q$ is inside or outside $P$.

Two main approaches exist: ray casting and winding numbers. For simple polygons they produce identical results. For complex (self-intersecting) polygons, they may differ, and the winding number provides a more useful definition.

Ray Casting (Crossing Number)

Shoot a ray (semi-line) from $Q$ in any direction. Count the number of intersections of the ray with polygon edges:

• Odd count: $Q$ is inside
• Even count: $Q$ is outside

Why It Works

The polygon divides the plane into inside and outside regions. Every time the ray crosses an edge, it moves from inside to outside (or vice versa). Since the ray starts at $Q$ and extends to infinity (which is outside), the parity of crossings determines the initial region.

Awkward Cases

The ray may pass through a vertex or be collinear with an edge. Solutions:

1. Shoot a horizontal ray (avoids floating-point ambiguity with vertical comparisons).
2. If the ray hits a vertex, check the neighbouring vertices:
   • If both neighbours are on the same side of the ray (both above or both below), the ray grazed the vertex — no crossing.
   • If neighbours are on opposite sides, the edge was crossed.
3. If a neighbour is also on the ray, skip it and check the next vertex in the same direction around the perimeter.

Alternatively, pick a random ray direction; with probability 1 it will miss all vertices (assuming finite precision is not an obstacle).

Complexity

For $n$ vertices: $\Theta(n)$ time — each edge is tested once.

Winding Number

The winding number of $Q$ with respect to polygon $P$ is the number of times the polygon “winds around” $Q$. Formally:

$w = \frac{1}{2\pi} \sum_{i=1}^{n} \theta_i$

where $\theta_i$ is the signed angle subtended by edge $p_i p_{i+1}$ at point $Q$.

• $w = 0$: $Q$ is outside
• $w = \pm 1$: $Q$ is inside (for simple polygons)
• $|w| > 1$: $Q$ is inside a self-intersecting polygon, wound around multiple times

Implementation Without Trigonometry

Computing actual angles via arctangent is slow and suffers floating-point error. Instead, use cross products and dot products to compute the signed contribution of each edge.

For each edge $AB$, the signed angle contribution can be determined from:

$\overrightarrow{QA} \times \overrightarrow{QB} \quad \text{and} \quad \overrightarrow{QA} \cdot \overrightarrow{QB}$

The cross product gives the sine of the angle (signed); the dot product gives the cosine. The quadrant of the angle determines the exact contribution to the winding number without needing $\arctan$.

Intuition

Imagine a string attached to a post at point $Q$. Walk around the polygon perimeter holding the string. When you return to the start, count how many times the string is wrapped around the post. Odd wraps = inside, even = outside.

Comparison

Method	Simple Polygons	Complex Polygons	Time	Trig?
Ray casting	$\Theta(n)$	Ambiguous	$\Theta(n)$	No
Winding number	$\Theta(n)$	Well-defined	$\Theta(n)$	Can avoid

Worked Example: Ray Casting

Polygon: square with vertices $(0,0), (4,0), (4,4), (0,4)$. Test point $Q = (2,2)$ with a horizontal ray to the right.

Edges checked:

• $(0,0)\to(4,0)$: $y=0$, ray at $y=2$, no intersection.
• $(4,0)\to(4,4)$: vertical edge at $x=4$, ray from $x=2$ hits at $(4,2)$. Intersection! Count = 1.
• $(4,4)\to(0,4)$: $y=4$, no intersection.
• $(0,4)\to(0,0)$: vertical edge at $x=0$, but ray goes right from $x=2$, so no intersection.

Count = 1 (odd) → inside. Correct.

Summary

Concept	Detail
Ray casting	Count edge crossings; odd = inside
Winding number	Sum signed angles / $2\pi$; 0 = outside
Horizontal ray	Simplest to implement
Vertex handling	Check neighbours: same side = grazing (no count)
Complexity	$\Theta(n)$ for both methods
No trigonometry	Use cross products and dot products for winding number