Topological Validation Rules for Production HD Mapping

Topological validation is the deterministic quality gate between raw LiDAR/vision-derived spatial features and a production-grade HD map. Within the Lane Geometry Extraction & Road Network Processing pipeline it sits immediately after centerline generation and before any tile is promoted to simulation or fleet deployment: latent connectivity faults, broken adjacency relationships, or geometric discontinuities propagate directly into particle-filter localization drift, path-planner oscillation, and unsafe control commands. This stage must therefore enforce hard, reproducible constraints — node-degree consistency, adjacency separation within ±0.15 m, G¹ tangent continuity, curvature bounded by the vehicle kinematic envelope, and zero dangling edges — and quarantine anything that fails rather than passing it downstream. The walkthrough below covers schema normalization, the four constraint families, the numeric QC thresholds that gate a CI build, and the failure and scale patterns that break naive implementations.

Each rule stage is a gate — features that fail are quarantined or routed to remediation:

Validation strategy comparison #

A topological validator can be built around several backends, each trading correctness guarantees against compute cost and integration effort. The table fixes the trade-offs so the choice is explicit rather than incidental.

The hybrid backend is the production default: it reuses the lane-level topology model as its graph substrate and layers shapely metric predicates on top, so a phantom connection across a median (legal in the graph, impossible in geometry) is caught by the geometry pass while an orphaned but geometrically clean stub is caught by the graph pass.

Stage-by-stage implementation walkthrough #

Stage 1 — Graph normalization and schema enforcement #

Before any rule runs, the extracted network must be normalized into a directed multigraph $G = (V, E)$, where vertices $V$ encode topological breakpoints (intersections, lane terminations, merge/diverge points) and edges $E$ carry continuous drivable segments. Every node and edge must share a single projected coordinate reference system — typically EPSG:326xx UTM or a local engineering grid established in coordinate reference systems for AVs — so that all downstream distances are metric and free of projection distortion. Edge attributes are schema-checked (lane_id UUID, traversal_direction enum, legal_speed_limit float, centerline LineString); features with null geometry, self-intersecting lines, or a CRS mismatch are quarantined at the gate rather than admitted.

import networkx as nx
from shapely.geometry import LineString
from shapely.validation import explain_validity

REQUIRED = ("lane_id", "traversal_direction", "legal_speed_limit", "centerline")

def normalize(features, target_epsg=32633):
    """Build a directed multigraph; quarantine malformed features."""
    G = nx.MultiDiGraph(crs=target_epsg)
    quarantine = []
    for f in features:
        geom = f.get("centerline")
        if (not all(k in f for k in REQUIRED)
                or geom is None
                or not isinstance(geom, LineString)
                or not geom.is_valid
                or geom.is_empty):
            quarantine.append((f.get("lane_id"), explain_validity(geom) if geom else "null"))
            continue
        u = tuple(round(c, 3) for c in geom.coords[0])   # snap endpoints to 1 mm
        v = tuple(round(c, 3) for c in geom.coords[-1])
        G.add_edge(u, v, key=f["lane_id"],
                   direction=f["traversal_direction"],
                   speed=f["legal_speed_limit"], geom=geom)
    return G, quarantine

Snapping endpoints to a 1 mm grid (round(c, 3) in metres) absorbs floating-point drift so that two segments meant to share a node actually do, eliminating false dangling-edge reports later.

Stage 2 — Connectivity and adjacency constraints #

Topological integrity is governed by node-degree distributions and lateral adjacency. Intersection vertices must hold in-degree/out-degree ratios consistent with lane counts and turn restrictions; parallel lanes must keep consistent lateral separation without illegal crossings or overlapping footprints. Adjacency is verified with a spatial index (shapely.STRtree) to bound the pairwise comparison, then a Hausdorff distance flags centerlines whose separation drifts outside the urban HD-mapping tolerance of 0.15 m.

from shapely import STRtree
import numpy as np

def check_adjacency(G, min_sep=0.15, max_sep=4.0):
    edges = [(k, d["geom"]) for *_ , k, d in G.edges(keys=True, data=True)]
    geoms = [g for _, g in edges]
    tree = STRtree(geoms)
    violations = []
    for i, (lane_id, g) in enumerate(edges):
        for j in tree.query(g.buffer(max_sep)):
            if j <= i:
                continue
            h = g.hausdorff_distance(geoms[j])           # symmetric worst-case offset
            if h < min_sep:                              # overlapping / crossing footprints
                violations.append((lane_id, edges[j][0], "overlap", round(h, 3)))
    # dangling edges: a non-terminal node with degree 1
    for n in G.nodes:
        if G.degree(n) == 1 and not G.nodes[n].get("terminal"):
            violations.append((n, None, "dangling_edge", G.degree(n)))
    return violations

Transition validity is layered on top: a rule blocks invalid lane-to-lane handoffs (opposing-traffic merges, phantom connections across a median) by comparing direction enums and the angular delta between an inbound and outbound tangent at each shared node.

Stage 3 — Geometric continuity and curvature thresholding #

Beyond discrete connectivity the validator enforces geometric smoothness across segment boundaries, especially at merge and diverge zones. A break in first-order tangent direction ($G^1$ continuity) or an abrupt second-order curvature shift injects systematic drift into scan matching and destabilizes the lateral controller. Each edge is densely resampled and discrete curvature is computed as $\kappa = \frac{|x'y'' - y'x''|}{(x'^2 + y'^2)^{3/2}}$; segments whose curvature exceeds the vehicle kinematic limit, or whose superelevation implies lateral acceleration above $a_y \leq 0.3g$ for passenger vehicles, are routed to remediation.

import numpy as np

def curvature_profile(geom, step=0.5):
    """Discrete curvature κ sampled every `step` metres along an edge."""
    n = max(int(geom.length / step), 3)
    pts = np.array([geom.interpolate(d).coords[0]
                    for d in np.linspace(0, geom.length, n)])
    dx, dy = np.gradient(pts[:, 0]), np.gradient(pts[:, 1])
    ddx, ddy = np.gradient(dx), np.gradient(dy)
    denom = (dx**2 + dy**2) ** 1.5
    kappa = np.abs(dx * ddy - dy * ddx) / np.where(denom == 0, np.nan, denom)
    return kappa

def check_continuity(G, kappa_max=0.20, tangent_tol_deg=8.0):
    bad = []
    for u, v, k, d in G.edges(keys=True, data=True):
        kappa = curvature_profile(d["geom"])
        if np.nanmax(kappa) > kappa_max:                 # 1/min_turn_radius
            bad.append((k, "curvature", round(float(np.nanmax(kappa)), 4)))
    return bad

The curvature ceiling kappa_max is the reciprocal of the platform minimum turning radius and is shared with the methodology in Road Curvature & Superelevation Mapping, so a curvature value that passes there cannot be re-flagged here.

Stage 4 — Centerline alignment and global consistency #

The final stage verifies centerline-to-boundary alignment and global topological consistency across the tile. Boundary polylines must stay parallel to their centerline within a 0.10 m envelope, every drivable segment must terminate at a valid graph node (no orphaned geometry), and the network as a whole must have closed cycles where the road layout implies them. Cross-references against regulatory attribute databases and the batch lane attribute extraction output confirm that semantic tags survived the geometric transforms intact.

def check_alignment(centerline, left, right, tol=0.10, step=1.0):
    """Lateral parallelism of boundaries to their centerline."""
    n = max(int(centerline.length / step), 3)
    errs = []
    for dist in np.linspace(0, centerline.length, n):
        p = centerline.interpolate(dist)
        errs.append(abs(left.distance(p) - right.distance(p)))   # symmetric offset
    rmse = float(np.sqrt(np.mean(np.square(errs))))
    return rmse, rmse <= tol

Validation and QC automation #

Every rule emits a structured violation record — rule_id, world coordinate, severity, measured value, threshold — serialized to Parquet or GeoJSON so the failing geometry is locatable on a map and the regression is queryable in CI. The gate is binary: a tile advances to simulation only when every blocking rule reports zero violations.

def ci_gate(G):
    report = (check_adjacency(G) + check_continuity(G))
    blocking = [r for r in report if r[1] != "cycle_closure"]
    assert not blocking, f"{len(blocking)} blocking topology violations: {blocking[:5]}"
    return report

Wiring ci_gate into a pre-merge job means a map version that introduces a phantom connection or an over-curved merge fails the build deterministically, the same way a unit test would, rather than surfacing as a localization incident in the field.

The four stages catch defects in a deliberate order, because a check run on an un-normalized graph reports the normalization problem rather than the defect it was written to find:

Edge cases and failure patterns #

• Endpoint micro-gaps. Two segments that should share a node sit 2–3 mm apart from independent fits, producing spurious dangling_edge reports. Mitigated by the 1 mm endpoint snap in Stage 1; raising the snap tolerance too far instead merges genuinely distinct nodes — keep it below the lane-width floor.
• STRtree false negatives on long thin geometry. Bounding-box queries over near-axis-aligned centerlines return many candidates; without the max_sep buffer the adjacency pass degrades toward O(n²). Always pre-buffer the query geometry rather than widening the index.
• Curvature spikes from undersampling. A step larger than the local radius of curvature aliases $\kappa$ and emits false positives at tight intersections. Clamp step to ≤ R_min/10 in dense zones.
• CRS drift across tiles. Adjacent tiles built in different UTM zones report apparent discontinuities at the seam; normalize every tile to a single engineering grid before cross-tile validation, consistent with managing map tile boundaries in ROS 2.
• OpenDRIVE namespace drift. Spec-conformance rules silently skip elements when the XSD namespace changes across versions; pin the schema version and fail closed on unknown namespaces.

The thresholds this section enforces, gathered in one place with what each is derived from. None of them is a round number chosen for tidiness — each traces back to a physical or regulatory quantity:

Performance and scale notes #

City-scale validation is dominated by the geometry pass, so the graph pre-gate should run first and short-circuit cheap structural failures before any shapely predicate executes. Partition tiles by H3 hex or GeoHash and validate non-overlapping cells in parallel with concurrent.futures.ProcessPoolExecutor; the multigraph for a single urban tile fits comfortably under a 2 GB worker ceiling, so concurrency is bounded by core count rather than RAM. Build the STRtree once per tile and reuse it across the adjacency and alignment passes instead of rebuilding per rule. Serialize violation reports as partitioned Parquet keyed by tile id so a CI run over thousands of tiles produces a single queryable dataset rather than scattered logs, and hash the input geometry so unchanged tiles skip re-validation entirely on incremental builds.

Why the stages run in this order #

The four stages are ordered by dependency rather than by importance, and running them out of order produces reports that are technically true and practically useless. Normalization comes first because every later check assumes canonical ids, types and winding. Connectivity comes second because it produces the successor relation that continuity checking needs in order to know which pairs of segments should join. Continuity comes third. Cross-tile alignment comes last because it is the only stage that spans tiles and therefore the only one that needs all three earlier results to be stable.

Run stage three first and the report reads "heading discontinuity at 4 812 joins" — every pair that un-normalized winding put back to front, and none of the real ones. A stage that fails should therefore abort the run rather than continuing: reporting stage four findings against a graph that failed stage one wastes the reviewer's time on artefacts of the earlier failure.

The invariants topology checks cannot see #

Every rule above asks a question about connectivity: does this lane have a successor, does the graph close, is the heading continuous across the join. A lane can satisfy all of them and still be undrivable, because none of them looks at the space the lane occupies.

Three geometric invariants close that gap, and each catches a defect the connectivity rules pass without comment. Width inside the band its road class allows, measured per station rather than per lane — a lane averaging a normal 3.4 m can be 2.1 m wide for eight metres in the middle, and the average hides exactly the stretch a vehicle cannot fit through. Bands have to be per class, because a 2.7 m residential lane is normal and a 2.7 m motorway lane is a defect; one global band accepts both.

No intersection between the bodies of adjacent lanes, measured on centreline-plus-width footprints and suspended inside junction extents, where turn paths are meant to cross. Applying the open-road rule inside a junction reports every junction as broken, which is the fastest way to have a check disabled.

No lane whose body intersects itself, which is what a smoothing or resampling step produces on a hairpin when the deviation budget is comparable to the local radius. The lane still has one start, one end and valid successors, so every connectivity rule passes; the body folds through itself and no vehicle can drive it.

The width check needs one process discipline to stay honest: pin the station spacing and record it with the result. A narrowing found at 1 m sampling and missed at 5 m sampling is not a fixed defect, and a gate whose spacing drifts coarser over time quietly stops finding the thing it was written for.

FAQ #

Should adjacency be measured with Hausdorff distance or a sampled lateral offset? Use Hausdorff for the overlap/crossing test because it captures the symmetric worst-case separation along the whole pair and never under-reports a local breach. For the parallelism check in boundary alignment, a station-sampled lateral offset RMSE is the right metric — it tolerates uniform width while still catching drift. The two are complementary, not interchangeable: Hausdorff alone misses a slow lateral splay that stays under the overlap floor, and offset RMSE alone misses a single sharp crossing.

Why snap endpoints to 1 mm rather than relying on exact coordinate equality? Independently fitted segments almost never share bit-identical endpoints, so exact equality reports spurious dangling_edge faults at every genuine junction. Snapping to a 1 mm grid (round(c, 3) in metres) absorbs sub-millimetre fit drift while staying far below the lane-width floor, so it never merges two distinct nodes. Raising the tolerance toward a few centimetres starts collapsing closely-spaced merge/diverge nodes and silently rewrites topology — keep it tight.

Should curvature violations block the build or only warn? Block them. A curvature spike above 1 / R_min is dynamically infeasible for the platform and injects systematic lateral-controller error, so it is a hard gate shared with the road curvature and superelevation mapping thresholds. The one caveat is undersampling: confirm the spike survives a refit with step ≤ R_min/10 before failing the tile, otherwise you are gating on an aliasing artifact rather than real geometry.

How do I keep cross-tile seams from producing false discontinuities? Normalize every tile into a single engineering grid before any cross-tile pass. Adjacent tiles authored in different UTM zones report apparent breaks at the seam that are pure projection artefacts; resolving them is the same coordinate-discipline problem handled in managing map tile boundaries in ROS 2. Validate seam connectivity only after re-projection, and treat cycle-closure residuals at seams as warnings, not blocking faults.

Related #

• Centerline Generation Algorithms — produces the centerlines this stage validates.
• Road Curvature & Superelevation Mapping — shares the curvature and lateral-acceleration thresholds enforced here.
• Batch Lane Attribute Extraction — the semantic attributes cross-referenced during alignment checks.
• Lane-Level Topology Modeling — the graph substrate the hybrid validator runs against.
• OpenDRIVE Schema Breakdown — schema-conformance gate run before export.

Up one level: Lane Geometry Extraction & Road Network Processing.