Choosing a Centerline Extraction Algorithm: Midpoint, Voronoi & QP

Centerline extraction looks trivial until the road stops being two parallel lines — at merges, forks, and intersections the naive midpoint average is simply undefined, and a pipeline that hard-codes one method ships broken geometry through every junction. This decision guide sits inside the lane geometry extraction and road network processing domain and frames the choice between the three methods that matter in production: midpoint averaging, the Voronoi medial axis, and a quadratic-program (QP) smoother. The selection is driven by road topology and a hard ≤0.1 m lateral-error budget, not preference. The concrete implementations live in centerline generation algorithms; this page decides which one to reach for.

The centerline method follows from road topology and the smoothness budget:

Algorithm Overview #

The three methods differ in what geometry they can handle, their compute cost, and the guarantees they give:

Midpoint is the default only for simple lane segments. The moment the drivable area branches, midpoint is not merely inaccurate but undefined, and the Voronoi medial axis becomes the correct primitive. The QP smoother is orthogonal: it is a refinement stage layered on top of either initialization when the planner demands curvature continuity.

Decision Criteria #

Criterion 1 — Road topology gates the method #

The first, non-negotiable filter is topology. A segment with two boundaries and matching vertex counts admits midpoint; a junction polygon with three or more openings does not. Classify the segment before choosing:

import numpy as np

def is_simple_lane(left: np.ndarray, right: np.ndarray, ratio_tol=0.15) -> bool:
    """Two roughly parallel boundaries with comparable vertex counts."""
    n_l, n_r = len(left), len(right)
    if abs(n_l - n_r) / max(n_l, n_r) > ratio_tol:
        return False                      # unequal sampling -> not 1:1
    # parallelism: mean boundary-to-boundary width should be near-constant
    widths = np.linalg.norm(left[:min(n_l, n_r)] - right[:min(n_l, n_r)], axis=1)
    return widths.std() / widths.mean() < 0.25

Key parameters: ratio_tol guards against mismatched vertex counts; the width coefficient of variation flags a segment whose boundaries diverge (an on-ramp), which pushes it to the Voronoi path. A False here means midpoint is off the table.

Criterion 2 — The smoothness budget gates the QP stage #

If the planner consumes curvature directly — for trajectory generation or comfort constraints — a raw skeleton with vertex-level kinks is unusable. Measure the curvature of the candidate centerline (see calculating road curvature with Python Shapely) and, if it exceeds the continuity bound, add the QP smoothing stage.

def needs_qp(kappa: np.ndarray, jump_bound: float = 0.02) -> bool:
    """True if successive-vertex curvature jumps exceed the bound (1/m)."""
    return bool(np.abs(np.diff(kappa)).max() > jump_bound)

Key parameter: jump_bound is the maximum tolerable curvature step between adjacent vertices; exceeding it triggers QP smoothing regardless of which method produced the initial centerline.

Criterion 3 — Compute budget at tile scale #

Voronoi and QP both cost more than midpoint. At metropolitan scale, apply them selectively: midpoint for the ~90% of segments that are simple lanes, Voronoi only for junction polygons, and QP only where the curvature gate fires. This keeps the average per-tile cost near midpoint while paying for the harder methods only where topology or the smoothness budget forces it.

The decision as a tree, with the two questions that actually branch it. Everything else is tuning inside a chosen method:

Validation & QC Automation #

Whatever method is chosen, validate the output the same way. Enforce these thresholds:

• Lateral error ≤0.1 m RMSE against surveyed centerline control points, ≤0.05 m for simple lanes.
• Containment: every centerline vertex lies inside the drivable polygon (no excursion outside the boundaries).
• Curvature continuity: post-QP, adjacent-vertex curvature jump ≤0.02 m⁻¹.
• Branch completeness at junctions: the Voronoi skeleton reaches every entry/exit opening.

def validate_centerline(centerline, polygon, control_pts, tol=0.1):
    inside = all(polygon.contains_point(p) for p in centerline)
    rmse = _rmse_to_control(centerline, control_pts)
    assert inside, "centerline leaves the drivable polygon"
    assert rmse <= tol, f"lateral RMSE {rmse:.3f} m > {tol}"

And the number that decides the third criterion. The QP stage buys a real accuracy gain at intersections and almost nothing on a straight, while costing the same either way:

Edge Cases & Failure Patterns #

• Midpoint applied at a merge. Unequal vertex counts silently pair the wrong points, producing a centerline that cuts across the gore. The topology filter must reject these before midpoint runs.
• Voronoi spurious branches. Boundary noise spawns short medial-axis spurs into corners. Prune branches shorter than a length threshold and below a clearance radius before accepting the skeleton.
• QP over-smoothing. Too high a smoothness weight pulls the centerline off true geometry, breaching the lateral-error budget. Tune the weight so the deviation term keeps RMSE ≤0.1 m.
• Mixed methods at segment joins. A midpoint lane meeting a Voronoi junction can leave a small position discontinuity at the hand-off. Blend the last few metres so the joined centerline is continuous.

Performance & Scale Notes #

Classify segments first and route each to the cheapest valid method — this is the single biggest lever, since most segments are simple lanes that never need Voronoi or QP. Compute Voronoi diagrams on decimated boundary samples (a 0.2 m step is plenty) to keep the diagram small, and solve the QP as a sparse banded system rather than a dense one. Both stages parallelize per segment; distribute them with the same worker pattern as batch lane-attribute extraction, bounding each worker's RAM so a dense downtown tile does not OOM the pool.

Keeping the benchmark fair #

The numbers above are only meaningful if the two arms were compared honestly, and three controls decide that — each of which, left free, flatters one method.

The first is the boundary input: vectorize once and feed both arms from the same artefact. Re-running the boundary extraction per method smuggles a different input into one arm, so the comparison measures vectorizers rather than axes. The second is the control-point set: score both arms on the same surveyed points at the same stations, because nearest-point scoring reports a distance either way and quietly lets each method pick the stations it happens to fit. The third is resampling: bring both outputs to the same station spacing before scoring, since a denser polyline scores better on nearest-point error for free — and the smoothed output is normally the denser one, so this control is the one that flatters the smoother.

What the smoother is worth, by segment class #

The third criterion above is a compute-budget question, and it has a measured answer that varies more by segment class than most teams expect. On a straight carriageway, midpoint averaging alone reaches about 0.030 m lateral error against surveyed control, and adding the quadratic-program smoother reaches 0.028 m — a gain that does not repay a roughly hundredfold cost increase on the segment. On a curved carriageway the base method reaches 0.060 m, which fails a 0.05 m gate, and the smoother brings it to 0.035 m, which passes. At a four-way junction the Voronoi axis alone reaches 0.090 m and the smoother brings it to 0.041 m.

So the smoother is close to worthless on straights, decisive on curves, and mandatory at junctions — and a single global decision to run it or not is wrong in two of those three cases. The threshold that matters turns out to be the junction's approach count rather than any geometric magnitude: below about five approach legs the two methods are indistinguishable inside the measurement noise, and above it the gap opens and stays open. That is why the decision rule branches on approach count rather than on a curvature or error threshold, and why the benchmark that produced the number reports convergence and accuracy separately rather than as one figure.

Deciding per segment, from measurements rather than opinion #

The criteria above describe what each method costs and buys. Turning that into a decision needs three numbers taken from the segment itself, and the reason to measure rather than to choose is that a single urban tile routinely contains a motorway straight, a roundabout and a residential junction — so any tile-wide choice is wrong somewhere.

Boundary correspondence is whether the two boundaries admit a monotone one-to-one pairing, which is exactly what midpoint averaging assumes. Project each left vertex onto the right boundary and check the resulting stations increase; a single backward jump means two left vertices map to the same stretch of the right boundary, the pairing does not exist, and averaging it produces a centreline that folds. This is False at essentially every junction and merge.

Width variation is the coefficient of variation of width sampled along the segment. A constant-width carriageway returns near zero; a lane with a taper or a lay-by returns above 0.15, which is roughly where midpoint averaging begins drifting toward the wider side.

Approach count is how many carriageways meet inside the segment's extent. More than two means a junction, and a junction disqualifies midpoint averaging regardless of the other two numbers, because the paths through the interior are synthesised rather than extracted.

The rule those three determine is short: Voronoi if the approach count exceeds two, or correspondence fails, or the width CV exceeds 0.15; midpoint otherwise; then append the quadratic-program smoother if the curvature-continuity budget is tighter than 0.02 m.

On a representative urban tile that selects the cheap method for roughly four segments in five and the expensive one for the remaining fifth. Both tile-wide alternatives are worse in a measurable way: a tile-wide midpoint choice produces wrong geometry on the 350 segments that needed the axis, including every junction; a tile-wide Voronoi choice pays roughly a hundredfold cost on the 1 490 that did not. The three measurements together cost microseconds per segment, which is cheaper than either mistake by orders of magnitude.

Recording the measurements alongside the chosen method is worth the column. When a lane's geometry is questioned later the first useful fact is how it was generated and the second is why; and a shift in the method mix between two releases is a strong signal that boundary extraction changed rather than that the roads did — which is a diagnostic no other artefact provides.

FAQ #

When is midpoint averaging good enough? #

Midpoint averaging works when a lane has two clean, roughly parallel boundaries with a one-to-one vertex correspondence. On a straight or gently curving single lane it produces sub-decimetre centerlines at negligible cost. It breaks the moment boundaries branch, merge, or have unequal vertex counts, because there is no longer a well-defined pair of points to average.

Why use a Voronoi medial axis at intersections? #

At an intersection the drivable area is a polygon with multiple entries and exits, not a pair of parallel boundaries, so there is no midpoint to take. The medial axis of that polygon — the set of points equidistant from the boundary, recovered from a Voronoi diagram of the boundary samples — is the natural skeleton of the drivable space and yields branching centerlines that follow every turn movement.

What does the quadratic-program method add? #

A quadratic program fits a centerline that minimizes a weighted sum of deviation from the raw skeleton and a curvature-smoothness penalty, subject to lane-width constraints. It is the choice when the downstream planner needs curvature continuity that midpoint and raw Voronoi output do not guarantee, and it is usually applied as a smoothing stage on top of a Voronoi or midpoint initialization.

Related #

• Benchmarking Voronoi vs QP Centerlines on Intersections — the head-to-head accuracy and compute numbers behind this guide.
• Centerline Generation Algorithms — the implementation-level cluster where each method is coded.
• Calculating Road Curvature with Python Shapely — the curvature measure that gates the QP stage.
• Extracting Lane Boundaries from Point Cloud Data — where the boundary polylines these methods consume come from.

Up one level: Lane Geometry Extraction & Road Network Processing — the parent domain whose centerline stage this guide helps you configure.