VehicleMapping HD AV Spatial Data

Reviewing HD Map Changes with Geometry-Aware Diffs

The delta machinery in HD map version control tells you that a feature changed — that is what the digest comparison in computing content-addressed map tile deltas is for. What it cannot tell you is whether the change matters. A reviewer handed a list of four hundred changed digests will approve them all; a reviewer handed six ranked findings will actually look.

This task turns the digest diff into a review artefact: a classification of what kind of change each feature underwent, a measurement of each kind, a ranking by safety consequence, and a rendering that makes a sub-metre shift visible.

The four change kinds, and why they cannot share a single threshold:

Four Kinds of Map Change and What Each Needs Measured Four small panels showing lateral shift, extension, topology change and attribute change on the same lane, each annotated with its measurement. 0.35 m +12 m new successor 50 → 30 geometry identical lateral shift extension topology attribute measure: max normal offset measure: length delta measure: edge set delta measure: key-by-key the topology panel has no distance to threshold, which is why it is ranked first rather than scored and why a single "how much did it change" number cannot order a review queue

Prerequisites #

  • Python 3.10+, NumPy 1.24+, shapely 2.0+, networkx 3.x.
  • Input: two map versions and the digest diff naming the changed feature set.
  • Upstream stage: the content-addressed delta; this consumes its modify list.
  • Output: a ranked review queue with a rendering per finding.

Step-by-Step #

1. Classify each changed feature #

python
from shapely.geometry import LineString

def classify_change(before: LineString, after: LineString,
                    attrs_before: dict, attrs_after: dict,
                    edges_before: set, edges_after: set,
                    move_tol: float = 0.02) -> set[str]:
    kinds = set()
    if edges_before != edges_after:
        kinds.add("topology")
    if attrs_before != attrs_after:
        kinds.add("attribute")
    if abs(after.length - before.length) > move_tol:
        kinds.add("extension")
    n = min(len(before.coords), len(after.coords))
    if n and max(before.interpolate(i / n, normalized=True)
                 .distance(after.interpolate(i / n, normalized=True))
                 for i in range(n)) > move_tol:
        kinds.add("lateral")
    return kinds or {"reencode"}

A feature can be in several classes at once, and reencode — a digest change with no measurable difference — is the class that should be filtered out of review entirely. Expected output: a set of change kinds per feature.

2. Rank by consequence, not by magnitude #

python
RANK = {"topology": 0, "lateral": 1, "attribute": 2, "extension": 3, "reencode": 9}

def review_key(finding) -> tuple:
    kind = min(finding.kinds, key=lambda k: RANK[k])
    crosses_boundary = finding.lateral_m > 0.5 * finding.lane_width_m
    return (RANK[kind], not crosses_boundary, -finding.lateral_m)

The middle term promotes any lateral shift big enough to cross into a neighbouring lane above every other lateral shift, regardless of absolute size: 0.4 m on a 3.0 m lane matters more than 0.8 m on a 7 m one.

3. Render before and after in one frame #

python
def render_finding(before, after, out_path, pad_m: float = 8.0) -> None:
    """One frame, both versions, displacement annotated at its widest point."""
    xs = [*before.xy[0], *after.xy[0]]
    ys = [*before.xy[1], *after.xy[1]]
    view = (min(xs) - pad_m, min(ys) - pad_m, max(xs) + pad_m, max(ys) + pad_m)
    draw_polyline(out_path, before, style="dashed", label="before", view=view)
    draw_polyline(out_path, after, style="solid", label="after", view=view)
    annotate_widest_separation(out_path, before, after)

Key parameter: pad_m is small deliberately. A frame padded to the whole tile renders a 0.35 m shift as two coincident lines; padding to the change plus a few metres is what makes the shift legible. Dashed against solid rather than two colours keeps the record readable in print and for colour-blind reviewers.

One consequence worth stating explicitly: the ranking is a claim about safety, so it belongs in version control next to the criteria it encodes rather than in whoever's notebook produced the queue. A team that reorders RANK because a release was noisy has changed what its reviewers see, and that change should be as reviewable as any threshold in the release gate. The same applies to the boundary-crossing test — the fraction of lane width at which a lateral shift is promoted is a tuned number, and tuning it quietly is how a queue slowly stops surfacing the findings it was built for.

What one release looks like once the queue is ranked, and what a byte diff would have shown instead:

One Release: Byte Diff Against a Ranked Review Queue Four rows reducing a raw byte diff to a ranked review queue, with the count at each stage. the same release, seen two ways byte diff what the storage layer sees 4 100 changed features · 180 MB unreviewable re-encode filtered canonicalized geometry compared 3 940 removed as no semantic change 160 left classified by what actually moved 118 attribute · 38 lateral · 4 topology 160 classified ranked queue topology first, then boundary-crossing shifts 4 topology + 6 shifts across a lane boundary 10 entries the reviewer sees ten items rather than four thousand, and the ten are the ones that change where a vehicle can go

Verification & Acceptance Criteria #

python
def assert_review_queue(queue, diff) -> None:
    assert all("reencode" not in f.kinds for f in queue), "noise reached review"
    kinds = [min(f.kinds, key=lambda k: RANK[k]) for f in queue]
    assert kinds == sorted(kinds, key=lambda k: RANK[k]), "queue is not ranked"
    covered = {f.feature_id for f in queue} | diff.reencode_only
    assert covered == diff.modified, "a modified feature is neither queued nor filtered"

Acceptance gate: zero re-encode-only findings in the queue; the queue ordered by consequence class; and every modified feature either queued or explicitly classified as re-encode — a feature that is silently in neither is the failure this assertion exists to catch.

The rendering decisions that decide whether a 0.35 m shift is visible at all:

Rendering Choices and Whether a Sub-Metre Shift Reads Four rows pairing a rendering choice with whether a sub-metre displacement is visible in it. the same 0.35 m lateral shift, rendered four ways frame padded to the tile the default extent two coincident lines invisible side-by-side panels two images, one each the reader registers them mentally invisible below ~1 m blinking overlay alternating frames unreadable at a glance, unprintable not a record one frame, fitted, dashed vs solid extent = change + a few metres displacement annotated at its widest legible, printable colour alone is not enough either — dashed against solid survives a colour-blind reviewer and a monochrome print

Common Errors & Fixes #

The queue has four hundred entries and nobody reads it. Re-encodes are not being filtered, usually because the comparison runs on raw serialized bytes rather than on canonicalized geometry. Canonicalize before diffing.

A topology change was approved without being noticed. It was ranked by displacement, and a new connection has none. Rank topology first, unconditionally.

Two versions look identical in the rendering. The frame is padded to the tile. Fit the view to the change.

A lane that moved 0.1 m is flagged and one that moved 0.4 m is not. move_tol is being applied to a resampled comparison where vertex counts differ. Compare at normalized stations, as in step 1, rather than vertex to vertex.

FAQ #

Why is a byte-level diff useless for map review? #

Because the size of a change tells you nothing about its consequence. A re-encoded but geometrically identical tile produces megabytes of diff and zero risk; a single vertex moved 0.4 metres across a lane boundary produces a few bytes and can put a vehicle in the wrong lane. Review has to be ordered by what the change means, and only a diff that understands geometry and topology can compute that.

What ranks highest in a review queue? #

Topology changes first — an added or removed connection changes where a vehicle can go, and no displacement threshold captures that. Then lateral displacements large enough to cross a lane boundary, then changes to regulatory attributes such as speed or turn restrictions, then everything else. Ranking by magnitude alone puts a 2 metre extension of a lane end above a 0.3 metre lateral shift at a junction, which is exactly backwards.

How should the before and after be rendered? #

In one frame, at a scale where the displacement is visible, with the two versions distinguishable without colour alone and the measured displacement written next to the widest separation. Side-by-side panels force the reviewer to do the registration mentally and hide sub-metre shifts entirely; a blinking overlay is worse, because it cannot be read at a glance or in a printed review record.

Up one level: HD Map Version Control — the versioning stage this review belongs to.