Lane-Level Topology Modeling for Autonomous Vehicle Spatial Data

Lane-level topology modeling converts raw survey geometry into a directed, attribute-rich graph of lane segments that serves as the deterministic backbone for predictive path planning, localization anchoring, and behavioral prediction. It sits one stage downstream of geometry extraction in the HD Mapping Architecture & Spatial Data Standards pipeline: once centerlines are projected into a metric frame, connectivity inference must resolve predecessor/successor relationships, merges, splits, and junction routing without introducing phantom edges or orphaned nodes. The tolerance budget is tight — coincident segment endpoints must agree to within ≤0.05 m, heading continuity across a join must hold to within ±5° on through-lanes (relaxed to ±45° at merges and turns), and the resulting graph must be cycle-free in one-way corridors. The workflow below builds that graph with networkx and shapely, then enforces those bounds with automated gates before any tile is committed to the map database.

Survey data becomes a validated directed lane graph in three phases:

Connectivity Inference Approaches #

Several strategies resolve which lane segments connect to which. The choice trades geometric precision against compute cost and against robustness on degenerate input (parallel parking bays, near-coincident service roads, hairpin junctions).

The proximity + heading gate is the canonical default and is implemented below. Where an authored OpenDRIVE source exists, prefer its explicit <link> directives and use heading inference only to fill gaps; where intersections remain ambiguous, layer trajectory voting on top.

Stage-by-Stage Implementation Walkthrough #

Stage 1: Spatial reference normalization #

Raw survey inputs — terrestrial LiDAR sweeps, mobile mapping imagery, and RTK-GNSS trajectories — must share one metric frame before topological inference begins. Projection misalignment introduces centimeter-scale drift that cascades into routing discontinuities and localization failures. The constraint: every segment endpoint must be expressed in a single East-North-Up (ENU) Cartesian frame with residual reprojection error ≤0.05 m RMSE against ground control. This stage follows the conventions of coordinate reference systems for AV pipelines; use thread-safe pyproj transformers (Transformer.from_crs(..., always_xy=True)) and a fixed local origin to avoid implicit datum shifts across multi-epoch updates.

from pyproj import Transformer
import numpy as np

# WGS84 (EPSG:4326) -> UTM zone 32N (EPSG:32632); always_xy keeps (lon, lat) order.
_tf = Transformer.from_crs("EPSG:4326", "EPSG:32632", always_xy=True)

def to_enu(lonlat: np.ndarray, origin: tuple[float, float]) -> np.ndarray:
    """Reproject (lon, lat) -> local ENU metres about a fixed origin."""
    x, y = _tf.transform(lonlat[:, 0], lonlat[:, 1])
    return np.column_stack([x - origin[0], y - origin[1]])

Stage 2: Geometric primitives and directed graph serialization #

Projected lane centerlines and boundaries are extracted via semantic segmentation followed by curve fitting. Clothoid splines or cubic Bézier approximations preserve G1/G2 continuity, which is required for smooth trajectory generation and lateral control stability. The constraint at this stage is structural: nodes represent discrete lane segments, edges encode permissible transitions, and every edge must carry a typed transition (lane_follow, merge, split, junction) plus a curvature ratio so the planner can cost it. The serialization maps directly onto the predecessor/successor model of the OpenDRIVE schema breakdown, keeping lane IDs and regulatory attributes structured for downstream consumption. The canonical construction uses networkx for topology and shapely for geometric validation:

import networkx as nx
from shapely.geometry import LineString, Point
import numpy as np
from typing import List, Dict

def build_lane_topology(segments: List[Dict], tolerance: float = 0.15) -> nx.DiGraph:
    """Constructs a directed lane topology graph with heading-aligned connectivity."""
    G = nx.DiGraph()
    for seg in segments:
        G.add_node(seg["id"],
                   geometry=LineString(seg["coords"]),
                   width=seg.get("width", 3.5),
                   speed_limit=seg.get("speed_limit", 50),
                   lane_type=seg.get("lane_type", "driving"))

    # Spatial indexing and heading-based edge inference
    for u_id, u_data in G.nodes(data=True):
        u_geom = u_data["geometry"]
        u_end = Point(u_geom.coords[-1])

        # Compute terminal heading (radians)
        dx = u_geom.coords[-1][0] - u_geom.coords[-2][0]
        dy = u_geom.coords[-1][1] - u_geom.coords[-2][1]
        u_heading = np.arctan2(dy, dx)

        # Candidate successors within proximity tolerance
        candidates = [n for n, d in G.nodes(data=True)
                      if n != u_id and Point(d["geometry"].coords[0]).distance(u_end) < tolerance]

        for v_id in candidates:
            v_data = G.nodes[v_id]
            v_geom = v_data["geometry"]
            v_dx = v_geom.coords[1][0] - v_geom.coords[0][0]
            v_dy = v_geom.coords[1][1] - v_geom.coords[0][1]
            v_heading = np.arctan2(v_dy, v_dx)

            # Heading alignment threshold (±45° for merges/turns)
            delta = np.rad2deg(abs(u_heading - v_heading)) % 360
            if delta <= 45 or delta >= 315:
                G.add_edge(u_id, v_id,
                           transition_type="lane_follow",
                           curvature=np.hypot(dx, dy) / (np.hypot(v_dx, v_dy) + 1e-6))

    return G

The naive candidate scan above is O(n²); Stage 3 replaces it with an R-tree query so the same logic scales to dense urban tiles.

Stage 3: Spatially indexed connectivity and attribute binding #

Production pipelines accelerate neighbor discovery with an R-tree over segment start-points so each terminal node queries only nearby candidates rather than the full node set. The heading gate then filters spurious connections from parallel parking lanes or service roads, and regulatory constraints — turn restrictions, traffic-signal phasing, dynamic speed zones — are attached as edge attributes and validated against municipal traffic-control databases.

from shapely.strtree import STRtree
from shapely.geometry import Point
import numpy as np

def index_successors(G, tolerance: float = 0.05):
    """R-tree-accelerated successor lookup keyed on segment start-points."""
    starts = [Point(d["geometry"].coords[0]) for _, d in G.nodes(data=True)]
    ids = list(G.nodes)
    tree = STRtree(starts)
    for u_id, u_data in G.nodes(data=True):
        end = Point(u_data["geometry"].coords[-1])
        for j in tree.query(end.buffer(tolerance)):     # candidate indices in radius
            v_id = ids[j]
            if v_id != u_id and starts[j].distance(end) <= tolerance:
                yield u_id, v_id

Validation & QC Automation #

Graph construction alone does not guarantee navigability. Every tile passes automated gates before it is committed; failures route the offending tile back to the survey QA queue rather than reaching the planner. The enforced thresholds:

• Endpoint coincidence — adjacent segments must share endpoints within ≤0.05 m; any join above this is a phantom edge.
• Heading continuity — through-lane joins must agree to within ±5°; joins between 5° and 45° must be typed as merge/turn, and anything beyond 45° is rejected.
• Orphan count — zero weakly-connected components of size 1 (every drivable segment must be reachable).
• Cycle freedom — one-way corridors must be acyclic; bidirectional roads are checked per-direction.
• Attribute completeness — width, speed_limit, and lane_type non-null; enforced via JSON Schema or Protobuf validators so the motion planner receives strictly typed fields.

import networkx as nx

def validate_topology(G) -> list[str]:
    """Returns a list of gate failures; empty list == pass."""
    errors = []
    orphans = [n for n in G if G.degree(n) == 0]
    if orphans:
        errors.append(f"orphan_nodes: {orphans}")
    oneway = G.subgraph([n for n, d in G.nodes(data=True)
                         if d.get("lane_type") == "driving"])
    if not nx.is_directed_acyclic_graph(oneway):
        cyc = nx.find_cycle(oneway, orientation="original")
        errors.append(f"cycle_in_oneway: {cyc}")
    for n, d in G.nodes(data=True):
        for field in ("width", "speed_limit", "lane_type"):
            if d.get(field) is None:
                errors.append(f"null_attr:{field}@{n}")
    return errors

# CI gate: assert validate_topology(G) == [], else fail the build.

Wire validate_topology into the tile-build CI step so a non-empty return fails the job and blocks the merge, mirroring the topological-validation discipline used across the lane geometry extraction and road-network processing pipeline.

Edge Cases & Failure Patterns #

• Parallel-lane false merges. In dense grids, two adjacent through-lanes share near-coincident endpoints at a stop bar. Proximity-only inference links them; the ±5° heading gate plus a lateral-offset check (reject if the perpendicular distance between centerlines exceeds half a lane width, ~1.75 m) suppresses these.
• Hairpin and U-turn under-detection. A ±45° gate rejects legitimate 180° U-turn lanes. Tag U-turn segments from the source schema and bypass the heading gate for them rather than widening the global threshold.
• Floating-point endpoint drift. Coordinates reprojected without a local origin lose precision in IEEE 754 doubles, so endpoints that should coincide fall just outside 0.05 m. Always subtract a fixed origin (Stage 1) before distance tests.
• Phantom edges across tile seams. A segment ending exactly on a tile boundary has no successor within the tile and is wrongly flagged as a dead-end. Resolve at runtime via buffer-zone stitching — see managing map tile boundaries in ROS2.
• Cyclic dependency from mislabeled one-way. A single segment digitized in the wrong direction creates a back-edge and trips the cycle gate; nx.find_cycle localizes it to the offending node for re-extraction.

Performance & Scale Notes #

Static topology graphs are too large to load whole on vehicle-grade hardware, so the global graph is partitioned into spatially indexed tiles — typically 500 m × 500 m or 1 km × 1 km — with overlapping buffer zones that prevent routing discontinuities during tile swaps. Cross-tile routing flags terminal nodes at tile edges and matches them against adjacent-tile metadata.

• Indexing. Replace the O(n²) candidate scan with the R-tree query from Stage 3; on a 1 km² tile of ~8,000 segments this drops connectivity inference from minutes to sub-second.
• Memory ceiling. At runtime the AV stack uses memory-mapped graph access and lazy tile loading to hold working memory within strict automotive budgets (target ≤200 MB resident for the active routing window).
• Pruning. Strip non-essential attributes (historical survey metadata, unused markings) and delta-encode edge lists before serializing the runtime graph; this typically shrinks a tile 4–6× versus the authoring graph.
• Concurrency. Tile builds are embarrassingly parallel — fan out one worker per tile, then run a single cross-seam stitching pass — so a fleet-wide rebuild scales linearly with worker count.

The lightweight graph feeds the local planner directly, enabling millisecond-scale route queries, dynamic obstacle avoidance, and predictive lane-change evaluation. CI regression suites validate each tile so topology updates never degrade localization confidence or planning-horizon stability.

Frequently Asked Questions #

What heading tolerance should connect two lane segments? Use ±5° for through-lane continuity and widen to ±45° only for typed merges and turns. Anything beyond 45° is rejected as a false edge unless the source schema explicitly marks it as a U-turn.

How do I keep endpoint coincidence stable across map updates? Reproject every epoch into the same ENU frame about a fixed local origin, then test coincidence at ≤0.05 m. Subtracting the origin before distance tests prevents the floating-point drift that otherwise breaks endpoint matching.

Why use a directed graph instead of an undirected one? Lane routing is direction-dependent: one-way corridors, legal turn restrictions, and merge/split logic all require directed edges, and the cycle-freedom gate only makes sense on a DiGraph.

Related #

• Coordinate Reference Systems for AVs — the ENU normalization stage this graph depends on.
• OpenDRIVE Schema Breakdown — predecessor/successor model and explicit <link> connectivity.
• Managing Map Tile Boundaries in ROS2 — buffer-zone stitching for cross-tile routing.
• Lane Geometry Extraction & Road Network Processing — the geometry pipeline that produces the centerlines fed into topology inference.

Up one level: HD Mapping Architecture & Spatial Data Standards.