VehicleMapping HD AV Spatial Data

Resolving Lane-Change and Neighbour Links

The successor graph built in building lane successor graphs from OpenDRIVE answers where a vehicle can go forward. It says nothing about sideways, and a planner without lateral edges cannot express an overtake, a merge onto a slip road, or a lane change to reach an exit.

Adding those edges is mostly bookkeeping with one genuine subtlety: legality is a property of the marking between two lanes, the marking can differ by side, and it can change partway along a lane. This task resolves all three for lane-level topology modeling.

Why the lane has to be split rather than the edge conditioned:

Splitting a Lane at a Marking Transition Top: one lane node spanning a solid and a dashed marking section, with both possible edge answers marked wrong. Bottom: the same lane split into two nodes, each with a single correct answer. one node solid · 60 m dashed · 90 m a single node — one edge answer for 150 m, wrong over half of it split at the transition node A — no lane-change edge node B — lane-change edge, both directions split here splitting costs one extra node and removes a positional condition from every consumer of the graph

Prerequisites #

  • Python 3.10+, networkx 3.x, and the successor graph from the parent guide.
  • Input: lane sections with signed lane ids, per-lane road-mark records with an s offset, and the section's own extent.
  • Upstream stage: node creation and successor linking; lateral edges are added to an existing graph.
  • Output: the same graph with lane_change edges carrying a direction and a reason.

Step-by-Step #

1. Derive neighbours from lane-id adjacency #

python
def neighbours(section) -> dict[int, dict[str, int]]:
    """Left and right neighbour lane ids within one lane section."""
    right = sorted((l.id for l in section.lanes if l.id < 0), reverse=True)
    left = sorted(l.id for l in section.lanes if l.id > 0)

    out: dict[int, dict[str, int]] = {}
    for run in (right, left):
        for inner, outer in zip(run, run[1:]):
            out.setdefault(inner, {})["outer"] = outer
            out.setdefault(outer, {})["inner"] = inner
    return out

Lane ids increase outward from the reference line on each side, so adjacency is ordering rather than geometry. Note that lane −1 and lane +1 are not neighbours for lane-change purposes — they are separated by the reference line and normally by opposing traffic.

2. Split lanes where the separating marking changes #

python
def split_stations(lane, section_length: float, tol: float = 0.01) -> list[float]:
    """Stations at which this lane's road-mark subtype changes."""
    marks = sorted(lane.road_marks, key=lambda m: m.s_offset)
    cuts = [m.s_offset for a, m in zip(marks, marks[1:])
            if (m.type, m.weight) != (a.type, a.weight)]
    return [0.0, *[c for c in cuts if tol < c < section_length - tol],
            section_length]

Cuts within tol of either end are dropped: a marking record that starts at the lane's own start is not a transition. Expected output: the station list that defines the split nodes, always containing at least the two endpoints.

3. Gate each direction on the marking side #

python
PERMITS = {
    ("broken", "broken"): ("in", "out"),
    ("solid", "solid"): (),
    ("broken", "solid"): ("out",),     # dashed side may cross toward solid
    ("solid", "broken"): ("in",),
}

def permitted_directions(mark) -> tuple[str, ...]:
    """Which crossing directions this road mark allows, by side."""
    key = (mark.inner_side, mark.outer_side)
    if key not in PERMITS:
        raise KeyError(f"unmapped marking pair {key!r} — decide before linking")
    return PERMITS[key]

Raising on an unmapped pair rather than defaulting to symmetric is deliberate: a marking combination nobody has classified is a decision, and the default that "feels safe" — permitting both — is the unsafe one.

4. Emit one directed edge per permitted direction #

python
def add_lane_change_edges(G, section, marks) -> int:
    added = 0
    for lane_id, rel in neighbours(section).items():
        outer = rel.get("outer")
        if outer is None:
            continue
        for direction in permitted_directions(marks[lane_id]):
            src, dst = ((lane_id, outer) if direction == "out"
                        else (outer, lane_id))
            G.add_edge(node_of(section, src), node_of(section, dst),
                       kind="lane_change", reason=marks[lane_id].type)
            added += 1
    return added

Recording reason on the edge is what makes the graph reviewable later: an edge whose justification is a marking type can be checked against the survey, and one with no reason cannot.

The marking cases, and the one that a symmetric implementation gets wrong:

Separating-Marking Cases and the Edges Each Produces Four panels showing marking combinations between two lanes with the directed edges each permits. broken / broken solid / solid broken inner / solid outer solid inner / broken outer 2 edges0 edges 1 edge, outward1 edge, inward a symmetric add_edge pair gets both of these wrong and they are common at exits and beside hard shoulders

Where the lateral edges come from, and the one place a geometric test is still needed:

Source of Each Piece of Lateral Information Four rows pairing a lateral-topology question with its source and whether geometry is involved. four questions, three of which the schema already answers which lanes are neighbours adjacency within a section lane-id ordering, same sign no geometry is a change permitted per direction road-mark subtype, per side no geometry where does that change partway along the lane road-mark station offsets no geometry are they physically adjacent an id gap can hide a lane the only geometric check needed distance test deriving the first three geometrically re-answers questions the file has already answered, and does so less reliably

Verification & Acceptance Criteria #

python
def assert_lane_change_edges(G, sections) -> None:
    for u, v, d in G.edges(data=True):
        if d.get("kind") != "lane_change":
            continue
        assert d.get("reason"), f"edge {u}->{v} has no marking justification"
        assert G.nodes[u]["section"] == G.nodes[v]["section"], \
            "lane-change edge crosses a lane section"
        assert abs(G.nodes[u]["lane_id"] - G.nodes[v]["lane_id"]) == 1, \
            "lane-change edge skips a lane"
        assert G.nodes[u]["lane_id"] * G.nodes[v]["lane_id"] > 0, \
            "lane-change edge crosses the reference line"

    asym = [(u, v) for u, v, d in G.edges(data=True)
            if d.get("kind") == "lane_change" and not G.has_edge(v, u)]
    assert asym, "no asymmetric lane-change edges — the marking side is being ignored"

Acceptance gate: every lane-change edge justified by a marking; adjacent lane ids only; never crossing the reference line or a section boundary; and — on any real motorway map — at least one asymmetric pair, which is the check that proves the per-side logic is running rather than a symmetric shortcut.

Common Errors & Fixes #

Every lane-change edge is bidirectional. The marking is being read once for the boundary rather than per side. Read inner_side and outer_side separately.

A lane change is legal along a whole lane that is solid at its start. The lane was not split at the marking transition. Add the split stations before creating nodes.

Lane −1 links to lane +1. The sign check is missing. Neighbours are within a side; the reference line is not a crossable boundary.

An unknown marking combination silently permits both directions. PERMITS defaulted. Restore the raise and classify the new combination explicitly.

Routing takes six lane changes to save two metres. The edges are correct and uncosted. Add the manoeuvre penalty described in road network graph construction.

FAQ #

Why are neighbours derived from lane ids rather than from geometry? #

Because within a lane section the schema already states the ordering: lane ids increase outward from the reference line on each side, so lane minus two's left neighbour is lane minus one by definition. Deriving it geometrically re-answers a question the file has already answered, and does so unreliably — on a widening carriageway the nearest lane by centreline distance is not always the adjacent one.

Why split a lane where the marking changes? #

Because a lane-change edge is a claim about a whole node, and a lane whose separating marking is solid for its first sixty metres and dashed afterwards cannot honestly carry either answer. Splitting the lane at the transition gives two nodes, each of which has one true answer. The alternative — a single node with a positional condition on the edge — pushes the check into every consumer instead of resolving it once.

When is a lane-change edge one-directional? #

Whenever the separating marking differs by side, which is common at motorway exits and on lanes adjacent to a hard shoulder. A combined solid-and-dashed line permits the change from the dashed side toward the solid side only. Emitting a symmetric pair of edges by default gets this wrong in exactly the places where being wrong matters, and the error is invisible to any geometric check.

Up one level: Lane-Level Topology Modeling — the topology stage these lateral edges complete.