VehicleMapping HD AV Spatial Data

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:

End-to-end lane-geometry extraction pipeline Raw LiDAR, photogrammetry, and GNSS/INS feed CRS normalization and vertical datum alignment, then centerline generation. The centerline branches into curvature and superelevation mapping and into batch lane-attribute extraction; both feed a topological validation gate. A pass compiles the road-network graph and delta-encoded OTA distribution; a fail routes to reprocess or manual review. STAGE 1 STAGE 2 STAGES 3 · 4 STAGE 5 Raw sensor in LiDAR · photo · GNSS/INS CRS + datum vertical datum align Centerline gen clothoid / spline fit Curvature κ + superelevation Lane attributes width · marks · speed Topo valid? pass fail Road-network graph nodes + weighted edges OTA delta-encoded Reprocess / manual review

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.

python
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.

python
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."

python
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.

python
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.

python
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.

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.

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.

Failure-mode to detection-gate to fallback map Five corruption vectors each map to a detection gate and a fallback. Vertical-datum bias is caught by a ground-control height check and the tile is rejected. Curvature noise spikes are caught by a smoothed-curvature bound against the design-speed lateral-acceleration limit and the segment is re-fit or quarantined. Attribute misbinding is caught by a spatial-index containment assertion and flagged for manual review. Topology defects are caught by graph-consistency assertions and the tile is quarantined. A stale runtime graph is caught by a content-addressed revision check and falls back to degraded-mode routing. CORRUPTION VECTOR DETECTION GATE FALLBACK Vertical-datum bias ellipsoidal read as orthometric Ground-control height check after Stage 1, before publish Reject tile do not publish Curvature noise spikes unfiltered 2nd derivative Smoothed |κ| bound vs design-speed lat-accel limit Re-fit / quarantine wider smoothing window Attribute misbinding unindexed nearest-neighbor Spatial-index containment attr within owning segment buffer Flag for review manual re-bind Topology defects phantom edges · dangling nodes Graph-consistency asserts 0 self-loops · positive weights Quarantine tile block distribution Stale graph at runtime planner holds old revision Content-addressed rev check verified at graph load Degraded-mode routing coarse nav-data graph Contract: ≤0.05 m horizontal · ≤0.1 m vertical RMS · ISO 26262 traceable

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.

Up one level: this guide is a top-level section of vehiclemapping.org.