17.5 Point in Polygon
Given a polygon and a query point, determine whether the point lies: ```text inside the polygon outside the polygon
17.5 Point in Polygon
Problem
Given a polygon and a query point, determine whether the point lies:
inside the polygon
outside the polygon
on the boundary
This problem appears in geographic information systems, computer graphics, collision detection, CAD software, robotics, game engines, and spatial databases. A map application may need to determine which administrative region contains a GPS coordinate. A game engine may need to determine whether a character is inside a trigger zone. A graphics system may need to determine whether a pixel belongs to a shape.
The challenge is supporting arbitrary polygons, including non-convex polygons, while handling boundary cases correctly.
Solution
Use the Ray Casting Algorithm.
Cast a horizontal ray from the query point toward positive infinity and count how many polygon edges the ray intersects.
If the number of intersections is:
odd
the point lies inside.
If the number of intersections is:
even
the point lies outside.
Example:
*
/ \\n / P \\n--------*-------*-------->
\ /
\ /
*
The ray intersects the polygon once.
Result:
inside
Core Idea
Imagine walking from the query point toward infinity.
Each time the ray crosses the polygon boundary, you switch between:
outside
inside
outside
inside
...
Therefore:
| Crossings | Result |
|---|---|
| 0 | Outside |
| 1 | Inside |
| 2 | Outside |
| 3 | Inside |
| 4 | Outside |
Only the parity matters.
Basic Implementation
Assume:
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
Polygon vertices:
polygon = [p0, p1, ..., pn-1]
Implementation:
def point_in_polygon(point, polygon):
inside = False
n = len(polygon)
for i in range(n):
j = (i + 1) % n
a = polygon[i]
b = polygon[j]
intersects = (
(a.y > point.y) != (b.y > point.y)
)
if intersects:
x_intersection = (
a.x +
(point.y - a.y) *
(b.x - a.x) /
(b.y - a.y)
)
if point.x < x_intersection:
inside = not inside
return inside
The variable:
inside
toggles each time the ray crosses an edge.
Example
Consider rectangle:
(0,0)
(6,0)
(6,4)
(0,4)
Query point:
(3,2)
Visual representation:
+------+
| |
| P |
| |
+------+
Horizontal ray:
P -------------------->
Crosses the rectangle once.
Count:
1
Result:
inside
Outside Example
Same rectangle.
Query point:
(8,2)
Visual representation:
+------+
P
The ray never enters the polygon.
Crossings:
0
Result:
outside
Why It Works
Every boundary crossing changes containment status.
Imagine entering a room.
Crossing the wall once moves you:
outside → inside
Crossing again moves you:
inside → outside
The ray casting method formalizes this observation.
Boundary Detection
Applications often require three results:
inside
outside
boundary
Before applying ray casting, check whether the point lies on an edge.
Using orientation:
def orientation(a, b, c):
return (
(b.x - a.x) * (c.y - a.y)
-
(b.y - a.y) * (c.x - a.x)
)
And:
def on_segment(a, b, p):
return (
min(a.x, b.x) <= p.x <= max(a.x, b.x)
and
min(a.y, b.y) <= p.y <= max(a.y, b.y)
)
Boundary test:
if orientation(a, b, p) == 0 and \\n on_segment(a, b, p):
return "boundary"
Only after checking boundaries should ray casting begin.
Non-Convex Polygons
A major advantage of ray casting is that it works for arbitrary simple polygons.
Example:
*
/ \\n * *
\ /
*
Query point inside the indentation:
odd crossings
Result:
inside
No convexity assumption is required.
Convex Polygon Alternative
For convex polygons, faster methods exist.
Using orientation tests:
point must remain on same side
of every edge
Example:
for each edge:
orientation(edge, point)
If all orientations have the same sign:
inside
Complexity:
O(n)
and with preprocessing:
O(log n)
queries are possible.
However, ray casting works for both convex and non-convex polygons.
Winding Number Method
A second approach uses winding numbers.
Instead of counting intersections, it measures how many times the polygon winds around the point.
Outside:
winding number = 0
Inside:
winding number ≠ 0
Advantages:
- Handles complex polygons
- More mathematically elegant
- Useful in graphics systems
Disadvantages:
- Slightly more complicated
Ray casting remains the most common practical solution.
Degenerate Cases
Point at a Vertex
Example:
P
/ \\n```
The point coincides with a polygon vertex.
Most systems classify this as:
```text
boundary
Point on an Edge
Example:
A-----P-----B
Classification:
boundary
Horizontal Edges
Horizontal edges can produce double counting.
A standard implementation counts an edge only when:
one endpoint is above the ray
and the other is below
This avoids duplicate intersections.
Applications
Geographic Information Systems
Determine which region contains a coordinate.
Computer Graphics
Determine whether a pixel belongs to a polygon.
Robotics
Determine whether a robot occupies a forbidden area.
Collision Detection
Check whether an object enters a zone.
Spatial Databases
Evaluate containment queries.
Complexity Analysis
For a polygon containing:
n vertices
Ray casting requires:
O(n)
time.
Space usage:
O(1)
excluding input storage.
For many practical applications, this performance is sufficient.
Common Pitfalls
Double Counting Vertices
The ray may intersect two edges at the same vertex.
Careful endpoint rules are necessary.
Ignoring Boundary Cases
Users usually expect points on edges to be treated differently from points outside.
Self-Intersecting Polygons
Ray casting assumes a simple polygon.
Self-intersections introduce ambiguity.
Floating-Point Precision
Near-edge points often generate unstable results.
Use epsilon comparisons:
EPS = 1e-9
when testing orientation.
Horizontal Edge Handling
Naive implementations frequently count intersections twice.
This is one of the most common bugs.
Discussion
Point-in-polygon testing is one of the most widely used geometric predicates. Despite its apparent complexity, the ray casting algorithm reduces the problem to counting edge crossings. The method requires only a linear scan, supports arbitrary simple polygons, uses constant additional memory, and is straightforward to implement. Combined with orientation tests and segment predicates from previous sections, it forms a core component of practical geometry libraries.
The next section moves from containment queries to one of the most important construction algorithms in computational geometry: building the convex hull of a set of points.