⚙️ How-To Movement & time Networks & routing Movement & Time · step 12 of 14 Updated

How to Map-Match a GPS Track to a Street Network

Problem statement

Map matching answers "which streets did this track use", and the obvious implementation — snap every point to its nearest edge — produces a sequence of streets nobody could have driven.

Measured on 13 real GPS traces against an OpenStreetMap drive network of central Manchester:

snap distance to the nearest edge
  p50    12.0 m
  p90    67.0 m
  p99   117.5 m
  max   138.9 m
  over  50 m: 18.51% of points
  over 100 m:  2.99%

the nearest edge changes on 23.8% of consecutive fixes
of those changes, 11.1% jump to an edge that shares no node

One fix in nine that changes street jumps to a road not connected to the previous one. That is a teleport, and no amount of better snapping fixes it, because the problem is that each point was matched independently.

Quick answer

Match the sequence, not the points. Score candidate edges by both distance and connectivity:

import numpy as np
import networkx as nx
import osmnx as ox


def match_sequence(G, points, radius=50, max_candidates=5):
    """Viterbi-style match: emission by distance, transition by route length."""
    candidates = [nearby_edges(G, p, radius, max_candidates) for p in points]

    scores = {c: emission(points[0], c) for c in candidates[0]}
    back = [{}]
    for i in range(1, len(points)):
        new_scores, pointers = {}, {}
        for c in candidates[i]:
            best, best_prev = -np.inf, None
            for prev, prev_score in scores.items():
                s = prev_score + transition(G, prev, c, points[i - 1], points[i]) \
                    + emission(points[i], c)
                if s > best:
                    best, best_prev = s, prev
            new_scores[c], pointers[c] = best, best_prev
        scores, back = new_scores, back + [pointers]

    path = [max(scores, key=scores.get)]
    for pointers in reversed(back[1:]):
        path.append(pointers[path[-1]])
    return list(reversed(path))

The transition term is what removes the teleports: a candidate edge is penalised when the route from the previous edge to it is far longer than the distance the vehicle could have travelled.

Independent nearest-edge snapping producing a disconnected sequence of streets against a sequence match that requires each step to be reachable from the last.
Independent snapping made 11.1% of street changes jump to a disconnected road.

Step-by-step solution

1. Use the right network for the mode

The p90 snap distance above is 67 m, which is far more than GPS error. The reason is that many of these traces are pedestrians — the median speed was 4.7 km/h — and they were being matched against a drive network that has no footpaths.

G = ox.graph_from_bbox(bbox, network_type="walk")   # not "drive"

Choosing the wrong network type produces large, systematic snap distances that look like GPS error and are not. Check the distribution: a p50 of 12 m is plausible for GPS; 18.5% of points beyond 50 m is not.

2. Project everything before measuring

Snapping compares distances. In degrees those distances are wrong, and wrong differently in each direction.

G = ox.project_graph(G, to_crs="EPSG:32630")

3. Generate candidates, not a single match

For each fix, take every edge within a radius — 30–50 m for good urban data, more where accuracy is poor. Keeping five candidates per point is usually plenty.

A single nearest edge throws away the information that resolves ambiguity: on a dual carriageway the two carriageways are metres apart, and only the sequence says which one you were on.

4. Score each candidate two ways

  • Emission: how well does this edge explain this observation? Usually a Gaussian on the perpendicular distance, with a standard deviation set to the GPS error.
  • Transition: how plausible is moving from the previous candidate to this one? Compare the shortest-path distance along the network with the straight-line distance between the two fixes. A ratio near 1 is plausible; a ratio of 10 means the route required a detour the timing does not allow.

5. Solve the sequence with Viterbi

The two scores define a hidden Markov model where the hidden state is "which edge am I on". The Viterbi algorithm finds the most likely sequence in time linear in the number of points and quadratic in the number of candidates.

6. Check the output for the failure you were fixing 

jumps = sum(1 for a, b in zip(path, path[1:])
            if not set(a[:2]) & set(b[:2]))
print(f"{jumps} disconnected transitions remain")

A good match has none, or has them only across genuine data gaps.

Candidate edges scored by perpendicular distance and by whether the network route between consecutive candidates matches the distance travelled.
Distance alone cannot choose between two parallel carriageways. The route between fixes can.

Code examples

Example 1 — candidates and emission scores 

import numpy as np
import osmnx as ox
from shapely.geometry import Point, LineString


def edge_geometry(G, u, v, k):
    edge = G.edges[u, v, k]
    if "geometry" in edge:
        return edge["geometry"]
    return LineString([(G.nodes[u]["x"], G.nodes[u]["y"]),
                       (G.nodes[v]["x"], G.nodes[v]["y"])])


def candidates(G, edges_gdf, sindex, x, y, radius=50.0, limit=5):
    """Every edge within radius of the fix, with its perpendicular distance."""
    point = Point(x, y)
    idx = list(sindex.intersection(point.buffer(radius).bounds))
    found = []
    for i in idx:
        row = edges_gdf.iloc[i]
        distance = point.distance(row.geometry)
        if distance <= radius:
            found.append((row.name, float(distance)))
    found.sort(key=lambda t: t[1])
    return found[:limit]


def emission(distance, sigma=10.0):
    """Log-likelihood that this edge produced this observation."""
    return -0.5 * (distance / sigma) ** 2

Setting sigma to the actual GPS error matters. Too small and the match becomes a nearest-edge snap with extra steps; too large and distance stops discriminating at all.

Example 2 — the transition score 

import networkx as nx


def transition(G, prev_edge, next_edge, prev_point, next_point,
               beta=10.0, cache=None):
    """Penalise routes much longer than the straight-line step."""
    straight = ((next_point[0] - prev_point[0]) ** 2 +
                (next_point[1] - prev_point[1]) ** 2) ** 0.5

    key = (prev_edge[1], next_edge[0])
    if cache is not None and key in cache:
        route = cache[key]
    else:
        try:
            route = nx.shortest_path_length(G, key[0], key[1], weight="length")
        except nx.NetworkXNoPath:
            route = float("inf")
        if cache is not None:
            cache[key] = route

    if not np.isfinite(route):
        return -1e6                        # unreachable: effectively forbidden
    return -abs(route - straight) / beta

Caching the shortest path between node pairs is what makes this tractable. With five candidates per fix, consecutive steps ask for the same node pairs repeatedly.

The -1e6 for unreachable pairs is what eliminates the 11.1% of disconnected jumps measured above: an impossible transition can never win, no matter how good its emission score.

Example 3 — a diagnostic before and after 

import numpy as np


def match_quality(G, points, matched):
    """Snap distance and connectivity, before trusting the result."""
    distances = []
    for (x, y), edge in zip(points, matched):
        geom = edge_geometry(G, *edge)
        distances.append(Point(x, y).distance(geom))
    distances = np.array(distances)

    jumps = sum(1 for a, b in zip(matched, matched[1:])
                if a != b and not set(a[:2]) & set(b[:2]))
    changes = sum(1 for a, b in zip(matched, matched[1:]) if a != b)

    print(f"  snap distance p50 {np.median(distances):5.1f} m, "
          f"p90 {np.percentile(distances, 90):5.1f} m, "
          f"max {distances.max():5.1f} m")
    print(f"  {changes} edge changes, {jumps} disconnected "
          f"({jumps / max(changes, 1):.1%})")
    if np.percentile(distances, 90) > 40:
        print("  ! large snap distances — check the network type matches the mode")
    return {"p50": float(np.median(distances)),
            "p90": float(np.percentile(distances, 90)),
            "disconnected": jumps, "changes": changes}
  snap distance p50  12.0 m, p90  67.0 m, max 138.9 m
  1529 edge changes, 169 disconnected (11.1%)
  ! large snap distances — check the network type matches the mode

That is the before. The warning is the useful part: it identified the real problem in this dataset, which was the network type rather than the algorithm.

Explanation

Why nearest-edge snapping fails

Each point is matched independently, so nothing prevents consecutive points landing on unrelated roads. The measurement is unambiguous: 23.8% of consecutive fixes changed edge, and 11.1% of those changes went to an edge sharing no node with the previous one.

In dense networks the nearest edge flips between parallel streets, between a road and a service road behind it, and between the two carriageways of a dual carriageway. Each flip is a plausible local decision and the sequence is nonsense.

Why the transition term is the whole algorithm

The insight behind every modern matcher is that movement is constrained. Between two fixes three seconds apart, a vehicle can travel maybe fifty metres along the network — so any candidate requiring a five-hundred-metre detour is wrong regardless of how close it is.

Comparing network distance with straight-line distance captures this in one number. It also handles the U-turn case correctly: doubling back is possible but requires travelling much further than the straight line, so it is penalised rather than forbidden.

Why the network type matters more than the algorithm

The measured p90 snap distance of 67 m is not GPS error — good urban GPS is within 10–20 m, which is what the p50 of 12.0 m reflects. It is the distance from a footpath to the nearest road.

Matching pedestrians to a drive network gives a confident, smooth, entirely fictional route along the roads beside the paths they used. No matcher can detect this, because the input contains nothing that says the pedestrian was not in the road.

Choose network_type from the mode. Where the mode is unknown, match against all and infer the mode from which classes of edge the match used.

Why matching cannot always be right

Map matching is inference, not measurement. Where the network is dense relative to the position error and the sampling is coarse, several routes explain the observations equally well.

Good matchers return a confidence — the margin between the best path and the next best. A low margin means the answer is a guess, and downstream analysis should be able to see that rather than treating every matched route as fact.

Snap distances with a median of 12 m and a 90th percentile of 67 m, indicating pedestrians matched to a drive network.
The median is plausible GPS error. The tail is the distance from a footpath to the nearest road.

Edge cases or notes

  • Choose the network type from the mode. A p90 snap distance above about 40 m usually means the wrong network.
  • Project before snapping. Degrees are not metres.
  • Split at data gaps. Matching across a fifty-minute gap invents a route.
  • Cache shortest paths between node pairs, or the transition term dominates the runtime.
  • Keep three to five candidates per fix. More rarely changes the answer and is quadratically more expensive.
  • Set the emission sigma to the real GPS error, not to a round number.
  • One-way streets matter. Match on the directed graph, or the route will include illegal moves.
  • Report a confidence, not just a route.

FAQ

How do I map-match a GPS track in Python?

Generate several candidate edges per fix, score each by perpendicular distance and by whether the network route from the previous candidate matches the distance travelled, and solve the sequence with Viterbi.

Why does nearest-edge snapping give a broken route?

Because each point is matched independently. Measured on real traces, 23.8% of consecutive fixes changed edge and 11.1% of those changes jumped to a disconnected road.

What snap distance should I expect?

Around 10–20 m at the median for good urban GPS on the right network. A p90 of 67 m, as measured here, means the network type does not match the travel mode.

Which network type should I use?

The one matching the mode: walk for pedestrians, drive for vehicles, bike for cycling. Matching pedestrians to a drive network produces a confident, fictional route.

How do I handle data gaps?

Split the track and match each leg separately. Matching across a gap forces the algorithm to invent a route.

How do I know if the match is right?

Check that consecutive matched edges share a node, and report the margin between the best path and the second best. A small margin means the answer is a guess.

Do I need a library, or is this enough?

The sketch here is a working Viterbi matcher. Established libraries add one-way handling, better candidate pruning and calibrated parameters — worth using in production, but the mechanism is exactly this.