Validating Turn Restrictions in Road Graphs

A lane graph can be geometrically perfect and still route a vehicle through an illegal left turn or into oncoming traffic, because turn legality lives in the regulatory layer, not the road shape. This task cross-checks every junction turn edge against the turn restrictions and one-way rules attached to the map, classifies each movement, and gates on any contradiction between geometry and traffic law. It is the regulatory half of topological validation rules, complementing the connectivity checks in detecting dangling lanes and connectivity gaps.

Each geometric turn edge is classified and cross-checked against regulatory relations, and contradictions fail the map:

Prerequisites #

• Python 3.10+, NetworkX 3.2+, NumPy 1.24+.
• Input: a lane graph whose junction edges carry incoming/connecting headings, plus regulatory relations (turn restrictions, one-way flags) keyed to junctions and lanes.
• Upstream stage: turn edges expanded from junction connection matrices; regulatory attributes attached during serialization.
• Output: a list of illegal turn edges and wrong-way movements, empty when the map is compliant.

Step-by-Step #

1. Classify each turn from the heading change #

Compute the signed heading change across each junction edge and bucket it.

import numpy as np

def classify_turn(hdg_in: float, hdg_out: float) -> str:
    d = (hdg_out - hdg_in + 180) % 360 - 180      # wrap to [-180, 180]
    if abs(d) < 20:   return "straight"
    if d >= 20:       return "left"
    if d <= -20:      return "right"
    return "u_turn"                               # |d| near 180

def classify_turn_maybe_u(hdg_in, hdg_out):
    d = (hdg_out - hdg_in + 180) % 360 - 180
    return "u_turn" if abs(abs(d) - 180) < 20 else classify_turn(hdg_in, hdg_out)

Key parameter: the ±20° band separates straight from turning; wrapping to [-180, 180] keeps the sign meaningful regardless of junction orientation.

2. Cross-check turns against permitted movements #

For each junction, the regulatory layer lists permitted movements per incoming lane. Flag any present edge that is not permitted, and any mandatory restriction with no matching absence.

def illegal_turns(g, permitted):
    """permitted[(junction, in_lane)] -> set of allowed turn classes."""
    bad = []
    for u, v, data in g.edges(data=True):
        if data.get("kind") != "junction":
            continue
        turn = classify_turn_maybe_u(data["hdg_in"], data["hdg_out"])
        allowed = permitted.get((data["junction"], u), set())
        if turn not in allowed:
            bad.append((u, v, turn, "not permitted"))
    return bad

Key parameter: permitted maps each incoming lane at a junction to its allowed turn set; an edge whose class is absent is illegal.

3. Catch wrong-way movements #

Independently of turn legality, a turn must not enter a lane against its direction of travel.

def wrong_way(g, lane_direction):
    """lane_direction[lane] -> unit heading of legal travel."""
    bad = []
    for u, v, data in g.edges(data=True):
        entry = data["hdg_out"]                    # heading entering v
        legal = lane_direction[v]
        # dot < 0 => entering against the lane's permitted direction
        if np.cos(np.radians(entry - legal)) < 0:
            bad.append((u, v, "wrong_way"))
    return bad

Key parameter: the cosine of the heading difference is negative when the movement opposes the lane's legal direction — a wrong-way entry.

Verification & Acceptance Criteria #

Gate the map on zero contradictions.

def assert_turns_legal(g, permitted, lane_direction):
    illegal = illegal_turns(g, permitted)
    wrong = wrong_way(g, lane_direction)
    assert not illegal, f"{len(illegal)} illegal turn edge(s): {illegal[:3]}"
    assert not wrong, f"{len(wrong)} wrong-way movement(s): {wrong[:3]}"
    print("turn restrictions honoured: no illegal or wrong-way edges")

Acceptance gate: zero turn edges contradicting a regulatory relation and zero wrong-way movements; every mandatory turn restriction has no corresponding permissive edge. A contradiction is either a missing regulatory attribute or a spurious junction edge — trace it back to the lane successor graph expansion.

Common Errors & Fixes #

A legal turn flagged illegal at an odd-angle junction. The ±20° classification band mislabels a skewed turn. Widen the band per junction geometry, or classify against the junction's own reference directions rather than absolute heading.

Wrong-way false positives on bidirectional lanes. A lane that legally carries both directions has no single legal heading. Exclude bidirectional lanes from the wrong-way check, or test against both permitted directions.

Restrictions silently ignored. The regulatory relations were not loaded, so every geometric turn passes. Assert that junctions with signs have a non-empty permitted entry; an empty regulatory layer should fail the gate, not pass it.

U-turns misclassified as left turns. The 180° case fell into the left bucket. Use the dedicated U-turn test (abs(abs(d) - 180) < 20) before the left/right split.

FAQ #

Why can't turn legality be inferred from geometry alone? #

Geometry tells you a turn is physically possible, not that it is legal. A junction may have the road layout for a left turn while a no-left-turn sign forbids it, or a lane may be right-turn-only despite connecting geometrically to a through lane. Those constraints live in regulatory relations — sign and marking semantics — not in the road shape, so validating turns means comparing the geometric turn edges against the regulatory layer, and flagging where they disagree.

How is a turn classified as left, right, or straight? #

By the signed heading change between the incoming lane's exit heading and the connecting lane's entry heading. A large positive change is a left turn, a large negative change a right turn, a near-zero change is straight, and a change near 180 degrees is a U-turn. Using the heading change rather than absolute geometry makes the classification robust to the junction's orientation in the map.

What is a wrong-way movement and how is it caught? #

A wrong-way movement is a turn edge that enters a lane against its legal direction of travel, for example turning into the exit lanes of a one-way street. It is caught by checking each turn edge's target lane against that lane's one-way attribute and driving direction: if the edge would place the vehicle travelling opposite to the lane's permitted direction, it is illegal regardless of whether the turn itself is allowed.

Related #

• Detecting Dangling Lanes and Connectivity Gaps — the connectivity sibling check on the same graph.
• Building Lane Successor Graphs from OpenDRIVE — the junction expansion that produces the turn edges checked here.
• Building Routable Road-Network Graphs from HD Maps — the router that relies on turn edges being legal.

Up one level: Topological Validation Rules — the parent workflow of connectivity and regulatory checks this turn validation completes.