Point in Polygon — Ray Casting and Winding Number Algorithms
- Ray casting: count horizontal ray crossings — odd=inside, even=outside. O(n) per query.
- Winding number: more robust for complex/self-intersecting polygons. Used in GIS applications.
- Edge cases: ray through vertex or along edge require careful handling in ray casting.
Point-in-polygon (PIP) is one of the most frequently implemented computational geometry algorithms. GIS systems (is this GPS coordinate in this city boundary?), game physics (is the player inside this room?), UI hit-testing (was this click inside this region?), and graphics rendering all need PIP. Two main algorithms: ray casting (even-odd rule, simple) and winding number (handles self-intersecting polygons, more robust).
Ray Casting Algorithm
Cast a horizontal ray from the point to +infinity. Count boundary crossings — odd = inside, even = outside.
def point_in_polygon_ray(point, polygon) -> bool: """ Ray casting algorithm: cast ray from point to +x infinity. Count edge crossings — odd = inside, even = outside. """ x, y = point n = len(polygon) inside = False j = n - 1 for i in range(n): xi, yi = polygon[i] xj, yj = polygon[j] # Does edge i-j cross the horizontal ray from (x,y) to +infinity? if ((yi > y) != (yj > y)) and \ (x < (xj - xi) * (y - yi) / (yj - yi) + xi): inside = not inside j = i return inside # Square polygon square = [(0,0),(4,0),(4,4),(0,4)] print(point_in_polygon_ray((2,2), square)) # True (inside) print(point_in_polygon_ray((5,2), square)) # False (outside) print(point_in_polygon_ray((0,0), square)) # False (vertex — edge case)
False
False
Winding Number Algorithm
Winding number counts how many times the polygon winds around the point. Non-zero = inside. More robust than ray casting for self-intersecting polygons and complex GIS boundaries.
def winding_number(point, polygon) -> int: """Winding number: non-zero = inside.""" x, y = point wn = 0 n = len(polygon) for i in range(n): x1, y1 = polygon[i] x2, y2 = polygon[(i+1) % n] if y1 <= y: if y2 > y and orientation((x1,y1),(x2,y2),(x,y)) > 0: wn += 1 else: if y2 <= y and orientation((x1,y1),(x2,y2),(x,y)) < 0: wn -= 1 return wn square = [(0,0),(4,0),(4,4),(0,4)] print(winding_number((2,2), square)) # 1 (inside) print(winding_number((5,2), square)) # 0 (outside)
0
🎯 Key Takeaways
- Ray casting: count horizontal ray crossings — odd=inside, even=outside. O(n) per query.
- Winding number: more robust for complex/self-intersecting polygons. Used in GIS applications.
- Edge cases: ray through vertex or along edge require careful handling in ray casting.
- For convex polygons: O(log n) using binary search on angles from centroid.
Interview Questions on This Topic
- QExplain the ray casting algorithm and handle the vertex edge case.
- QWhen would you use winding number over ray casting?
- QHow would you optimise point-in-polygon for 10^6 queries against the same polygon?
Frequently Asked Questions
What is the performance of point-in-polygon for many queries?
Single query: O(n). For many queries against the same polygon: preprocess with a grid spatial index or R-tree — reduces average query to O(1) or O(log n). NumPy's vectorised ray casting handles millions of points per second against a single polygon.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.