VehicleMapping HD AV Spatial Data

Merging Concurrent HD Map Edits Without Conflicts

When two survey crews edit the same tile in parallel — one re-mapping a rebuilt junction, another adding a new bike lane — a last-writer-wins policy silently throws one crew's work away. Within HD map version control, the fix is a deterministic three-way merge over content-addressed tiles: diff each branch against the snapshot they both forked from, auto-apply the changes that do not touch each other, and stop at a conflict gate for the ones that do. This task builds that merge on top of the digests produced by computing content-addressed map tile deltas, so no lane is ever lost without a human seeing it.

A three-way merge classifies each feature against the common ancestor and gates on conflicts:

Three-Way Merge of Concurrent HD Map Edits Ancestor tile at top centre. Two boxes below it, ours on the left and theirs on the right, each connected to the ancestor. Both feed a merge node in the middle. The merge node outputs to a diamond conflict gate. Pass leads to a merged tile terminal; fail leads to a human-review box that loops back to the merge. Common ancestor base snapshot Ours: diff vs base add / modify / delete Theirs: diff vs base add / modify / delete Merge + classify auto-apply · flag overlap conflicts resolved? pass → merged tile · fail → human review, then re-merge

Prerequisites #

  • Python 3.10+, Shapely 2.0+ (STRtree spatial index), NumPy 1.24+.
  • Input: three tile snapshots — base (common ancestor), ours, theirs — each a mapping of feature id → feature, all in one projected CRS.
  • Upstream stage: feature digests and the version DAG come from the content-addressed store; features carry stable ids and geometry in the committed CRS.
  • Output: a merged tile plus a conflict list; an empty conflict list means the merge auto-completed and passed topology validation.

Step-by-Step #

1. Classify each feature against the ancestor #

For every feature id touched by either branch, decide the merged state. Non-overlapping changes apply automatically; a feature changed on both sides is a structural conflict.

python
def classify(base, ours, theirs):
    """Return (merged, conflicts) from three {id: digest-or-None} maps.
    None means the feature is absent (deleted) on that side."""
    merged, conflicts = dict(base), []
    ids = set(base) | set(ours) | set(theirs)
    for fid in sorted(ids):                     # sorted => deterministic
        b, o, t = base.get(fid), ours.get(fid), theirs.get(fid)
        if o == t:                              # both agree (incl. both deleted)
            _set(merged, fid, o)
        elif o == b:                            # only theirs changed
            _set(merged, fid, t)
        elif t == b:                            # only ours changed
            _set(merged, fid, o)
        else:                                   # changed on both sides
            conflicts.append((fid, "structural", o, t))
    return merged, conflicts

def _set(d, fid, digest):
    if digest is None:
        d.pop(fid, None)
    else:
        d[fid] = digest

Key parameter: processing ids in sorted order makes the merge a pure function of its three inputs. Expected output: a merged digest map and a list of structural conflicts.

2. Detect geometric overlap conflicts #

Two independently added lanes can share the same physical space even with distinct ids. Build a spatial index over the merged geometry and flag pairs that overlap within the positional tolerance.

python
from shapely.strtree import STRtree

def geometric_conflicts(features: dict, tol_m: float = 0.15):
    """Flag pairs of features whose buffered footprints overlap."""
    items = list(features.items())
    geoms = [g.buffer(tol_m / 2) for _, g in items]
    tree = STRtree(geoms)
    conflicts = []
    for i, gi in enumerate(geoms):
        for j in tree.query(gi):
            if j > i and gi.intersects(geoms[j]):
                conflicts.append((items[i][0], items[j][0], "geometric"))
    return conflicts

Key parameters: tol_m is the positional tolerance; buffering by half the tolerance each makes two features within tol_m intersect. The STRtree keeps this near-linear instead of O(n²).

3. Resolve and re-validate #

Apply human resolutions (choose ours, theirs, or an edited feature) and re-run topology validation on the merged tile before it can be committed.

python
def resolve(merged, resolutions):
    for fid, chosen_digest in resolutions.items():
        _set(merged, fid, chosen_digest)
    return merged

Verification & Acceptance Criteria #

The merge is accepted only when it is conflict-free and topologically sound.

python
def assert_merge_ok(conflicts, merged_tile):
    assert not conflicts, f"{len(conflicts)} unresolved conflict(s)"
    # topology validation shares the connectivity checks used site-wide
    assert validate_topology(merged_tile), "merged tile fails topology gate"
    print("merge accepted: no conflicts, topology valid")

Acceptance gate: zero unresolved structural or geometric conflicts; the merged tile passes the connectivity checks from topological validation rules; and re-running the merge on the same three inputs reproduces the identical merged root digest.

Common Errors & Fixes #

A lane silently disappears after merge. Last-writer-wins logic slipped in — a delete on one branch was applied over a modify on the other without flagging. Ensure classify raises a structural conflict whenever o != b and t != b and o != t, including the delete-vs-modify case.

Merge result differs between runs. Iteration order is non-deterministic. Sort feature ids before classifying and never merge from an unordered set.

Two valid new lanes flagged as a false conflict. The overlap tolerance is too large, so adjacent lanes buffer into each other. Set tol_m to the positional tolerance, not the lane width, and buffer by half of it.

Merged tile fails topology validation on a connection edited by neither branch. A predecessor/successor link referenced a feature deleted on one branch. Validate that every retained connection's endpoints still exist post-merge, the same invariant enforced when building lane successor graphs from OpenDRIVE.

FAQ #

Why not just take the most recent edit? #

Last-writer-wins silently discards the other team's work. If one crew re-surveyed a junction while another added a bike lane in the same tile, taking the newest snapshot drops one of those changes with no record. A three-way merge against the common ancestor keeps both non-overlapping edits and surfaces only the genuine conflicts for human review, which is the difference between a merge and an overwrite.

What counts as a conflict for map features? #

Two kinds. A structural conflict is the same feature id modified or deleted on both branches. A geometric conflict is two independently added or moved features whose footprints now overlap within the positional tolerance, for example two centerlines occupying the same lane. Structural conflicts are cheap to detect from the digest diff; geometric conflicts need a spatial index over the merged feature set.

How do I keep the merge deterministic? #

Operate entirely on content-addressed digests and process feature ids in sorted order, so the same three inputs always yield the same merged tile and the same conflict list regardless of machine or thread scheduling. Determinism is what lets the merge be replayed in CI and audited: the merged root digest is a pure function of the base, ours, and theirs.

Up one level: HD Map Version Control — the parent workflow covering branching, snapshots, and rollback that this concurrent-merge step plugs into.