From Noisy Points to Clean Routes
Open any navigation app and your position sits neatly on the road. But the raw GPS data rarely falls exactly on a road — it scatters in a cloud with 3-50 meter uncertainty, sometimes placing you on the wrong side of a highway, on a parallel street, or in a building. Map matching is the algorithmic bridge between raw GPS measurements and clean road-level positioning, and it runs invisibly on billions of devices worldwide.
The Candidate Search
For each GPS point, the matcher identifies candidate road segments within a search radius. In sparse rural areas there may be only one candidate; in dense urban grids, dozens. The simulation visualizes this search process, highlighting candidate segments and showing why simple nearest-road matching fails when multiple roads are within the GPS error circle. The search radius must balance completeness (including the correct road) against computational cost.
Hidden Markov Model Matching
The state-of-the-art approach models map matching as a Hidden Markov Model. The hidden states are road positions; GPS observations are noisy emissions. The emission probability decreases with distance from GPS point to road. The transition probability between consecutive road positions depends on the difference between shortest-path distance and great-circle distance — penalizing routes that require implausible detours. The Viterbi algorithm finds the globally optimal path through this probability lattice.
Challenges at Scale
Real-world map matching must handle GPS outages (tunnels, urban canyons), U-turns, one-way streets, altitude ambiguity (overpasses vs. underpasses), and map errors. Low-sampling-rate data (one point per minute from fleet GPS) leaves large gaps that span multiple intersections, requiring path inference not just point snapping. The simulation lets you increase noise and road density to observe how these challenges degrade matching accuracy and how algorithmic parameters can compensate.