VehicleMapping HD AV Spatial Data

Choosing Between Centerline Methods for Intersection Geometry

The comparison in centerline algorithm selection establishes what each method costs and what it buys. What it does not do is decide, and a decision made by whoever is building the tile that day produces a map whose geometry quality varies by author.

This task replaces that with three measurements taken from the segment itself. Each is cheap, each is a useful diagnostic on its own, and together they determine the method without anybody needing an opinion.

The decision rule, with the measurement that drives each branch:

The Three-Measurement Decision Rule A decision tree branching on approach count, boundary correspondence and width variation, with a final smoothing branch on the curvature budget. approaches > 2? carriageways meeting inside correspondence? projections monotone width CV > 0.15? variation along the segment yesno yesno Voronoi medial axis — junction Voronoi — no usable pairing Voronoi — width varies midpoint averaging — sufficient then: if the curvature budget is tighter than 0.02 m, append the QP smoother

Prerequisites #

  • Python 3.10+, NumPy 1.24+, shapely 2.0+.
  • Input: the two boundaries of a segment, its extent, and the pipeline's curvature-continuity budget.
  • Upstream stage: boundary extraction; this runs before any centerline is generated.
  • Output: a method name and the three measurements, stored with the segment.

Step-by-Step #

1. Measure boundary correspondence #

python
import numpy as np
from shapely.geometry import LineString, Point

def has_correspondence(left: LineString, right: LineString) -> bool:
    """True when projecting left vertices onto the right boundary is monotone."""
    s = np.array([right.project(Point(p)) for p in left.coords])
    return bool(np.all(np.diff(s) >= -1e-9))

One backward jump is enough to disqualify midpoint averaging: it means two left vertices map to the same stretch of the right boundary, and the average of a pairing that does not exist is a centerline that folds. Expected output: a boolean, and in practice False at every junction and merge.

2. Measure width variation #

python
def width_cv(left: LineString, right: LineString, n: int = 50) -> float:
    """Coefficient of variation of width sampled along the segment."""
    w = np.array([right.distance(Point(left.interpolate(s, normalized=True)))
                  for s in np.linspace(0.0, 1.0, n)])
    return float(w.std() / max(w.mean(), 1e-6))

A constant-width carriageway returns close to 0; a lane with a taper or a lay-by returns above 0.15, which is the threshold at which midpoint averaging starts drifting toward the wider side.

3. Count approaches inside the extent #

python
def approach_count(segment_extent, carriageways) -> int:
    return sum(1 for c in carriageways if c.intersects(segment_extent))

More than two means a junction, and a junction disqualifies midpoint averaging regardless of what the other two measurements say — the paths through the interior are synthesised rather than extracted, as intersection and junction modeling sets out.

4. Apply the rule and record the decision #

python
from dataclasses import dataclass

@dataclass(frozen=True)
class Decision:
    method: str
    smooth: bool
    approaches: int
    correspondence: bool
    width_cv: float

def choose(left, right, extent, carriageways, curvature_budget_m: float) -> Decision:
    n = approach_count(extent, carriageways)
    corr = has_correspondence(left, right)
    cv = width_cv(left, right)
    method = "voronoi" if (n > 2 or not corr or cv > 0.15) else "midpoint"
    return Decision(method, curvature_budget_m < 0.02, n, corr, cv)

Recording the three measurements alongside the method is what makes the decision auditable later — and what turns a shift in the method mix between releases into a detectable signal about the boundary extractor rather than an unexplained change in the map.

What the method mix looks like across a real tile, and why a tile-wide choice is wasteful either way:

Method Mix Across One Urban Tile A proportional bar splitting 1840 segments into a large midpoint-sufficient group and three smaller groups that require the Voronoi axis, with the cost of a tile-wide choice stated. 1 490 midpoint-sufficient · 214 segments with varying width (CV > 0.15) · 98 segments with no monotone correspondence · 38 junctions 350 of 1 840 segments require the Voronoi axis tile-wide midpoint: 350 wrong centerlines including every junction in the tile tile-wide Voronoi: 1 490 needless solves roughly a hundredfold cost on those segments the three measurements cost microseconds each — cheaper than either mistake by orders of magnitude

Verification & Acceptance Criteria #

python
def assert_decisions(decisions, segments) -> None:
    assert len(decisions) == len(segments), "a segment has no recorded decision"
    for seg, d in zip(segments, decisions):
        if d.approaches > 2:
            assert d.method == "voronoi", f"{seg.id}: junction using midpoint"
        if d.method == "midpoint":
            assert d.correspondence and d.width_cv <= 0.15, \
                f"{seg.id}: midpoint chosen without the preconditions"
    mix = sum(1 for d in decisions if d.method == "voronoi") / len(decisions)
    assert 0.05 <= mix <= 0.60, f"method mix of {mix:.2f} is implausible"

Acceptance gate: every segment carries a decision with its three measurements; no junction using midpoint averaging; midpoint chosen only where both preconditions hold; and a method mix inside a plausible band, which is the check that catches a measurement returning a constant.

What each measurement costs, against what it prevents:

Cost of Each Measurement Against What It Prevents Three rows pairing a measurement with its cost and the specific defect it prevents. three measurements, all cheaper than one wrong choice correspondence one projection per vertex a few microseconds prevents a folded centreline width variation fifty distance queries tens of microseconds prevents drift to the wider side approach count one spatial query microseconds prevents midpoint at a junction together they cost roughly a thousandth of a single Voronoi solve, and they decide whether that solve is needed at all

Common Errors & Fixes #

Every segment chooses Voronoi. has_correspondence is returning False everywhere, usually because the two boundaries run in opposite directions. Orient both before projecting.

A junction chose midpoint averaging. The approach count is computed against the segment's own geometry rather than its extent, so intersecting carriageways were missed. Test against the extent polygon.

Width CV is enormous on a normal lane. The distance is being measured to the wrong boundary, or one boundary is a multi-part geometry. Merge parts before measuring.

The mix changes sharply between releases. The boundary extractor changed, not the roads. That is exactly the signal the recorded measurements exist to surface — compare the CV distribution rather than the method counts.

FAQ #

Why decide per segment rather than per tile? #

Because the property that decides the method is a property of the geometry, and a single tile routinely contains a motorway straight, a roundabout and a residential junction. A tile-wide choice either pays Voronoi and QP cost on thousands of straights that did not need it, or applies midpoint averaging at a junction where it produces a centerline off the road. Measuring per segment costs microseconds and the measurement is reusable as a diagnostic in its own right.

What is boundary correspondence and how is it measured? #

It is whether each vertex on one boundary has a well-defined partner on the other, which is what midpoint averaging assumes. Measure it by projecting each left vertex onto the right boundary and checking the resulting stations are monotone increasing: if the projections jump backwards, the pairing is ill-defined and averaging will produce a centerline that folds. A single non-monotone run is enough to disqualify the method.

Should the chosen method be recorded with the segment? #

Yes, along with the three measurements that produced it. When a lane's geometry is questioned later, the first useful fact is how it was generated, and the second is why that method was chosen. Recording the measurements also makes the decision rule auditable across a release: a sudden shift in the method mix between two releases is a signal that boundary extraction changed, not that the roads did.

Up one level: Centerline Algorithm Selection — the decision stage this procedure implements.