Indoor Routing Graph Construction

Everything upstream produces geometry; a router needs a graph. This topic, part of Indoor Mapping Architecture & Standards, covers the conversion: turning validated room polygons and openings into nodes and weighted edges that a shortest-path solve can run over, and proving the result is connected before anyone tries to navigate on it.

The Problem: Areas Are Not a Network

A floor plan describes bounded areas. A router needs a network: discrete positions and the traversable connections between them, with costs. Nothing in the geometry says where those positions should be, and the choice determines both what a route looks like on the map and whether turn-by-turn instructions are usable.

Four ways to build an indoor routing graph, compared A grid comparing four graph-construction approaches. Room-centroid graphs have about 40 nodes on a typical floor and build instantly, but paths visually cut through walls, wide spaces are not handled and turn-by-turn quality is poor. Medial-axis graphs have about 740 nodes, follow corridors naturally, cost moderate build time, collapse wide spaces to a single line, and give good turn-by-turn. Visibility graphs have about 2,100 nodes and quadratic build cost but give direct lines and handle wide spaces. Navmeshes have about 310 nodes, moderate cost, natural paths and good turn-by-turn, and suit large open floors. Four approaches, and the cheapest one is the one users notice Property Room-centroid Medial axis Visibility graph Navmesh Node count (typical floor) ● 40 740 △ 2,100 310 Path realism △ cuts through walls visually ● follows corridors ● direct lines ● natural Build cost ● instant moderate △ O(n²) visibility moderate Handles wide spaces △ no △ collapses to a line ● yes ● yes Turn-by-turn quality △ poor ● good moderate ● good Where it fits quick prototypes ● corridor buildings open concourses large open floors Most indoor estates are corridor buildings, which is why the medial axis is the default.

The first column is a trap worth naming. A room-centroid graph is ten minutes' work and routes correctly in the graph-theoretic sense, while drawing a line through three walls on the map — which reads to a user as a broken product.

The room-centroid graph deserves a specific warning because it is what most first implementations produce. Every room becomes one node, every shared opening becomes an edge, and shortest-path works immediately. It is also the version users complain about, because the rendered route is a straight line from the middle of one room to the middle of the next — through the wall between them. The graph is correct; the drawing of it is wrong, and to a user those are the same thing.

The medial axis is the default for a reason: most indoor estates are corridor buildings, and the medial axis of a corridor is its centreline, which is exactly where people walk. Where it struggles is wide open space — a concourse, an atrium, an open-plan floor plate — because the medial axis of a large convex area collapses to a short segment that carries no useful routing structure. That is what the navmesh and visibility-graph columns are for, and a large estate frequently needs more than one approach applied per space type.

Prerequisites & Dependencies

Graph construction is the first stage that consumes semantics as well as geometry, so it has more preconditions than anything upstream.

  • Validated, non-overlapping room polygons per level, from geometry cleanup. Overlapping rooms produce ambiguous door placement and duplicate nodes.
  • Openings with positions and widths, from wall and door detection. An opening is the only thing that authorises an edge between two spaces.
  • A level index on every feature, from level mapping. Vertical edges are built from the index, not from geometry.
  • A space_class on every space, from POI taxonomy. Stairs, lifts and escalators need to be identified as such to become vertical transitions, and service spaces need to be excluded from public routing.
Dependency Version Used for
shapely ≥ 2.0 polygon operations, buffering, nearest points
networkx ≥ 3.0 the graph itself, connectivity and shortest paths
scipy ≥ 1.11 Voronoi diagram underlying the medial axis
numpy ≥ 1.24 vertex arrays and vectorised distance work

Architecture: Skeleton, Nodes, Edges, Verify

From room polygons to a verified routing graph A left-to-right pipeline of five stages. Room polygons and openings enter as bounded areas. The skeleton stage computes a medial axis per space, producing centrelines. The node stage places anchor points at doors, corridor junctions and vertical transitions. The edge stage connects those nodes and assigns weights. The verification stage checks that the result is a single connected component across the level set, and emits the routing graph. Five stages, and the last one is the only proof the others worked bounded areas centrelines anchor points a graph 1 Spaces room polygons + openings 2 Skeleton medial axis per space 3 Nodes doors, junctions, vertical 4 Edges connect + weight 5 Verify one component per level set routing.graph

Verification is a stage, not an afterthought. Every earlier stage can succeed and still leave a wing unreachable — connectivity is the only property that says the graph is usable.

Skeleton. For each traversable space, compute a centreline. The practical construction is a Voronoi diagram of densified boundary points, keeping only the ridges that lie strictly inside the polygon — that is the medial axis, and for a corridor it is the line down the middle. Rooms get the same treatment, but their skeleton is usually discarded in favour of a single interior point, because routing within a room is not something users need instructions for.

Nodes. Three kinds come from geometry and one does not:

  • Door nodes at the centre of each opening, plus a short spur connecting the opening to the skeleton on each side. The spur is what stops paths cutting through wall faces.
  • Junction nodes where skeleton branches meet, which is where turn instructions are generated.
  • Space nodes, one per room, as the destination a search resolves to.
  • Vertical nodes at stairs, lifts and escalators, which exist on every level the transition serves and are joined by edges that no single level’s geometry describes.
Where nodes are placed on one floor and what each kind connects A floor with five rooms and a corridor. A teal centreline runs the length of the corridor, computed as its medial axis. Amber door nodes sit on the centreline opposite each room's opening, each joined to its room by a short spur. A rose junction node marks where a side corridor branches. A cyan vertical node at the end of the branch is a lift, connecting to the same position on levels one and three. Doors, junctions and vertical transitions — the graph is only these 2.01 2.02 2.03 2.04 Lab corridor centreline (medial axis) junction node lift -> level 1, level 3 corridor edge door node junction node vertical node

Four node kinds, three of them derived from geometry. The vertical node is the exception: nothing in a single level's geometry says a lift reaches level 3, so that edge comes from the level index rather than from the plan.

Edges. Every edge carries a length, a class (corridor, door, stair, elevator, escalator, ramp), and any accessibility attributes the source provides. Weighting is deliberately kept out of the graph: profiles apply multipliers at query time, as accessible routing profiles describes, so one graph serves every profile.

Verify. The graph is checked for exactly one connected component across the whole building’s level set, for zero orphan nodes, and for per-profile reachability. A graph that fails any of these is not published, because a disconnected graph produces the single most damaging user-visible failure: a route that cannot be found between two places a person can clearly walk between.

Step-by-Step Implementation

Step 1 — a medial-axis skeleton for one space.

import logging

import numpy as np
from scipy.spatial import Voronoi
from shapely.geometry import LineString, MultiLineString, Polygon
from shapely.ops import linemerge, unary_union

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


def medial_axis(space: Polygon, step: float = 0.35) -> MultiLineString:
    """Approximate the medial axis as the interior ridges of a boundary Voronoi diagram."""
    if space.is_empty or not space.is_valid:
        raise ValueError("medial_axis needs a valid, non-empty polygon")

    boundary = space.exterior
    n = max(int(boundary.length / step), 8)
    pts = np.array([boundary.interpolate(i / n, normalized=True).coords[0] for i in range(n)])
    try:
        vor = Voronoi(pts)
    except Exception as exc:                       # QhullError on degenerate input
        logger.warning("voronoi failed for a %.1f m2 space: %s", space.area, exc)
        return MultiLineString([])

    inner = space.buffer(-0.05)                    # keep ridges clear of the wall face
    ridges = [
        LineString([vor.vertices[a], vor.vertices[b]])
        for a, b in vor.ridge_vertices
        if a >= 0 and b >= 0
    ]
    kept = [r for r in ridges if inner.contains(r)]
    logger.info("space %.1f m2: %d/%d voronoi ridges kept", space.area, len(kept), len(ridges))
    merged = linemerge(unary_union(kept)) if kept else MultiLineString([])
    return merged if merged.geom_type == "MultiLineString" else MultiLineString([merged])

Step 2 — place nodes and build the graph.

import networkx as nx
from shapely.geometry import Point


def build_level_graph(spaces: dict[str, Polygon], openings: list[dict],
                      level: float) -> nx.Graph:
    """One level's graph: skeleton edges, space nodes, and door nodes joining them."""
    g = nx.Graph()

    for space_id, poly in spaces.items():
        g.add_node(f"space:{space_id}", kind="space", level=level,
                   x=poly.representative_point().x, y=poly.representative_point().y)
        for seg in medial_axis(poly).geoms:
            coords = list(seg.coords)
            for a, b in zip(coords, coords[1:]):
                na, nb = f"n:{a[0]:.2f},{a[1]:.2f}", f"n:{b[0]:.2f},{b[1]:.2f}"
                g.add_node(na, kind="skeleton", level=level, x=a[0], y=a[1])
                g.add_node(nb, kind="skeleton", level=level, x=b[0], y=b[1])
                g.add_edge(na, nb, length=Point(a).distance(Point(b)), cls="corridor")

    for op in openings:
        door = f"door:{op['id']}"
        g.add_node(door, kind="door", level=level, x=op["x"], y=op["y"], width=op["width"])
        for side in ("a", "b"):                    # the two spaces the opening joins
            sid = op[f"space_{side}"]
            if sid is None:
                continue
            anchor = _nearest_skeleton(g, op["x"], op["y"], level)
            g.add_edge(door, anchor, length=op.get("spur_len", 0.6), cls="door")
            g.add_edge(door, f"space:{sid}", length=0.1, cls="door")

    logger.info("level %+g: %d nodes, %d edges", level, g.number_of_nodes(), g.number_of_edges())
    return g

Step 3 — join levels with vertical edges.

def add_vertical_edges(g: nx.Graph, transitions: list[dict]) -> nx.Graph:
    """Connect a stair/lift/escalator node across every level it serves."""
    for t in transitions:
        levels = sorted(t["levels"])
        for lo, hi in zip(levels, levels[1:]):
            a, b = f"vert:{t['id']}:{lo}", f"vert:{t['id']}:{hi}"
            for node, lv in ((a, lo), (b, hi)):
                g.add_node(node, kind="vertical", level=lv, x=t["x"], y=t["y"])
            g.add_edge(a, b, length=t.get("rise_m", 4.2), cls=t["class"])
    return g

Step 4 — verify before anything is published.

def verify(g: nx.Graph) -> dict[str, int | bool]:
    """The only check that says the graph is usable: is every place reachable?"""
    components = nx.number_connected_components(g)
    orphans = [n for n, d in g.degree() if d == 0]
    spaces = [n for n, a in g.nodes(data=True) if a.get("kind") == "space"]
    unreachable = [n for n in spaces if g.degree(n) == 0]
    result = {"components": components, "orphans": len(orphans),
              "unreachable_spaces": len(unreachable), "ok": components == 1 and not unreachable}
    if not result["ok"]:
        logger.error("graph is not routable: %s", result)
    return result

Edge Cases & Gotchas

Pattern Symptom Handling
Wide open concourse Skeleton collapses to a short stub Fall back to a navmesh or grid for spaces above ~300 m²
Room with no opening Orphan space node Fail the level; a room with no door is a modelling error
Double doors modelled as two Two parallel edges, odd instructions Merge openings closer than 0.4 m into one node
Lift shaft on every level, serving three Edges to levels it does not stop at Take served levels from the transition record, never from geometry
Escalator Routed against its direction Model as a directed edge; networkx.DiGraph for these only
Very long corridor, no intermediate nodes Route snapping is coarse Split skeleton edges longer than ~15 m
Curved corridor densified coarsely Skeleton wanders into walls Densify boundary at ≤ 0.35 m before the Voronoi

The escalator case is worth highlighting because it is the one place a purely undirected model breaks. An escalator is traversable in one direction only, and a graph that treats it as bidirectional will confidently route a user the wrong way up one. The practical arrangement is an undirected graph for everything else plus a small set of directed edges, applied as a constraint at query time rather than by converting the whole graph to a DiGraph — which would double the memory and complicate every other operation for the sake of a handful of edges.

Validation Output

A healthy building:

{
  "building": "HQ",
  "levels": [-1, 0, 1, 2, 3, 4, 5, 6],
  "nodes": 5914,
  "edges": 7238,
  "components": 1,
  "orphan_spaces": 0,
  "vertical_transitions": 11,
  "reachability": {"default": 1.00, "step_free": 1.00, "service": 1.00},
  "median_edge_length_m": 1.8,
  "longest_edge_m": 14.6
}

A building with a stranded wing:

{
  "building": "HQ",
  "levels": [-1, 0, 1, 2, 3, 4, 5, 6],
  "nodes": 5902,
  "edges": 7201,
  "components": 2,
  "orphan_spaces": 0,
  "vertical_transitions": 11,
  "reachability": {"default": 0.91, "step_free": 0.74, "service": 0.91},
  "component_sizes": [5488, 414]
}

The second is the case the verification stage exists for. Nothing is invalid — 5,902 nodes, no orphans, sensible edge lengths — and 9% of the building cannot be reached from the other 91%. The step-free figure falling further, to 0.74, adds the diagnosis: the stranded component is reachable by stairs but its lift was not modelled, so it is doubly isolated for wheelchair users.

The assertion to automate is per profile, not just overall:

def test_every_space_reachable_per_profile(graph, profiles):
    for name, weights in profiles.items():
        reachable = reachable_space_fraction(graph, weights)
        assert reachable == 1.0, f"{name}: only {reachable:.0%} of spaces are reachable"

Performance & Scale Notes

Skeletonisation dominates, and it is per space, so it parallelises trivially.

Level Spaces Skeleton Nodes + edges Verify Total
Small office 22 0.3 s 0.05 s 0.01 s 0.36 s
Typical floor 61 1.1 s 0.14 s 0.02 s 1.26 s
Hospital ward floor 214 4.6 s 0.51 s 0.06 s 5.17 s
Concourse (navmesh path) 8 0.2 s 0.9 s 0.03 s 1.13 s

Node count is the number that matters downstream, because it sets solve latency. A medial-axis graph produces roughly 12 nodes per space at a 0.35 m densification step, and the step is the lever: 0.5 m roughly halves the node count and coarsens route geometry noticeably at building scale; 0.25 m doubles it for detail nobody sees. A 42,000-node campus graph solves single-source paths in around 70 ms with networkx, which is comfortable — the point at which igraph becomes worth its integration cost is roughly 150,000 nodes, or a service handling many concurrent solves.

Memory is modest — a 42,000-node graph with attributes is around 90 MB in networkx — but rebuild time is not, which is why the graph is built once per publish and mutated incrementally for live changes such as corridor closures.

Frequently Asked Questions

Why not just connect room centroids?

Because the route is drawn on a map. A centroid graph is topologically correct — it will find a valid sequence of rooms — but the polyline rendered between two centroids runs straight through whatever walls lie between them, and a user watching a blue line cross three offices concludes the product is broken. It also produces poor instructions, since there are no junction nodes to say “turn left at the end of the corridor”, and it cannot express distance honestly: the centroid-to-centroid distance between two rooms at opposite ends of an L-shaped corridor understates the walk by a wide margin.

How do I handle large open spaces?

Switch approach for those spaces rather than trying to make the medial axis work. A concourse, atrium or open-plan floor plate has a medial axis that collapses to a short stub in the middle, which carries no routing structure — every entrance connects to the same point and every path through the space is the same path. The two practical alternatives are a navmesh, which triangulates the space and routes across triangle adjacency, and a coarse grid with obstacle masking. Both give plausible paths through open areas, and both can be applied per space, so a building can use the medial axis in its corridors and a navmesh in its lobby with no special handling at the boundary beyond a shared door node.

Should edge weights be baked into the graph?

No — store the physical length and the edge class, and let profiles apply multipliers at query time. Baking weights means one graph per profile, which multiplies build time and memory by the profile count and, worse, means a live corridor closure has to be applied to every copy. With weights applied as a function, one in-memory graph serves the default, step-free, low-vision and service profiles concurrently, and an attribute change is seen by all of them on the next query. The only thing worth precomputing is the length, because it never changes.

How often should the graph be rebuilt?

On geometry change, and never on attribute change. A full rebuild is expensive — seconds per level — and is only necessary when the polygons or openings themselves moved, which is when a new drawing or model revision lands. Everything else that affects routing is an attribute: a corridor closed for maintenance, a lift out of service, a door locked outside hours. Those are applied to the live graph as attribute updates, which is an operation measured in microseconds and which every profile picks up immediately. Rebuilding for them would make live operational changes cost the same as a map release, which is how stacks end up with a map that is always slightly out of date.

This page is part of the Indoor Mapping Architecture & Standards section.

Building a Routing Graph from Room Polygons

A complete Python walkthrough from a validated GeoJSON envelope to a verified indoor routing graph: skeletonisation, door spurs, level joins, and the connectivity check that gates publication.

Read more

Medial Axis vs. Visibility Graph

Choose the right graph structure per space: how a medial axis and a visibility graph differ in path realism and scaling, where each breaks down, and how to mix both in one building.

Read more

Placing Nodes at Doors and Corridor Junctions

Node placement rules for indoor routing graphs: door spurs, merging double doors, junction nodes for turn-by-turn, splitting long corridor edges, and the degree assertions that catch a broken graph.

Read more

Weighting Indoor Routing Edges

Make indoor routes match what people would walk: converting turns, level changes, doors and crowding into metres-equivalent, tuning the turn cost, and keeping weights out of the stored graph.

Read more