Lane Geometry Extraction & Road Network Processing: Production Spatial Pipeline
Lane geometry extraction and road network processing are the deterministic spatial substrate for autonomous vehicle localization, trajectory optimization, and behavioral forecasting. Naive GIS workflows break at production scale: polyline boundaries digitized straight from raw returns carry curvature discontinuities that corrupt lateral-acceleration limits; attributes joined without strict spatial indexing drift onto the wrong lane segment; and a road graph compiled without topological validation routes the planner across phantom edges. A production pipeline therefore enforces strict isolation between raw sensor ingestion, geometric abstraction, semantic enrichment, topological verification, and graph compilation — each stage gated by an explicit numeric tolerance and an audited contract with the stage downstream. This guide sets the algorithms, spatial-data standards, and cross-stack dependencies for turning raw sensor returns into a validated, navigable road-network graph at fleet scale.
From raw sensor returns to a validated, navigable road-network graph:
Stage 1 — Spatial ingestion & datum alignment #
Production-grade processing begins with coordinate normalization and vertical datum alignment. Raw LiDAR point clouds, multi-camera photogrammetric reconstructions, and survey-grade GNSS/INS trajectories must be projected into a single, locally optimized planar frame to eliminate metric distortion before any geometric derivative is computed. Elevation references demand explicit transformation between ellipsoidal heights and orthometric datums, because an unhandled geoid separation injects a systematic bias straight into longitudinal grade and cross-slope. The dual-frame discipline this requires — a global geodetic frame for archival, a metric projection for planning — is the same one governed by coordinate reference systems for autonomous vehicles on the HD mapping side, and the CRS contract must be shared, not re-derived.
Ingestion enforces strict schema validation against automotive spatial standards — typically the ASAM OpenDRIVE specification or proprietary NDS schemas — and the tolerance set at this gate dictates how spatial uncertainty propagates through the rest of the stack. Build the transform layer on the PROJ coordinate transformation library (via pyproj), pin the EPSG datum and epoch explicitly, and validate conformance to ISO 19111 spatial referencing by coordinates.
from pyproj import Transformer
# Pin datum + epoch; resolve ellipsoidal vs orthometric height before geometry.
to_local = Transformer.from_crs("EPSG:4326", "EPSG:32633", always_xy=True)
east, north = to_local.transform(lon, lat) # metres, ready for curve fitting
A wrong vertical datum is the canonical silent failure here: horizontal geometry validates cleanly while every grade and superelevation value is biased. Gate the height path against ground control before anything downstream consumes it.
Stage 2 — Centerline generation #
Once spatial data is aligned and quality-gated, the pipeline reduces noisy lane-boundary polylines into mathematically stable reference curves. Centerline generation algorithms are the primary mechanism for this abstraction: production implementations employ constrained medial-axis transforms, Voronoi skeletonization, or G²-continuous spline and clothoid fitting to minimize curvature discontinuity while preserving drivable-width constraints and lane topology. The output must be strictly parameterized by arc length so downstream kinematic modeling and path planning can sample it deterministically, and it must hold ≤0.1 m lateral error against the source boundaries — the same tolerance the OpenDRIVE serialization stage downstream depends on.
Centerlines are derived from the lane boundaries themselves, so the boundary-extraction step — extracting lane boundaries from point cloud data — is the precondition for this stage. Model both boundaries and the fitted centerline with shapely and resample to a fixed arc-length step before fitting.
import numpy as np
from shapely.geometry import LineString
from scipy.interpolate import CubicSpline
left, right = LineString(left_pts), LineString(right_pts)
s = np.linspace(0, 1, 400)
mid = np.array([left.interpolate(t, normalized=True).coords[0], # paired
right.interpolate(t, normalized=True).coords[0]]
for t in s).mean(axis=1)
# Arc-length reparameterize, then fit a C2-continuous spline.
cs = CubicSpline(np.r_[0, np.cumsum(np.linalg.norm(np.diff(mid, axis=0), axis=1))], mid)
Method trade-offs — midpoint versus Voronoi versus quadratic-program fitting, and how each behaves through intersection geometry — are treated in depth in the centerline generation algorithms reference.
Stage 3 — Curvature & superelevation mapping #
Geometric stability enables the spatial derivatives the dynamics model consumes. Road curvature and superelevation mapping computes lateral-acceleration constraints and banking angles by numerically differentiating the arc-length-parameterized centerline and cross-referencing DEM-derived elevation profiles. Because curvature κ is a second derivative, it amplifies high-frequency sensor noise: regularize with a Savitzky–Golay filter or moving least squares before differentiating, or the resulting κ profile will violate the vehicle-dynamics envelope with spurious spikes. State the bound explicitly — for example, reject any segment whose smoothed |κ| exceeds the design-speed lateral-acceleration limit — rather than trusting a qualitative "smooth enough."
from scipy.signal import savgol_filter
xy = cs(np.linspace(0, cs.x[-1], 2000))
xy = savgol_filter(xy, window_length=31, polyorder=3, axis=0) # denoise first
d1 = np.gradient(xy, axis=0); d2 = np.gradient(d1, axis=0)
kappa = (d1[:, 0]*d2[:, 1] - d1[:, 1]*d2[:, 0]) / np.linalg.norm(d1, axis=1)**3
The differentiation scheme, geoid handling for the cross-slope term, and the canonical calculating road curvature with Python and Shapely walkthrough are detailed in the road curvature and superelevation mapping reference.
Stage 4 — Lane-attribute extraction & fusion #
Geometric primitives alone cannot drive decision-making; semantic and regulatory attributes must be fused with the spatial features. Batch lane-attribute extraction processes large map tiles to classify lane types, extract marking geometries, associate speed limits, and bind traffic-control devices to specific lane segments. This stage leans on spatial joins, raster–vector overlay, and post-processed machine-learning inference resolved into deterministic attributes. Attribute binding must maintain strict spatial indexing — R-tree or quadtree — so map compilation can resolve "which lane owns this attribute" in sub-millisecond queries; an unindexed nearest-neighbor join is the failure mode that silently snaps a speed limit onto the adjacent lane.
from shapely.strtree import STRtree
tree = STRtree(lane_segments) # R-tree spatial index
for marking in markings: # bind each marking to its lane
seg = lane_segments[tree.nearest(marking)]
seg.attrs.setdefault("markings", []).append(marking.attrs)
Versioned attribute stores let regulatory updates propagate without triggering full geometric recomputation, which is what makes delta-based distribution to the fleet tractable. The classification pipeline, overlay patterns, and the automating lane width attribute sync workflow are covered in the batch lane-attribute extraction reference.
Stage 5 — Topological validation & graph construction #
Spatial accuracy is meaningless without topological correctness. Topological validation rules enforce connectivity, intersection consistency, and lane-adjacency relationships across the whole network: validation engines reject dangling nodes, overlapping geometries, inconsistent widths, and invalid turn restrictions before any tile is accepted. This is the same class of graph-consistency discipline that lane-level topology modeling applies on the HD mapping side, and the two contracts must agree at the tile seam.
Validated primitives are then compiled into a directed, weighted graph. Road-network graph construction translates centerlines and lane boundaries into navigable nodes and edges, embedding traversal cost, speed profiles, and maneuver constraints so global planners can run efficient Dijkstra/A* queries with dynamic edge weighting and hierarchical abstraction for long-range routing. Model it with networkx and assert the invariants the planner relies on.
import networkx as nx
g = nx.DiGraph()
for lane in lanes:
for succ in lane.successors:
g.add_edge(lane.id, succ, cost=lane.cost(succ),
restriction=lane.turn_rule(succ))
assert nx.number_of_selfloops(g) == 0 # no phantom self-edges
assert all(d > 0 for *_, d in g.edges.data("cost")) # positive weights
Connectivity constraints, intersection consistency checks, and self-intersection thresholds are detailed in the topological validation rules reference.
Stage 6 — Junctions, which are authored rather than extracted #
Stages 1 to 5 recover geometry that exists on the ground. Inside a junction there is nothing to recover: the paint stops at the stop line, the drivable surface is one continuous area, and the paths vehicles take across it are conventions rather than markings. The boundary detection that produces ordinary lanes returns nothing there, which makes junction geometry the one part of an HD map that is authored — and authored geometry needs a different kind of validation.
Intersection and junction modeling covers that stage. Its three obligations are to produce one path per legal movement, to keep each path drivable, and to record where paths conflict. The first is a bookkeeping problem taken from the source schema's connection table rather than inferred from geometry — turn movements overlap in space, so geometry alone cannot tell a left turn from a through movement passing over the same asphalt. The second is a kinematic constraint: peak curvature must stay inside what the vehicle class can execute at the junction's design speed, which at 8 m/s and a 2.0 m/s² lateral cap is a 32 m radius, tighter than many residential left turns. The third is what makes an unprotected turn tractable for a planner, because the crossings do not change between frames and therefore belong in the map rather than in a per-frame computation.
The validation that matters most is the one every check written for ordinary lanes misses. A turn path can join its lanes with continuous heading, stay inside its curvature limit, and still put the vehicle's rear wheels over a kerb — because on a tight turn the rear axle tracks up to a metre inside the path the front axle follows, and a symmetric buffer around the centreline places the corridor's inside edge exactly where the vehicle definitely is not. Building the swept corridor from both axle tracks, and reporting the depth of any incursion rather than a boolean, is what turns that from an invisible defect into a triageable finding.
Choosing the method rather than defaulting to it #
Two of the stages above admit more than one algorithm, and a decision made once — in a design document, for a road that no longer resembles what the fleet drives — is how a pipeline ends up applying midpoint averaging at a junction.
For centerlines the decision is three cheap measurements on the segment itself: whether the two boundaries admit a monotone correspondence, how much the width varies along the segment, and how many carriageways meet inside its extent. Choosing between centerline methods for intersection geometry sets out the rule those three numbers determine, and the reason it is worth measuring per segment rather than per tile: a single urban tile routinely contains a motorway straight, a roundabout and a residential junction, and roughly one segment in five needs the more expensive method while four in five do not.
Where the medial axis is the right method, its raw output is never usable — it inherits every wobble of the boundary that produced it. Generating centerlines with a Voronoi medial axis covers the pruning that reduces it to a spine, with a threshold expressed as a multiple of local road width so it survives a carriageway that widens. Smoothing centerlines with quadratic programming then poses the smoothing as a constrained optimisation rather than a filter, so the accuracy budget this section allocates is a hard constraint rather than something discovered afterwards.
The graph, and the invariants topology cannot see #
The routing graph is where the section's output becomes usable, and two additions matter at this phase. Junction interiors have to be expanded into the graph as first-class nodes rather than collapsed into a single hop across the junction, or the route's length is wrong, the turn's curvature is unavailable and there is nowhere to record a conflict. Edges then have to be costed in a single unit — time — so that a lane change, a conflicted turn and a comfort penalty can be weighed against each other by somebody who can check the numbers against fleet behaviour.
Separately, a lane can pass every connectivity check and still be undrivable. It can narrow to 2.1 m for eight metres while averaging a normal 3.4 m; its body can intersect an adjacent lane's; it can fold through itself after a smoothing step on a hairpin. None of those is visible to a check that asks about starts, ends and successors, which is why enforcing lane width and overlap invariants measures the space each lane occupies, per station, against a band that depends on the road class.
Cross-stack integration notes #
This domain's outputs are the source of truth for the rest of the AV spatial stack, and the contracts between them are where integration defects surface:
- Into HD map serialization. The arc-length centerlines, widths, and curvature produced here feed directly into the OpenDRIVE serialization governed by HD mapping architecture and spatial-data standards. If centerline geometry exceeds ≤0.1 m lateral error, the OpenDRIVE schema validation gate downstream will reject the tile — geometry tolerance here is an upstream precondition for schema conformance there.
- From sensor fusion. The registered, time-aligned point clouds this pipeline consumes are produced by sensor fusion and spatial-data alignment; residual misregistration from the point-cloud registration stage propagates as boundary noise that the centerline smoother in Stage 2 must absorb, so the fusion accuracy budget and the centerline tolerance are coupled.
- Into planning. The compiled lane graph and its regulatory attributes are the planner's source of truth for legal maneuvers; an unvalidated turn restriction or a mislabeled speed limit becomes an illegal trajectory, which is why Stage 5 validation is a hard CI gate rather than a soft warning.
The tolerance budget for the whole section, drawn as the chain it is. Each stage consumes part of a fixed lane-level allowance, and a stage that overspends leaves the ones after it nothing:
Failure modes & safety constraints #
An automotive-grade failure taxonomy pairs every stage boundary with a detection gate and a fallback, traceable to the ISO 26262 functional-safety lifecycle:
- Vertical-datum bias — ellipsoidal height consumed as orthometric, biasing every grade and cross-slope. Gate: height check against ground control after Stage 1. Fallback: reject the tile; do not publish.
- Curvature noise spikes — unfiltered second derivatives producing κ that violates the dynamics envelope. Gate: smoothed-|κ| bound against the design-speed lateral-acceleration limit. Fallback: re-fit with a wider smoothing window or quarantine the segment.
- Attribute misbinding — a speed limit or marking snapped to the wrong lane by an unindexed join. Gate: spatial-index containment assertion (attribute geometry within its owning segment buffer). Fallback: flag for manual review.
- Topology defects — phantom edges, dangling nodes, or cycles producing invalid routes. Gate: graph consistency assertions (zero self-loops, positive weights, reachability). Fallback: quarantine the tile.
- Stale graph at runtime — the planner holding a superseded road-graph revision. Gate: content-addressed revision check at load. Fallback: degraded-mode routing on a coarsened graph derived from standard navigation data.
When a critical anomaly is detected in production, automated safeguards halt the affected tile's distribution to prevent fleet-wide propagation, and emergency rollback reinstates the last cryptographically verified good revision. Spatial-data contracts between this domain and planning mandate ≤0.05 m horizontal and ≤0.1 m vertical RMS error, and these fallback paths must be exercised against datum bias, attribute drift, and sudden topology changes in integration test.
The one number the whole section is spending #
Every stage in this section consumes part of a single lane-level positional budget, and the budget is small enough that no stage gets a comfortable share. Datum alignment takes 0.02 m, centerline generation 0.04 m, curvature and superelevation fitting 0.02 m, attribute projection and graph snapping 0.01 m each — which sums to exactly the 0.10 m ceiling with nothing left over.
That arithmetic has two consequences worth stating explicitly. The first is that a stage which overspends does not merely degrade its own output; it consumes the allowance the stages after it were relying on, and the failure surfaces somewhere else entirely. A smoothing step that quietly takes 0.09 m leaves the graph-snapping stage with a negative budget, and what a reviewer sees is a connectivity gap rather than an over-smoothed lane. Recording each stage's actual spend, not just its pass or fail, is what makes that traceable.
The second is that errors do not always add in quadrature. Independent random errors do, which is the assumption behind treating the budget as generous; a systematic error — a datum shift, a consistent sign convention mistake, a projection applied at the wrong epoch — adds linearly and eats the whole budget at once. That asymmetry is why stage 1 is gated harder than its 0.02 m share suggests: it is the stage whose errors are systematic by nature, and a systematic 0.02 m is worth several random ones.
Production deployment checklist #
Enforcing strict datum alignment, geometrically stable centerlines, regularized curvature, indexed attribute binding, and topological validation lets engineering teams deliver high-definition road networks that scale reliably across diverse operational design domains.
Related #
- Centerline Generation Algorithms
- Road Curvature & Superelevation Mapping
- Batch Lane Attribute Extraction
- Topological Validation Rules
- Choosing a Centerline Extraction Algorithm: Midpoint, Voronoi & QP
- Building Routable Road-Network Graphs from HD Maps
- HD Mapping Architecture & Spatial Data Standards
- Sensor Fusion & Spatial Data Alignment
Up one level: this guide is a top-level section of vehiclemapping.org.