Measuring Map Matching Accuracy with Hausdorff and F1

The validation topic argues that map matching needs several metrics because there are several independent ways to be wrong. This page is the implementation: four metrics, what each one sees, and the ways each can be quietly misleading.

All four assume a matched output and a ground truth expressed the same way — an ordered sequence of directed edge identifiers, plus the geometry those edges resolve to. Comparing internal engine edge IDs is a trap covered at the end.

Compatibility and Configuration Requirements

The Metrics

from __future__ import annotations

import numpy as np
import shapely
from shapely.geometry import LineString


def hausdorff(matched: LineString, truth: LineString, densify: float = 0.05) -> float:
    """Symmetric Hausdorff distance in metres. A worst-case measure."""
    return max(
        shapely.hausdorff_distance(matched, truth, densify=densify),
        shapely.hausdorff_distance(truth, matched, densify=densify),
    )


def directed_percentile(matched: LineString, truth: LineString, q: float = 95.0, step_m: float = 5.0) -> float:
    """Distance from truth to the matched path at the q-th percentile of sample points."""
    n = max(int(truth.length // step_m), 2)
    pts = [truth.interpolate(d) for d in np.linspace(0, truth.length, n)]
    d = np.array([matched.distance(p) for p in pts])
    return float(np.percentile(d, q))


def edge_scores(matched: list[tuple[int, int]], truth: list[tuple[int, int]],
                lengths: dict[tuple[int, int], float]) -> dict[str, float]:
    """Length-weighted precision, recall, F1 and correct-edge rate over directed edges."""
    m, t = set(matched), set(truth)
    inter_len = sum(lengths[e] for e in (m & t))
    m_len = sum(lengths[e] for e in m) or 1.0
    t_len = sum(lengths[e] for e in t) or 1.0
    precision = inter_len / m_len
    recall = inter_len / t_len
    f1 = 0.0 if precision + recall == 0 else 2 * precision * recall / (precision + recall)
    return {"precision": precision, "recall": recall, "f1": f1, "correct_edge_rate": recall}


def temporal_error(matched_offsets: np.ndarray, truth_offsets: np.ndarray,
                   speeds_mps: np.ndarray) -> dict[str, float]:
    """Along-path offset error converted to seconds using the local speed."""
    delta_m = np.abs(matched_offsets - truth_offsets)
    seconds = delta_m / np.clip(speeds_mps, 0.5, None)
    return {"median_s": float(np.median(seconds)), "p95_s": float(np.percentile(seconds, 95))}

Two implementation details are worth stating. hausdorff_distance without the densify argument compares only the vertices, so two paths that agree at every vertex and diverge between them score zero — which is exactly what happens when the matched path uses a simplified geometry. And edge_scores uses directed edges: an edge traversed the wrong way is a different element, which is what makes the metric able to see a reversal at all.

Execution and Tuning Guidelines

Weight edge scores by length, always. An urban trace crosses dozens of tiny junction links, and counting edges makes the metric mostly about those. Weighting by length makes it about driving.

Report precision and recall separately as well as F1. They fail differently and the difference is diagnostic: low recall with high precision means the matcher is dropping segments, usually at gaps; low precision with high recall means it is adding segments, usually detours through parallel roads.

Convert temporal error to seconds, not metres. An along-path offset of eighty metres is trivial on a motorway and enormous in a depot yard. Dividing by the local speed makes the number comparable across the fleet, which is the only way an aggregate is meaningful.

Clip the speed divisor. The np.clip(speeds_mps, 0.5, None) above prevents a stationary period from producing an infinite temporal error. Without it, one stop makes the whole trace’s p95 useless.

Comparing Across Engines

Every engine has its own internal edge identifiers, and they change between builds of the same engine. Comparing on them measures the identifier scheme.

Resolve both sides to OSM way id plus a direction flag before scoring. Every engine can emit the source way for a matched edge, and direction comes from whether the traversal runs with or against the way’s node order. A small resolution layer per engine costs an afternoon and makes every subsequent comparison meaningful.

def normalise(edges: list[dict]) -> list[tuple[int, int]]:
    """(osm_way_id, +1 forward / -1 reverse) — comparable across engines and builds."""
    return [(e["osm_way_id"], 1 if e["forward"] else -1) for e in edges]

One caveat: a single OSM way often carries several engine edges, because engines split ways at junctions. Normalising collapses those, which slightly coarsens the metric — a matcher that takes the right way but the wrong half of it scores as correct. For fleet work that is usually acceptable, and where it is not, keep the split point in the key as well.

Common Pitfalls Specific to This Technique

Computing Hausdorff on the simplified display geometry. The simplified line is a few metres from the real one by construction, so the metric measures the simplification. Always score against the analytical geometry, per Douglas-Peucker simplification.

Scoring undirected edges and then wondering why reversals are invisible. Direction has to be in the key. It is one extra field and it is the only thing that makes a whole class of failure visible.

Averaging per-trace metrics without weighting. A fleet average over traces treats a four-kilometre delivery and a four-hundred-kilometre trunk run equally. Weight by distance when aggregating, or report the distribution rather than the mean.

Aggregating Across a Corpus

Per-trace metrics have to be combined before they mean anything at fleet scale, and the combination rule changes the answer more than most people expect.

Weight by distance, not by trace. A corpus containing four-kilometre delivery rounds and four-hundred-kilometre trunk runs will, under an unweighted mean, be dominated by the short traces simply because there are more of them. Weighting by matched distance gives a figure that means “the share of driving attributed to the right road”, which is what a consumer of the number assumes it already means.

def aggregate(rows: list[dict]) -> dict[str, float]:
    """Distance-weighted aggregate of per-trace metrics."""
    total = sum(r["truth_length_m"] for r in rows) or 1.0
    return {
        "correct_edge_rate": sum(r["correct_edge_rate"] * r["truth_length_m"] for r in rows) / total,
        "hausdorff_p95_m": float(np.percentile([r["hausdorff_m"] for r in rows], 95)),
        "temporal_p95_s": float(np.percentile([r["temporal_p95_s"] for r in rows], 95)),
        "traces": len(rows),
        "distance_km": total / 1000,
    }

Aggregate distances as percentiles, not as means. Hausdorff and temporal error both have long right tails, so a mean is pulled around by a handful of traces and moves noisily between runs. The 95th percentile is stable and answers a more useful question — how bad is it for the worst one trace in twenty.

Report the corpus size alongside every figure. A stratum of thirty traces has a standard error of several points, and a number quoted without its denominator invites comparisons it cannot support.

Confidence intervals, briefly

For a distance-weighted rate, a bootstrap over traces is the least troublesome way to get an interval: resample traces with replacement a thousand times, recompute the weighted rate, and take the 2.5th and 97.5th percentiles. It handles the weighting and the correlation within a trace without any distributional assumption, and it runs in under a second on a few hundred traces.

The interval matters most when comparing two configurations. A difference of half a point between configurations whose intervals are ±1.2 points is not a difference, and reporting it as one is how a team ends up chasing noise for a sprint.

Related

• Map matching accuracy validation and benchmarking — parent topic and the metric-selection argument
• Building a ground-truth set for map-matching evaluation — where the labels come from
• Regression testing a map matcher in CI — turning these numbers into a gate
• Choosing a map matching algorithm — the decision these metrics inform
• Trajectory Analysis & Map Matching Techniques — parent section