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.

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}"

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.

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.