The Ray Casting Algorithm
The ray casting algorithm is the most common mathematical solution to the Point-in-Polygon problem. It determines whether a point sits inside a complex, irregular polygon.
How It Works
The logic is elegantly simple based on topology: draw a horizontal ray (a straight line) starting from the point in question and extending to infinity in one direction (usually to the right). Then, count how many times this ray intersects the edges of the polygon.
- If the number of intersections is ODD, the point is INSIDE the polygon.
- If the number of intersections is EVEN, the point is OUTSIDE the polygon.
Handling Edge Cases
While conceptually simple, the implementation must handle tricky edge cases carefully:
- Boundary policy: First decide whether a point on an edge or vertex counts as inside, corresponding to semantics such as
coversversus strictcontains. Detect that case explicitly before odd/even counting. A half-open endpoint rule then prevents a vertex from contributing twice. - Horizontal edges: If the ray perfectly overlaps a horizontal edge of the polygon, it could cause issues. The vertex rules mentioned above usually resolve this naturally by ignoring horizontal edges entirely.
Computational Complexity
The basic test is O(N) in polygon edges. Production geometry also needs valid ring orientation, holes and multipolygons, a documented boundary rule, robust predicates near edges, and a coordinate model. Applying planar longitude/latitude arithmetic across the antimeridian or over large regions can be wrong; use an appropriate projected or spherical library. Spatial indexing narrows candidates but never replaces the exact predicate.
Worked example
Polygon: square with vertices (0,0), (4,0), (4,4), (0,4).
- Point (2,2): cast a ray to +x. Edge (4,0) to (4,4) straddles y = 2 (one endpoint below, one above) and crosses at x = 4, which is right of 2: 1 crossing. The left edge crosses at x = 0, left of the point, so it does not count. Odd, so inside.
- Point (5,2): both vertical edges cross at x = 0 and x = 4, left of 5: 0 crossings, outside.
- Point (2,4): lies on the top edge. A boundary pre-check reports "on boundary", then the product rule decides.
- Ray through a vertex: triangle (0,0), (4,2), (0,4) and point (1,2). The ray y = 2 passes through vertex (4,2). Edge (0,0) to (4,2): is 0 > 2 different from 2 > 2? Both false, so it does not count. Edge (4,2) to (0,4): is 2 > 2 different from 4 > 2? Yes, it counts once. Result 1 crossing: inside, which is correct. Without the half-open rule both edges would count and the answer would be wrong.
The standard loop
inside = false; for each edge (a, b): if ((a.y > p.y) != (b.y > p.y)) and (p.x < a.x + (p.y - a.y) * (b.x - a.x) / (b.y - a.y)) then inside = !inside
The first condition skips horizontal edges automatically (both endpoints on the same side) and implements the half-open vertex rule.
Crossing number versus winding number
| Aspect | Crossing number (even-odd) | Winding number (non-zero) |
|---|---|---|
| Idea | Parity of crossings | Net number of times the boundary wraps the point |
| Simple polygons | Same answer | Same answer |
| Self-intersecting shapes | Overlaps count as holes | Overlaps count as filled |
| Cost | O(V) | O(V), similar constant with the signed-crossing form |
| Used by | SVG and canvas even-odd fill rule | SVG and canvas nonzero fill rule (the default) |
Production concerns
- Holes and multipolygons: inside the outer ring and not inside any hole; for multipolygons, inside any part.
- Repeated queries: index edges by y-interval (as GEOS prepared geometries do) so each test is roughly O(log V) instead of O(V).
- Floating point: points within about 1e-9 of an edge can flip; use robust orientation predicates or snap to a tolerance, and document the boundary policy.