Detecting Dangling Lanes and Connectivity Gaps

A single lane that dead-ends where a successor should exist strands every route that enters it, and the vehicle discovers the defect at runtime unless the map is checked first. This task walks the lane graph in NetworkX to find the three failure shapes — interior dead-ends, unreachable islands, and near-miss endpoint gaps — and separates genuine map-boundary dangles from real defects. It is the core check of topological validation rules, operating on the graph produced by building lane successor graphs from OpenDRIVE.

Three connectivity defects — interior dead-end, unreachable island, near-miss gap — are found and classified:

Prerequisites #

• Python 3.10+, NetworkX 3.2+, Shapely 2.0+ (STRtree), NumPy 1.24+.
• Input: a directed lane-successor graph with node geometry (endpoints, heading) and a polygon of the mapped region's outer boundary.
• Upstream stage: the graph is built and passes basic structural checks; endpoints are in one projected CRS.
• Output: classified lists of interior dead-ends, isolated components, and candidate near-miss stitches.

Step-by-Step #

1. Find dead-ends and separate boundary from interior #

A dead-end has out-degree zero. Keep only those in the interior of the mapped region — boundary dead-ends are legitimate.

import networkx as nx

def interior_dead_ends(g: nx.DiGraph, boundary_polygon, margin=2.0):
    """Out-degree-0 lanes whose endpoint is not near the mapped boundary."""
    dead = [n for n in g if g.out_degree(n) == 0]
    return [n for n in dead
            if boundary_polygon.exterior.distance(_endpoint(g, n)) > margin]

Key parameter: margin is the distance from the boundary within which a dead-end is treated as a legitimate map edge; interior dead-ends beyond it are defects.

2. Find unreachable islands #

Compute weakly connected components; every component but the largest is an island. Small islands far from the core are almost always defects.

def islands(g: nx.DiGraph, min_core_frac=0.5):
    comps = sorted(nx.weakly_connected_components(g), key=len, reverse=True)
    core = comps[0] if comps else set()
    return [c for c in comps[1:] if len(c) < min_core_frac * len(core)]

Key parameter: min_core_frac guards against flagging a legitimately separate sub-network; only components much smaller than the core are reported.

3. Find near-miss endpoint gaps #

Two endpoints within the stitch tolerance, with agreeing heading, were probably meant to connect. Use a spatial index to find them efficiently.

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

def near_miss_gaps(endpoints, headings, tol=0.5, heading_tol_deg=10.0):
    pts = [Point(*p) for p in endpoints]
    tree = STRtree(pts)
    gaps = []
    for i, p in enumerate(pts):
        for j in tree.query(p.buffer(tol)):
            if j > i and p.distance(pts[j]) <= tol and \
               abs(headings[i] - headings[j]) <= heading_tol_deg:
                gaps.append((i, j, p.distance(pts[j])))
    return gaps

Key parameters: tol (0.5 m) is the maximum gap to consider a stitch candidate; heading_tol_deg prevents pairing endpoints that are close but point in unrelated directions.

Verification & Acceptance Criteria #

Gate the map on zero unexplained defects.

def assert_connectivity(g, boundary, endpoints, headings):
    dead = interior_dead_ends(g, boundary)
    isl = islands(g)
    gaps = near_miss_gaps(endpoints, headings)
    assert not dead, f"{len(dead)} interior dead-end lane(s)"
    assert not isl, f"{len(isl)} unreachable island(s)"
    assert not gaps, f"{len(gaps)} near-miss gap(s) to review"
    print("connectivity clean: no interior dead-ends, islands, or gaps")

Acceptance gate: zero interior dead-ends, zero unreachable islands, and zero unresolved near-miss gaps; every reported dangle either sits on the mapped boundary or has a documented reason. Near-miss gaps must be resolved — stitched after a 3D height check, or explicitly marked as a true discontinuity.

Common Errors & Fixes #

Every boundary lane flagged as a dead-end. The boundary polygon is missing or the margin is too small. Supply the mapped-region outer boundary and set margin to a couple of metres so legitimate edges are excluded.

Overpass lanes auto-stitched into a false connection. A near-miss gap in plan view ignored height — two lanes cross at an overpass. Add a height check before proposing a stitch; require the endpoints be close in 3D, not just in 2D.

A legitimately separate lot flagged as an island. A private parking area is genuinely disconnected. Tune min_core_frac, and maintain an allowlist of known-separate components rather than forcing an edge.

Slow on large maps. The near-miss search is O(n²) without an index. Use the STRtree query as shown; it keeps the gap search near-linear, the same indexing used in joining lane attributes across map tiles.

FAQ #

What is a dangling lane? #

A dangling lane is one that ends without connecting to anything — no successor, and not because it reaches the edge of the mapped area. Some dead-ends are legitimate: a lane that runs to the boundary of the tile set, or a genuine cul-de-sac. The defect is a lane that dead-ends in the middle of a road network where a successor should exist, which strands any route that enters it.

How do you tell a real gap from a mapped boundary? #

By location and geometry. A boundary dead-end sits on the convex edge of the mapped region and points outward; a defect dead-end sits in the interior with drivable space continuing beyond it. Near-miss gaps are the clearest defects: two lane endpoints within a stitch tolerance of each other, aligned in heading, that were simply never linked. Those are almost always an extraction miss, not a real discontinuity in the road.

Should the tool auto-stitch near-miss gaps? #

It can propose a stitch but should not silently apply one. A gap within tolerance with matching heading is a strong candidate to link, but auto-stitching risks connecting two lanes that are close by accident, for example at an overpass where lanes cross in plan but not in height. The safe pattern is to emit candidate stitches for review or apply them only when a 3D check confirms the endpoints are also close in height.

Related #

• Validating Turn Restrictions in Road Graphs — the regulatory-rule sibling check on the same graph.
• Building Lane Successor Graphs from OpenDRIVE — the graph this validation consumes.
• Building Routable Road-Network Graphs from HD Maps — the routing layer whose reachability depends on these checks passing.

Up one level: Topological Validation Rules — the parent workflow of connectivity and regulatory checks this dead-end detection anchors.