Point-in-Polygon — Ray Casting

Drag the query point. A horizontal ray counts edge crossings — odd = inside, even = outside.

Query: O(n) Convex: O(log n) Space: O(1)

Polygon & Ray

polygon edge
edge being tested
counted crossing
query point
horizontal ray

Drag the purple point anywhere. Use Step to walk edges one at a time, or Run to animate.

Slow Fast

Verdict

— press Run or Step —
Edge
0 / 0
Crossings
0
Parity
EVEN

What's happening

The ray starts at the point and goes right. For each edge we test (ay>py) != (by>py) and whether the crossing is to the right of the point.

Complexity

MethodPer querySpace
Ray casting (any polygon)O(n)O(1)
Winding numberO(n)O(1)
Convex, binary searchO(log n)O(n)
Trapezoidal map (many q)O(log n)O(n)

Operation Log