VehicleMapping HD AV Spatial Data

Benchmarking Voronoi vs QP Centerlines on Intersections

The centerline algorithm selection guide says use Voronoi at junctions and add a quadratic-program smoother when curvature continuity is required — but "when" needs numbers, not intuition. This task runs a reproducible head-to-head on real intersection polygons, scoring lateral error, curvature continuity, and per-junction compute, so the QP stage is applied exactly where it earns its cost and skipped where the raw medial axis already suffices. Both methods are implemented in centerline generation algorithms.

Each intersection runs through both methods and is scored on three metrics against surveyed control points:

Voronoi vs QP Centerline Benchmark Intersection corpus box feeds two method boxes, Voronoi and QP smoother. Each produces a scored result on lateral RMSE, curvature jump, and compute. A decision box compares them and outputs a complexity threshold. Intersection corpus + control pts Voronoi medial axis raw skeleton QP smoother from Voronoi init Score 3 metrics RMSE · κ-jump · time Threshold use QP above

Prerequisites #

  • Python 3.10+, NumPy 1.24+, SciPy 1.11+ (spatial.Voronoi, sparse, optimize), Shapely 2.0+, and a QP solver (scipy.sparse.linalg or osqp).
  • Input: a corpus of intersection polygons, each with surveyed centerline control points as ground truth, in one projected CRS.
  • Upstream stage: boundary polygons from extracting lane boundaries from point cloud data; control points from survey.
  • Output: a per-junction table of lateral RMSE, curvature jump, and compute for each method, plus the derived complexity threshold.

Step-by-Step #

1. Score a single centerline against control points #

Define one scoring function both methods use, so the comparison is apples-to-apples.

python
import numpy as np
from scipy.spatial import cKDTree

def score(centerline: np.ndarray, control: np.ndarray, kappa: np.ndarray) -> dict:
    d, _ = cKDTree(control).query(centerline)
    return {
        "rmse": float(np.sqrt(np.mean(d ** 2))),
        "kappa_jump": float(np.abs(np.diff(kappa)).max()),
    }

Key parameters: rmse is lateral fit against ground truth; kappa_jump is the worst adjacent-vertex curvature step, the continuity metric QP targets.

2. Time each method per junction #

Wrap both generators with a consistent timer so compute is measured the same way. Use a fixed sampling resolution for both.

python
import time

def benchmark_junction(polygon, control, voronoi_fn, qp_fn) -> dict:
    t0 = time.perf_counter()
    v_line, v_kappa = voronoi_fn(polygon)
    t1 = time.perf_counter()
    q_line, q_kappa = qp_fn(v_line)          # QP initialized from Voronoi
    t2 = time.perf_counter()
    return {
        "voronoi": {**score(v_line, control, v_kappa), "ms": (t1 - t0) * 1e3},
        "qp":      {**score(q_line, control, q_kappa), "ms": (t2 - t1) * 1e3},
    }

Key parameter: the QP timer measures only the smoothing step, isolating its marginal cost over the Voronoi baseline.

3. Aggregate and find the threshold #

Run the corpus, then find the junction complexity (branch count) above which QP's curvature win justifies its cost.

python
def aggregate(results, kappa_budget=0.02):
    rows = []
    for r in results:
        needs_qp = r["voronoi"]["kappa_jump"] > kappa_budget
        rows.append({"branches": r["branches"], "needs_qp": needs_qp,
                     "qp_ms": r["qp"]["ms"]})
    # threshold = smallest branch count where most junctions need QP
    return rows

Key parameter: kappa_budget (0.02 m⁻¹) is the continuity bound; a junction whose raw Voronoi exceeds it is one where QP is required.

Verification & Acceptance Criteria #

The benchmark itself must be trustworthy before its conclusion is.

python
def assert_benchmark_valid(results):
    for r in results:
        # both methods scored on the same control set and resolution
        assert r["voronoi"]["rmse"] < 0.2 and r["qp"]["rmse"] < 0.2, "method diverged"
        # QP must not worsen lateral fit beyond a small deviation cost
        assert r["qp"]["rmse"] <= r["voronoi"]["rmse"] + 0.03, "QP over-smoothed"
        # QP must improve or match curvature continuity
        assert r["qp"]["kappa_jump"] <= r["voronoi"]["kappa_jump"] + 1e-6, "QP no help"
    print("benchmark valid: both methods within budget, QP behaves as expected")

Acceptance gate: both methods keep lateral RMSE ≤0.1 m on simple junctions; QP never worsens RMSE by more than the deviation-cost margin; QP never increases the curvature jump. A run where QP worsens both metrics means its smoothness weight is mis-tuned — the benchmark, not the method, is at fault.

Common Errors & Fixes #

QP appears strictly worse on every metric. The smoothness weight is too high, pulling the line off geometry without a curvature payoff. Lower the weight until the deviation term keeps RMSE within budget, per the centerline algorithm selection guidance.

Compute times are noisy and unrepeatable. Warm-up and GC jitter dominate on tiny junctions. Run each junction several times and report the median, and disable the QP solver's verbose mode.

Voronoi RMSE spikes on some junctions. Spurious medial-axis branches were included in the scored centerline. Prune short branches before scoring so the comparison reflects the intended centerline.

Threshold shifts between corpus samples. The corpus is too small or unbalanced by junction type. Stratify the corpus across branch counts and report the threshold with a confidence interval, not a single number.

FAQ #

What makes a fair benchmark between the two methods? #

Both methods must run on the identical input — the same intersection polygon sampled at the same resolution — and be scored against the same surveyed control points. The QP method is initialized from the Voronoi skeleton, so the comparison is really Voronoi-only versus Voronoi-plus-QP-smoothing, which isolates exactly what the smoother adds. Fixing the random elements, such as any sampling seed, keeps the benchmark reproducible run to run.

Which metrics decide the winner? #

Three: lateral RMSE against control points, the maximum curvature jump between adjacent vertices, and wall-clock per junction. Voronoi usually ties or wins on lateral RMSE because it follows the medial axis exactly, while QP wins decisively on curvature continuity because that is what it optimizes. Compute is where QP pays — it solves a sparse program per junction. The decision is whether the curvature improvement justifies that cost for a given junction.

When does the QP smoother stop being worth it? #

On simple junctions where the raw Voronoi skeleton is already smooth, the QP stage adds compute for a curvature improvement the planner cannot feel. The benchmark typically shows a complexity threshold — a number of branches or a curvature-jump level — below which Voronoi alone meets the continuity budget. Above it, the raw skeleton has kinks the planner rejects and QP becomes necessary. Applying QP only above that threshold keeps average per-junction cost low.

Up one level: Choosing a Centerline Extraction Algorithm: Midpoint, Voronoi & QP — the parent decision guide this benchmark quantifies.