Geofencing and the Point-in-Polygon Problem
Geofencing involves creating virtual boundaries (polygons) around real-world geographical areas. When a user or device enters, exits, or lingers within these boundaries, the system triggers an event. Applications range from targeted advertising and location-based reminders to fleet management and airport surge pricing zones.
The Core Algorithm
At the mathematical heart of geofencing is the "Point-in-Polygon" (PIP) problem. Given a coordinate (a point) and a set of vertices (a polygon), how do we determine if the point is inside the polygon?
Optimizing Geofencing at Scale
Evaluating the PIP algorithm for every user against every polygon is computationally impossible at scale. System design requires multi-stage filtering:
- Bounding Box Filtering: Every polygon has a minimum bounding box (MBR). PostGIS commonly uses a GiST spatial index with bounding-box operators to find candidate polygons before the exact predicate. This reduces the candidate polygons from millions to a handful.
- Exact PIP Calculation: Only for the polygons that pass the bounding box filter, the system runs an exact point-in-polygon test (for example ray casting, O(V) per polygon; libraries such as GEOS/PostGIS use prepared geometries with edge indexes for repeated tests) to confirm if the point is truly inside the precise polygon boundaries.
System Architecture
A stream processor can index versioned polygons and consume location updates, but point membership alone does not define an enter/exit event. Persist the last evaluated polygon version and membership per device. For example, GPS jitter around an airport boundary can alternate inside/outside every second; require hysteresis, consecutive observations, or a dwell interval before emitting a transition. Give transitions stable IDs so replay after a crash does not send duplicate notifications, and define how a polygon edit re-evaluates devices already nearby.
Worked example: delivery zones
Assume 50,000 polygons (delivery zones and airport pickup areas) averaging 200 vertices, and 200,000 location updates per second.
- Naive: 200,000 x 50,000 = 10 billion polygon tests per second. Impossible.
- R-tree on bounding boxes: each point overlaps on average about 1.5 polygon bounding boxes. That is 300,000 exact tests per second, each O(V) with 200 edges, about 60 million edge checks per second: a handful of CPU cores.
- H3 pre-classification: fill each polygon with H3 resolution 9 cells (about 0.1 square km). Cells fully inside the polygon are marked interior, cells crossing the border are marked boundary. A point in an interior cell is inside with no geometry work; only points in boundary cells (often under 10 percent) need the exact test.
Indexing strategies
| Strategy | Lookup | Update cost when a polygon changes | Notes |
|---|---|---|---|
| Brute force within a city | Test every polygon in the city | None | Uber's early geofence service did this after first finding the city; fine for small counts |
| R-tree over bounding boxes (PostGIS GiST) | O(log n) plus exact tests | Reinsert one box | General purpose default |
| Cell map (H3 or S2) with interior and boundary cells | One hash lookup, exact test only on boundary cells | Recompute the polygon's cells | Fastest at very high point rates |
| Prepared geometry cache | Exact test in about O(log V) using an edge index | Rebuild per polygon version | Helps when polygons have thousands of vertices |
Event pipeline
- Hysteresis example: enter when the point is at least 20 m inside the boundary, exit only when at least 30 m outside, or require 3 consecutive fixes.
- Idempotency: event ID = hash(device, polygon, polygon_version, transition_sequence), so replay after a crash produces the same ID and consumers deduplicate.
- Partitioning by device keeps each device's membership state on one worker and preserves ordering of its fixes.