Enforcing Lane Width and Overlap Invariants

The checks in topological validation rules answer questions about connectivity: does this lane have a successor, does the graph close, is the heading continuous. A lane can pass all of them and still be undrivable, because none of them looks at the space the lane occupies.

This task adds the three invariants that do: width inside the band its road class allows, no intersection between the bodies of adjacent lanes, and no lane whose body intersects itself.

The three defects, and why the topology checks are blind to all of them:

Prerequisites #

• Python 3.10+, NumPy 1.24+, shapely 2.0+ with an STRtree.
• Input: lane centrelines with per-station width, road class per lane, and the junction extents.
• Upstream stage: centerline generation and smoothing; these invariants check their output.
• Output: findings with a lane identifier, a station and a measured value.

Step-by-Step #

1. Sample width per station #

import numpy as np

def width_profile(lane, spacing_m: float = 1.0) -> tuple[np.ndarray, np.ndarray]:
    """Width sampled at fixed stations along the lane."""
    s = np.arange(0.0, lane.length, spacing_m)
    w = np.array([lane.width_at(x) for x in s])
    return s, w

Sampling at a metre keeps an eight-metre narrowing from falling between samples while staying cheap: a national map is a few hundred million samples, which is one pass over a columnar array.

2. Band by road class #

WIDTH_BAND_M = {
    "motorway": (3.25, 3.90),
    "primary": (2.90, 3.75),
    "residential": (2.60, 3.50),
    "service": (2.30, 3.40),
}

def width_findings(lane, spacing_m: float = 1.0) -> list[dict]:
    lo, hi = WIDTH_BAND_M[lane.road_class]
    s, w = width_profile(lane, spacing_m)
    bad = np.flatnonzero((w < lo) | (w > hi))
    return [{"lane": lane.id, "s": float(s[i]), "width": float(w[i]),
             "band": (lo, hi)} for i in bad]

Bands per class rather than one global range: a 2.7 m residential lane is normal and a 2.7 m motorway lane is a defect, and a single band either accepts both or rejects both.

3. Test adjacent lane bodies for intersection #

from shapely.geometry import LineString
from shapely.strtree import STRtree

def overlap_findings(lanes, junction_extents) -> list[dict]:
    bodies = {l.id: LineString(l.centreline).buffer(l.mean_width / 2.0,
                                                   cap_style=2) for l in lanes}
    tree = STRtree(list(bodies.values()))
    ids = list(bodies)
    out = []
    for i, lid in enumerate(ids):
        for j in tree.query(bodies[lid]):
            other = ids[j]
            if other <= lid:
                continue
            inter = bodies[lid].intersection(bodies[other])
            if inter.is_empty or any(e.contains(inter) for e in junction_extents):
                continue
            out.append({"lanes": (lid, other), "area_m2": inter.area})
    return out

The junction-extent exclusion is essential: turn paths are meant to cross, and applying the open-road rule inside a junction reports every junction as broken.

4. Detect self-overlap #

def self_overlap_findings(lanes) -> list[dict]:
    out = []
    for l in lanes:
        line = LineString(l.centreline)
        if not line.is_simple:
            out.append({"lane": l.id, "reason": "centreline self-intersects"})
            continue
        body = line.buffer(l.mean_width / 2.0, cap_style=2)
        if body.geom_type == "MultiPolygon" or not body.is_valid:
            out.append({"lane": l.id, "reason": "body is not a simple polygon"})
    return out

is_simple on the centreline catches the outright fold; the buffered-body check catches the near-fold, where the centreline does not quite cross itself but the lane body does. Both come from the same cause — smoothing on a hairpin with a deviation budget comparable to the radius.

Where the width band sits relative to real road classes, and why one band cannot serve all of them:

Verification & Acceptance Criteria #

def assert_geometry_invariants(lanes, junction_extents) -> list[dict]:
    findings = []
    for l in lanes:
        findings += width_findings(l)
    findings += overlap_findings(lanes, junction_extents)
    findings += self_overlap_findings(lanes)
    return findings

Acceptance gate: zero self-overlaps, which are never acceptable; zero adjacent-lane body intersections outside junction extents; and width findings only where a survey note records a genuine narrowing, with every unexplained finding blocking the release. The width check runs at 1 m stations, and the gate records the spacing so a later run at a coarser spacing cannot silently pass more.

Which stage each geometric defect comes from, which is where the fix belongs:

Common Errors & Fixes #

Every junction reports overlapping lanes. Junction extents are not being excluded. Exclude them; turn paths are expected to cross.

A narrowing is reported that a surveyor confirms is real. Correct behaviour — record the exemption against the lane rather than widening the band, so the next unexplained narrowing is still caught.

Self-overlap appears only after smoothing. The deviation budget is comparable to the local radius at a hairpin. Reduce the budget on high-curvature segments rather than disabling the check.

Width findings vanish when the pipeline is re-run. The station spacing was coarsened, so the narrow stretch now falls between samples. Pin the spacing and record it with the result.

The overlap test is slow on a dense tile. Pairwise comparison without an index. Build the STRtree once and query it, as in step 3.

FAQ #

Why check width per station rather than per lane? #

Because a lane that is 3.4 metres wide on average can be 2.1 metres wide for eight metres in the middle, and the average hides exactly the stretch a vehicle cannot fit through. Per-station sampling turns the check into a profile with a location, which is what a surveyor needs, and lets the gate distinguish a genuine narrowing — a construction taper — from an extraction error that pinches one station.

Should adjacent lanes ever overlap? #

Their bodies, no; their swept corridors at a junction, yes and necessarily. That is why the overlap test runs on lane bodies derived from centreline and width on open road, and is suspended inside junction extents where turn paths are expected to cross. Applying the open-road rule inside a junction reports every junction as broken, which is the fastest way to have the check disabled.

What causes a lane to overlap itself? #

A smoothing or resampling step that moved vertices far enough for the centreline to fold back on itself, usually on a hairpin where the deviation budget is comparable to the radius. The result is a lane whose body self-intersects, which every topology check passes — the lane has one start, one end and valid successors — and which no vehicle can drive. A self-intersection test on the buffered body is the only cheap way to find it.

Related #

• Detecting Dangling Lanes and Connectivity Gaps — the connectivity half of the same validation stage.
• Smoothing Centerlines with Quadratic Programming — the stage whose budget causes most self-overlaps.
• Validating Intersection Drivable Area — the containment reasoning inside the extents this check excludes.

Up one level: Topological Validation Rules — the validation stage these invariants extend.