VehicleMapping HD AV Spatial Data

Building Routing Graphs from OpenDRIVE Junctions

The graph produced in road network graph construction routes cleanly along roads and stops at junctions unless the junction interior is expanded into it. The tempting shortcut is one edge per movement, straight from the incoming lane to the outgoing lane, treating the junction as a hop. That shortcut discards the interior geometry, so the route's length is wrong, the turn's curvature is unavailable, and there is nowhere to record that two movements cross.

This task expands junctions properly: a node per connecting-road lane, two edges per movement, conflict annotations on the interior pairs, and a reachability gate.

The two expansions, and what the collapsed one cannot express:

Collapsed against Expanded Junction Representation Two graph fragments for the same movement, one a single hop edge and one with an interior connecting-road node carrying geometry, cost and conflict annotations. collapsed — one edge across the junction incoming outgoing no interior length, curvature or conflict slot expanded — a node per connecting-road lane incoming connecting lane outgoing conflict with movement 7 at s = 4.2 m length, curvature and conflicts all attach here the extra node costs one entry per movement and makes three otherwise unanswerable questions answerable

Prerequisites #

  • Python 3.10+, networkx 3.x, shapely 2.0+.
  • Input: the movement list from modelling OpenDRIVE junction connections in Python and the synthesised turn paths.
  • Upstream stage: the road-level graph, with nodes for ordinary lanes already present.
  • Output: the same graph with junction interiors routable and conflicts annotated.

Step-by-Step #

1. Create a node per connecting-road lane #

python
def add_connecting_nodes(G, movements, paths) -> int:
    added = 0
    for mv in movements:
        node = ("conn", mv.connecting_road, mv.connecting_lane)
        if node in G:
            continue
        path = paths[mv.id]
        G.add_node(node, kind="junction_interior",
                   length=path_length(path),
                   curvature=peak_curvature(path),
                   junction=mv.junction)
        added += 1
    return added

Several movements can share a connecting-road lane — a two-lane connecting road serves two movements from each of two incoming lanes — so the node is created once and keyed on the road and lane rather than on the movement.

2. Add the two edges per movement #

python
def add_movement_edges(G, movements) -> None:
    for mv in movements:
        entry = ("lane", mv.incoming_road, mv.incoming_lane)
        interior = ("conn", mv.connecting_road, mv.connecting_lane)
        exit_ = ("lane", mv.outgoing_road, mv.outgoing_lane)
        G.add_edge(entry, interior, kind="junction_entry", movement=mv.id)
        G.add_edge(interior, exit_, kind="junction_exit", movement=mv.id)

Both edges carry the movement identifier, which is what lets a route be translated back into a list of movements the planner can reason about — and what makes a conflict annotation on the interior resolvable to the two movements involved.

3. Annotate conflicts rather than adding edges #

python
from shapely.geometry import LineString

def annotate_conflicts(G, movements, paths, tol_m: float = 0.5) -> int:
    found = 0
    for i, a in enumerate(movements):
        la = LineString(paths[a.id])
        for b in movements[i + 1:]:
            if a.junction != b.junction or a.incoming_lane == b.incoming_lane:
                continue
            lb = LineString(paths[b.id])
            hit = la.intersection(lb)
            if hit.is_empty:
                continue
            pt = hit if hit.geom_type == "Point" else hit.centroid
            G.nodes[("conn", a.connecting_road, a.connecting_lane)] \
                .setdefault("conflicts", []).append(
                    {"with": b.id, "s_self": la.project(pt), "s_other": lb.project(pt)})
            found += 1
    return found

Movements sharing an incoming lane diverge rather than conflict, so they are excluded — otherwise every junction reports its own fan-out as a conflict and the annotation becomes noise.

4. Verify reachability across the junction #

python
import networkx as nx

def unreachable_pairs(G, junction_id, movements) -> list[tuple]:
    entries = {("lane", m.incoming_road, m.incoming_lane)
               for m in movements if m.junction == junction_id}
    exits = {("lane", m.outgoing_road, m.outgoing_lane)
             for m in movements if m.junction == junction_id}
    legal = {(("lane", m.incoming_road, m.incoming_lane),
              ("lane", m.outgoing_road, m.outgoing_lane))
             for m in movements if m.junction == junction_id}
    return [(u, v) for u, v in legal if not nx.has_path(G, u, v)]

Every legal movement must survive the expansion as a path. A non-empty result means an edge was dropped somewhere between the connection record and the graph, which no local check will find.

What reachability catches that node and edge counts do not:

A Mis-Signed Connecting Lane, Visible Only Through Reachability A junction reachability matrix with one blocked entry, alongside unchanged node and edge counts. N exitE exit S exitW exit N approachE approach S approachW approach unreachable node and edge counts unchanged one legal movement is now unroutable

Verification & Acceptance Criteria #

python
def assert_junction_graph(G, movements) -> None:
    for j in {m.junction for m in movements}:
        bad = unreachable_pairs(G, j, movements)
        assert not bad, f"junction {j}: {len(bad)} unreachable legal movement(s)"

    for n, d in G.nodes(data=True):
        if d.get("kind") != "junction_interior":
            continue
        assert d["length"] > 0, f"{n}: interior node with zero length"
        assert G.in_degree(n) and G.out_degree(n), f"{n}: interior node is a dead end"

    for _, d in G.nodes(data=True):
        for c in d.get("conflicts", []):
            assert 0 <= c["s_self"] <= d["length"], "conflict station outside the path"

Acceptance gate: zero unreachable legal movements at every junction; every interior node with positive length and both an in-edge and an out-edge; and every conflict station inside its path's extent, which is the cheap proof the projection used the right geometry.

What each junction representation can and cannot answer:

Questions Each Junction Representation Can Answer Four rows pairing a planner question with whether a collapsed and an expanded junction representation can answer it. four planner questions, two representations how long is the route through? interior length collapsed: no · expanded: yes expansion needed how tight is the turn? interior curvature collapsed: no · expanded: yes expansion needed what does it cross? conflict annotations collapsed: nowhere to put them expansion needed is every movement still routable? reachability checkable either way the catch-all check the fourth question is the one that finds a dropped edge, and it is the only one a collapsed graph can still answer

Common Errors & Fixes #

Routes through junctions are shorter than reality. The junction was collapsed to a single edge, so the interior length is missing. Expand as in step 1.

Every junction reports dozens of conflicts. Movements sharing an incoming lane are being compared. Exclude them; a fan-out is not a conflict.

A legal movement is unroutable. Usually a mis-signed connecting lane, so the exit edge names a lane that does not exist. Check the contact-point sign before checking the graph code.

Conflict stations are all zero. The projection is being taken against the wrong path — project was called on the other movement's geometry. Project each station against its own path.

Interior nodes accumulate across releases. Nodes are keyed on movement rather than on connecting road and lane, so a re-run with reordered movements creates duplicates. Key on the road and lane.

FAQ #

Why put nodes inside the junction rather than one edge across it? #

Because the junction interior has geometry, cost and conflicts of its own, and a single edge across it has nowhere to carry them. With a node per connecting-road lane, the interior path is a first-class part of the route: its length contributes to travel cost, its curvature is checkable, and a conflict can be located at a station along it. Collapsing the junction to one edge makes every one of those questions unanswerable at planning time.

What does the reachability check actually catch? #

Junctions that became one-way by accident. A missing laneLink row, a mis-signed connecting lane or a dropped connection record all produce a graph that is structurally valid and in which some approach can no longer reach some exit. Reachability is the only check that sees this, because every local check passes: the edges that exist are all correct, and the fault is in the edges that do not.

Should conflicts be edges or annotations? #

Annotations. A conflict is not a movement — nobody drives it — so making it an edge corrupts every routing query with paths that cross from one turn onto another. Recording it as an attribute on the pair of edges, with the station along each, gives the planner what it needs without making the graph claim something false about connectivity.

Up one level: Road Network Graph Construction — the graph this expansion completes.