Building a Routing Graph from Room Polygons

The end-to-end implementation behind Indoor Routing Graph Construction: one function that takes a validated envelope and returns either a graph a router can use or a named reason it cannot.

What the Function Has to Guarantee #

Graph construction is easy to write and easy to write badly, and the difference is entirely in what the function promises. Three guarantees are worth building around:

1. It never returns an unusable graph. A disconnected graph is a failure, not a result with a warning attached. Anything that logs and continues will eventually publish a building with a stranded wing.
2. Paths stay inside the building. Every edge between a space and the circulation network goes through an opening, which means a door node and a spur — never a direct join from a room’s interior point to the nearest skeleton vertex.
3. It is deterministic. The same envelope produces the same graph, node ids included, because the graph’s hash feeds the content-addressed version that decides whether caches are purged.

Minimal Working Example #

The whole build, for one building, with the guarantees above enforced:

import hashlib
import json
import logging
from dataclasses import dataclass

import networkx as nx
from shapely.geometry import Point, Polygon, shape

logging.basicConfig(level=logging.INFO, format="%(asctime)s [%(levelname)s] %(message)s")
logger = logging.getLogger(__name__)


class GraphNotRoutable(RuntimeError):
    """Raised when the assembled graph cannot serve routes; never downgraded to a warning."""


@dataclass(frozen=True)
class BuildResult:
    graph: nx.Graph
    graph_hash: str
    stats: dict


def build_graph(envelope: dict, transitions: list[dict], *, step: float = 0.35,
                spur_len: float = 0.6, merge_doors: float = 0.4) -> BuildResult:
    """Assemble and verify a building's routing graph from a validated envelope."""
    features = envelope.get("features", [])
    if not features:
        raise ValueError("empty envelope: nothing to build a graph from")

    spaces: dict[float, dict[str, Polygon]] = {}
    openings: dict[float, list[dict]] = {}
    for f in features:
        props, level = f["properties"], float(f["properties"]["level"])
        if props.get("space_class") == "door":
            pt = shape(f["geometry"]).representative_point()
            openings.setdefault(level, []).append(
                {"id": props["feature_id"], "x": pt.x, "y": pt.y,
                 "width": props.get("width_m", 0.9),
                 "space_a": props.get("space_a"), "space_b": props.get("space_b")})
        elif props.get("is_routable"):
            spaces.setdefault(level, {})[props["feature_id"]] = shape(f["geometry"])

    g = nx.Graph()
    for level, polys in sorted(spaces.items()):
        doors = _merge_close(openings.get(level, []), merge_doors)
        g = nx.compose(g, build_level_graph(polys, doors, level, step=step, spur=spur_len))
    g = add_vertical_edges(g, transitions)

    stats = verify(g)
    if not stats["ok"]:
        raise GraphNotRoutable(
            f"{stats['components']} component(s), "
            f"{stats['unreachable_spaces']} unreachable space(s)")

    payload = json.dumps(
        {"nodes": sorted(g.nodes()), "edges": sorted(map(sorted, g.edges()))},
        separators=(",", ":"))
    graph_hash = hashlib.sha256(payload.encode()).hexdigest()[:16]
    logger.info("graph ok: %d nodes, %d edges, hash %s",
                g.number_of_nodes(), g.number_of_edges(), graph_hash)
    return BuildResult(g, graph_hash, stats)


def _merge_close(openings: list[dict], tol: float) -> list[dict]:
    """Collapse double doors into one node so instructions do not say 'turn' twice."""
    out: list[dict] = []
    for op in sorted(openings, key=lambda o: (o["x"], o["y"])):
        if out and Point(op["x"], op["y"]).distance(Point(out[-1]["x"], out[-1]["y"])) < tol:
            out[-1]["width"] += op["width"]
            continue
        out.append(dict(op))
    if len(out) != len(openings):
        logger.info("merged %d double-door opening(s)", len(openings) - len(out))
    return out

Two details in that function do more work than their line count suggests. The hash is computed over sorted node and edge ids, not over the object, so it is stable across dictionary ordering and Python versions. And the door merge runs before node placement, so a pair of double doors becomes one node with a combined width rather than two nodes 0.3 m apart that generate a spurious turn instruction between them.

Node Placement and the Spur #

The spur is the smallest part of the build and the one that decides whether routes look right.

A door node sits on the opening — the centre of the gap in the wall. A space node sits at the room’s representative point. Joining the two directly is correct. Joining the space node directly to the corridor skeleton is not, because the straight line between them passes through the wall face beside the door, and that line is what gets rendered.

So each door node gets two edges: one to the space it serves, and one to the nearest point on the corridor skeleton, perpendicular where possible. The spur length is short — 0.6 m is typical, being roughly half a corridor width — and it is charged as real distance, because it is.

The other placement rule worth stating explicitly: junction nodes come from the skeleton, not from the rooms. Where the medial axis branches, a node is created, and that node is what a turn-by-turn generator uses to emit “turn left”. A graph without junction nodes can route perfectly and cannot give directions.

Parameter Reference #

strict exists as a parameter only so that diagnostic tooling can inspect a broken graph. It must be True in the build path, and the CI gate should assert that it is — a flag that can be flipped to make a failing build pass will eventually be flipped.

Common Errors & Fixes #

GraphNotRoutable: 2 component(s). The commonest cause is an opening whose space_a or space_b reference does not resolve, so a room was never joined to the corridor. Print the component sizes and the space ids in the smaller one; the answer is usually a single door feature whose reference was dropped upstream.

Every route is a few metres longer than the walk. The densification step is too coarse and the skeleton is cutting corners. The chart above quantifies it: at a 1 m step, route length under-reports by 1.4 m per corner, which compounds across a long route into a visible discrepancy between the estimate and the walk.

Instructions say “turn” in the middle of a straight corridor. Junction nodes are being created by skeleton noise rather than by real branches. Simplify each skeleton segment before adding it — seg.simplify(0.05, preserve_topology=True) removes the wobble the Voronoi introduces without moving the centreline perceptibly.

The graph hash changes on every build with identical input. Node ids are being generated from unordered iteration or from object identity. Derive them from coordinates (rounded) or from stable feature_id values, and sort before hashing — the assertion is worth automating:

def test_graph_hash_is_stable(envelope, transitions):
    a = build_graph(envelope, transitions).graph_hash
    b = build_graph(envelope, transitions).graph_hash
    assert a == b, "graph construction is not deterministic; caches will churn"

Integration Point #

This build runs after geometry cleanup has produced non-overlapping room polygons and after level mapping has assigned every feature a level. Its output is consumed by accessible routing profiles, which apply weights at query time, and by fallback routing architectures, whose reconciliation tier snaps drifted endpoints onto exactly these nodes.

The graph_hash it returns joins the topology_hash in the published artifact, and the CI gate runs verify again on the candidate before promotion — the same check, run twice, because the build machine and the gate are allowed to disagree and it is much cheaper to find out there than in production.

Frequently Asked Questions #

Related #

• Indoor Routing Graph Construction — the architecture this implementation follows.
• Placing Nodes at Doors and Corridor Junctions — the placement rules in detail, including double doors and thresholds.
• NetworkX vs. igraph for Large Indoor Routing Graphs — when the graph this builds outgrows the library it is built in.

This page is a companion to Indoor Routing Graph Construction, part of the Indoor Mapping Architecture & Standards section.