Snapping Synthetic Traces Without Teleporting Across Junctions

A map-matcher run over a synthetic trace produces a route that jumps sideways at a junction, doubles back, or abandons the obvious road for a parallel one. The coordinates are all within a few metres of the correct segments, and the match is still wrong.

Part of Map Matching & Network Snapping: this is the transition-cost failure, which is both the most common way a synthetic trace fails to match and the one whose cause is furthest from where the symptom appears.

Root Cause: The Matcher Is Enforcing a Rule the Generator Ignored

A matcher scores a candidate route by two terms. The emission term asks how far each fix is from its assigned segment; the transition term asks whether the movement between consecutive assignments was possible at all. A manoeuvre the network forbids does not have a large transition cost — it has an infinite one, because there is no path.

That produces a specific and confusing behaviour. Faced with a trace whose true route uses a banned turn, the matcher cannot return the true route at any price. It returns the best legal route instead, which may run along a different street entirely, and every fix in that stretch is then assigned to a segment several metres away. The output looks like an emission problem — fixes far from their segments — and tuning the emission sigma makes it worse rather than better.

The generator is the origin. If the routing stage consulted only connectivity, it produced paths that are geometrically continuous and legally impossible, and no downstream parameter recovers from that.

Probability a route touches a restricted junction, against route length The horizontal axis is the number of junctions a route passes through, from four for a short local trip to forty for a long cross-city one. The vertical axis is the probability that at least one of those junctions carries a turn restriction. A flat dashed line marks the share of junctions that are restricted at all, which is around eleven per cent and is the number people quote when arguing that restrictions are an edge case. The curve rises far above it: because the route passes many junctions and only needs to meet one restriction to be affected, the probability compounds, and by a dozen junctions the majority of routes touch at least one. By forty junctions almost every route does. Markers give the probability at three representative route lengths. The conclusion drawn underneath is that the per-junction share and the per-route share answer different questions and lead to opposite decisions: a tenth of junctions sounds like an edge case, and the fact that most routes touch one means a generator that ignores restrictions produces mostly unmatchable traces. 12% of junctions, and most routes — two numbers that argue opposite cases 4 8 12 18 26 40 0% 25% 50% 75% 100% junctions passed by the route routes touching ≥ 1 restriction (%) 12% of junctions are restricted 65% 90% 99% routes touching at least one restriction junctions that are restricted 2,500 junctions with a 12% restriction rate, 2,000 routes per length, fixed seed. Per-junction and per-route shares answer different questions: one makes restrictions look like an edge case, the other makes ignoring them the dominant source of unmatchable traces.
Measured across 2,500 simulated junctions: the share of junctions carrying at least one restriction is small, and the share of *routes* touching one is not.

Minimal Reproducer: Route Through a Banned Turn

python
import networkx as nx

g = nx.MultiDiGraph()
g.add_edge("A", "J", key="north_in", geometry=...)
g.add_edge("J", "B", key="east_out", geometry=...)
g.add_edge("J", "C", key="west_out", geometry=...)
# The junction bans a left turn from the northbound approach into the westbound exit.
g.nodes["J"]["no_turn"] = {("A", "J", "north_in"): {("J", "C", "west_out")}}


def connectivity_only(graph, src, dst):
    """What most generators do — and what produces unmatchable traces."""
    return nx.shortest_path(graph, src, dst)


path = connectivity_only(g, "A", "C")
print(path)                       # ['A', 'J', 'C'] — perfectly connected, and illegal

Nothing raises. The path is continuous, every coordinate is on a real road, and a matcher enforcing the restriction will refuse to reproduce it.

Fix: Consult Restrictions in the Generator, Then Verify the Match

1 — Make legality part of the successor function

python
def legal_successors(graph, node, arrived_by):
    """Edges leaving `node` that may be entered from `arrived_by`."""
    banned = graph.nodes[node].get("no_turn", {}).get(arrived_by, set())
    return [e for e in graph.out_edges(node, keys=True) if e not in banned]


def routed_walk(graph, rng, start_edge, steps):
    """A walk that cannot produce a manoeuvre the network forbids."""
    edge = start_edge
    path = [edge]
    for _ in range(steps):
        options = legal_successors(graph, edge[1], edge)
        if not options:
            break                       # a genuine dead end, not a bug
        edge = options[rng.integers(len(options))]
        path.append(edge)
    return path

This is a small change to the routing stage and it removes the entire failure class. Note the break rather than a fallback: a junction from which no legal manoeuvre exists is real — a turn-restricted cul-de-sac — and silently ignoring the restriction to keep the walk going reintroduces exactly the problem.

2 — Carry the true route with the trace during development

python
trace = {
    "fixes": perturb(render(path), rng),
    "true_route": [e for e in path],       # development only, never released
}

Keeping the generated route alongside the trace is what turns matching from a black box into a testable stage: the matcher’s output can be compared against the route the generator actually used, which is a ground truth that no real dataset has.

3 — Diagnose a mismatch by cost term, not by eye

python
def diagnose(trace, graph, matcher):
    got = matcher.match(trace["fixes"])
    want = trace["true_route"]
    if got.segments == want:
        return "ok"
    legal = all(nxt in legal_successors(graph, prev[1], prev)
                for prev, nxt in zip(want, want[1:]))
    if not legal:
        return "generator produced an illegal manoeuvre"
    emission_true = sum(matcher.emission_cost(f, s) for f, s in zip(trace["fixes"], want))
    emission_got = sum(matcher.emission_cost(f, s) for f, s in zip(trace["fixes"], got.segments))
    if emission_got < emission_true:
        return "emission: the wrong segment is genuinely nearer — noise is too wide"
    return "transition: the true route is legal but scored worse — check turn costs"

The three outcomes need three different fixes, and distinguishing them takes ten lines. Without it, every mismatch gets treated as an emission problem, because that is the only knob most matchers expose.

Three mismatch diagnoses, the test for each, and the stage each points at Three rows. The first is an illegal manoeuvre in the generated route: the test is to check every consecutive edge pair in the route the generator used against the network's turn restrictions, it points at the routing stage, and the fix is to make legality part of the successor function. The second is emission-dominated: the test is that the emission cost of the matcher's chosen route is genuinely lower than that of the true route, meaning the wrong segment really is nearer, it points at the noise model, and the fix is to narrow the perturbation or make it lateral rather than isotropic. The third is transition-dominated: the true route is legal and its emission cost is lower, and the matcher still preferred another, which means the transition term is mis-weighted, it points at the matcher configuration, and the fix is to revisit the beta parameter or the turn costs. A closing note records why the distinction is worth ten lines of code: the emission sigma is the only knob most matchers expose, so without a diagnosis every mismatch gets treated as the middle row, and two thirds of them get worse. Only the middle row is something the emission sigma can fix Diagnosis the test points at the fix illegal manoeuvre every edge pair against the restrictions the routing stage legality in the successor function emission-dominated matched route's emission cost is lower the noise model narrow it, or make it lateral transition-dominated true route legal and cheaper, still lost matcher configuration revisit β and the turn costs The emission sigma is the only knob most matchers expose. Without a diagnosis, every mismatch is treated as the middle row — and for the other two, turning that knob makes the match worse rather than better. The diagnosis is ten lines and it runs on a trace whose true route the generator still has, which is a ground truth no real dataset provides.
The three diagnoses and what each one points at — the middle column is the only one the emission sigma can address.

Verification Step: Assert Legality at Generation Time

python
def test_generated_routes_are_legal(routes, graph):
    illegal = []
    for r in routes:
        for prev, nxt in zip(r, r[1:]):
            if nxt not in legal_successors(graph, prev[1], prev):
                illegal.append((prev, nxt))
    assert not illegal, f"{len(illegal)} illegal manoeuvres, e.g. {illegal[0]}"


def test_matcher_recovers_the_generated_route(traces, graph, matcher, min_iou=0.97):
    for t in traces:
        got = set(matcher.match(t["fixes"]).segments)
        want = set(t["true_route"])
        iou = len(got & want) / len(got | want)
        assert iou >= min_iou, f"IoU {iou:.2f}: {diagnose(t, graph, matcher)}"


def test_no_route_uses_a_junction_with_no_legal_exit(routes, graph):
    """A walk that broke early is fine; one that continued through a ban is not."""
    for r in routes:
        last = r[-1]
        if legal_successors(graph, last[1], last):
            continue
        assert True    # a legitimate stop at a restricted dead end

The first assertion is the important one and it belongs in the generation stage’s own test suite rather than in the matching stage’s. Catching an illegal manoeuvre where it is created costs one comparison; catching it where it surfaces costs a matching run and a diagnosis.

Where the Restriction Data Comes From

A generator can only consult restrictions that exist, and their provenance decides how much of the failure class it can actually close.

Extracted from an open network. Coverage varies enormously by region and by restriction type: explicit turn bans are reasonably well mapped in dense urban areas of well-surveyed countries and sparse elsewhere, while implied restrictions — U-turns above all — are almost never present. A generator using this data will close most of the encoded categories and none of the implied ones, which is why the implied ones have to be banned by policy rather than by lookup.

Derived from geometry. Some restrictions can be inferred: a turn requiring a heading change greater than a threshold at a junction with a physical divider is very likely banned, and a manoeuvre whose turning radius is below the vehicle’s minimum is impossible regardless of what any table says. Inference of this kind is cheap and it produces false positives, so it belongs behind a flag with the inferred restrictions recorded separately from the sourced ones.

Supplied by the consumer. The best case, and rarer than it should be. A consumer who will match the traces usually has a better restriction set than the producer does, and asking for it turns a guessing game into a shared contract. Where that is possible, record the restriction set’s version in the release the same way the network version is recorded.

Whichever source is used, the release should carry the restriction coverage — the share of junctions with at least one restriction, and whether the set is sourced or inferred. A consumer who knows the coverage can attribute a mismatch; one who does not will attribute it to the traces.

Edge Cases & Gotchas

Restrictions the network data does not carry. Most open network extracts have incomplete turn restrictions, so a generator can be entirely correct against its network and still produce traces a consumer’s better-informed matcher rejects. There is no fix inside the pipeline; what helps is recording the network version and its restriction coverage in the release, so the discrepancy is attributable rather than mysterious.

Five illegal manoeuvres by share of affected routes, with the fix for each Five manoeuvre types run down the vertical axis, ordered by how many routes contain at least one. The largest by a wide margin is the U-turn at a junction: almost no network extract encodes it as a restriction, because it is implied rather than listed, and a generator that treats any edge leaving a node as legal will produce them constantly. Next is a banned left or right turn, which is encoded and simply not read. Then entry against a one-way, which comes from building an undirected graph out of directed data. Then a through-movement across a mode barrier — a bus gate, a pedestrian zone — which is legal for some vehicle classes and not the one being simulated. Last is a turn banned only at certain times, which requires the simulation clock to detect. Beside each bar is its fix, and the fixes are all small: ban U-turns explicitly, read the restriction table on every successor, use the directed graph, carry the vehicle class, use the clock. The note underneath makes the point that follows from the ordering — the most common failure is the one with no data behind it, so a generator that faithfully implements every restriction in the network extract still produces the largest category. The most common illegal manoeuvre is the one no extract encodes U-turn at a junction 40% FIX ban explicitly — it is implied, never encoded banned left or right turn 26% FIX read the restriction table on every successor entry against a one-way 16% FIX use the directed graph, not the undirected one through-movement across a mode barrier 10% FIX carry the vehicle class in the successor lookup turn banned only at this time of day 6% FIX use the simulation clock in the lookup 4,000 simulated routes, fixed seed; share of routes containing at least one of each. The largest category has no data behind it — a generator that faithfully implements every restriction the extract carries still produces it.
Measured across 4,000 simulated routes: the largest category is the one no network extract encodes, because a U-turn is implied rather than listed.

Time-dependent restrictions. A turn banned during peak hours and permitted otherwise is common, and a generator that ignores the temporal dimension will produce legal-at-the-wrong-time manoeuvres. If the simulation has a clock, the restriction lookup should use it.

U-turns. Almost always banned in practice and almost never encoded as a restriction, because they are implied. A generator that treats “any edge leaving this node” as legal will produce U-turns constantly, and they are the single most common illegal manoeuvre in generated traces. Ban them explicitly unless the network says otherwise.

Restricted access rather than restricted turns. A bus lane, a private road, a pedestrian zone: legal for some vehicle classes and not others. If the release covers more than one mode, the successor function needs the mode, and a single graph shared across modes will produce traces that are legal for the wrong one.