Placing Nodes at Doors and Corridor Junctions

The placement half of Indoor Routing Graph Construction: which points in a building become nodes, what each kind is for, and the degree checks that turn a silent graph defect into a countable one.

Five Kinds of Node

The five node kinds, where each is placed and what depends on it A table of five node kinds. A space node sits at a room's representative point, has degree one, and exists so search results have somewhere to resolve to. A door node sits at the centre of an opening, has degree two or three, and is the only thing that links one space to another. A junction node sits at a skeleton branch point, has degree three or more, and is what turn-by-turn instructions are generated from. A vertical node sits at a stair or lift centre, has degree two to six, and carries cross-level edges. A split node is inserted every fifteen metres along a corridor, has degree two, and exists to give position snapping enough resolution. Five kinds, and each has an expected degree you can assert on Node kind Placed at Degree Used for Space node room representative point 1 search results, destinations Door node centre of the opening 2-3 ● the only space-to-space link Junction node skeleton branch point 3+ ● turn-by-turn instructions Vertical node stair / lift centre 2-6 ● cross-level edges Split node every 15 m of corridor 2 position snapping resolution Degree is diagnostic: a door node of degree 1 means one of its two spaces went missing.

Degree is the cheapest integrity check there is. A door node with only one edge means one of the two spaces it should join was never connected — countable, and much easier to find than a missing route.

Every node in an indoor routing graph exists for a reason, and the reasons are worth keeping distinct because they have different failure modes.

A space node is a destination. When a user searches for “Room 2.04” the result resolves to this node, and nothing routes through it — it hangs off a door node with a short edge.

A door node is the only thing that joins two spaces. This is the load-bearing rule of the whole graph: if two rooms are connected, an opening authorises it, and the door node is that authorisation made routable. A door node with fewer than two edges means one of its spaces was never resolved.

A junction node is where turn-by-turn instructions come from. Without them a route is a polyline and the instruction generator has nothing to say beyond “continue”.

A vertical node is the only node kind that is not derived from a single level’s geometry. It exists on each level a transition serves, and its edges come from the transition record.

A split node exists purely so that a position can snap somewhere sensible, which the next section covers.

The Door Spur and Double Doors

Merging a double-door pair into a single node On the left, a wall run with two openings 0.32 metres apart, each given its own node, which causes turn-by-turn generation to emit two instructions a third of a metre apart. An arrow leads right to the merged result: a single node with a combined width of 1.8 metres, producing one instruction. A caption notes that double doors, revolving-door bypasses and airlock pairs all produce the unmerged pattern. Two openings, one doorway, one instruction two nodes 0.32 m apart “turn” twice, 0.3 m apart one node, width 1.8 m one instruction double doors, revolving-door bypasses and airlock pairs all produce this as modelled after merging

Merge on distance, sum the widths. The combined width is what an accessibility profile needs — a pair of 0.9 m leaves is a 1.8 m opening, and treating them as two narrow doors would wrongly exclude a wheelchair route.

Two placement rules around doors do most of the work.

The spur. A door node connects to the corridor skeleton by a short perpendicular edge rather than by a direct join from the space’s interior point. Without it the rendered route leaves the room diagonally through the wall beside the door, which is the same visual defect a room-centroid graph has and the reason the medial-axis approach was chosen in the first place.

The merge. Openings closer than about 0.4 m are one doorway modelled as two. Double doors, airlock pairs and revolving-door bypasses all produce this, and leaving them as separate nodes causes two problems: the instruction generator emits two turns a third of a metre apart, and each leaf’s width is evaluated separately by accessibility profiles — so a pair of 0.9 m leaves reads as two narrow doors rather than one 1.8 m opening, and a wheelchair route is wrongly excluded.

Merging sums the widths and keeps a single node, which fixes both.

Minimal Working Example 

import logging
from dataclasses import dataclass

import networkx as nx
from shapely.geometry import LineString, Point
from shapely.ops import nearest_points

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

EXPECTED_DEGREE = {"space": (1, 4), "door": (2, 3), "junction": (3, 8),
                   "vertical": (2, 6), "split": (2, 2)}


@dataclass(frozen=True)
class Placement:
    added: int
    merged_doors: int
    split_edges: int


def attach_door(g: nx.Graph, door: dict, skeleton: LineString, level: float,
                spur_len: float = 0.6) -> None:
    """Place a door node on the opening and spur it onto the corridor skeleton."""
    if door.get("space_a") is None and door.get("space_b") is None:
        raise ValueError(f"opening {door['id']} joins nothing; check the detection stage")

    node = f"door:{door['id']}"
    g.add_node(node, kind="door", level=level, x=door["x"], y=door["y"],
               width=door["width"])

    p = Point(door["x"], door["y"])
    anchor_pt = nearest_points(skeleton, p)[0]
    anchor = f"n:{anchor_pt.x:.2f},{anchor_pt.y:.2f}"
    g.add_node(anchor, kind="skeleton", level=level, x=anchor_pt.x, y=anchor_pt.y)
    g.add_edge(node, anchor, length=max(p.distance(anchor_pt), spur_len), cls="door")

    for side in ("space_a", "space_b"):
        if door.get(side):
            g.add_edge(node, f"space:{door[side]}", length=0.1, cls="door")


def split_long_edges(g: nx.Graph, max_len: float = 15.0) -> int:
    """Insert intermediate nodes so a position always has somewhere close to snap to."""
    count = 0
    for a, b, data in list(g.edges(data=True)):
        if data.get("cls") != "corridor" or data.get("length", 0) <= max_len:
            continue
        pa, pb = g.nodes[a], g.nodes[b]
        n = int(data["length"] // max_len)
        prev = a
        for i in range(1, n + 1):
            t = i / (n + 1)
            x = pa["x"] + t * (pb["x"] - pa["x"])
            y = pa["y"] + t * (pb["y"] - pa["y"])
            mid = f"split:{x:.2f},{y:.2f}"
            g.add_node(mid, kind="split", level=pa["level"], x=x, y=y)
            g.add_edge(prev, mid, length=data["length"] / (n + 1), cls="corridor")
            prev = mid
            count += 1
        g.add_edge(prev, b, length=data["length"] / (n + 1), cls="corridor")
        g.remove_edge(a, b)
    logger.info("split %d long corridor edge(s)", count)
    return count


def assert_degrees(g: nx.Graph) -> list[str]:
    """Every node kind has an expected degree range; violations name a specific defect."""
    problems: list[str] = []
    for node, attrs in g.nodes(data=True):
        lo, hi = EXPECTED_DEGREE.get(attrs.get("kind", ""), (0, 99))
        d = g.degree(node)
        if not lo <= d <= hi:
            problems.append(f"{attrs.get('kind')} node {node} has degree {d}, expected {lo}-{hi}")
    for p in problems[:10]:
        logger.warning("degree check: %s", p)
    return problems

assert_degrees is the cheapest integrity check in the build and finds a surprising range of defects: a door node of degree 1 (one space unresolved), a junction node of degree 2 (a false branch from skeleton noise), a space node of degree 0 (a room with no opening at all).

Splitting Long Corridor Edges

Snapping resolution against how long skeleton edges are allowed to be Two curves against the maximum permitted skeleton edge length. Worst-case snap error rises roughly linearly with edge length, from 0.9 metres at a 5 metre limit to 2.4 metres at 15 metres and 9.8 metres at 60 metres. Nodes added per 100 metres of corridor falls hyperbolically, from 20 at a 5 metre limit to 7 at 15 metres and under 2 at 60 metres. Splitting long corridor edges is what makes snapping precise 0 5 10 15 20 15 30 45 60 maximum skeleton edge length (m) snap error (m) / nodes per 100 m snap error (m) nodes added per 100 m of corridor 15 m: 2.4 m worst-case snap, 7 nodes / 100 m

Long edges are cheap and imprecise. A position can only snap to a node or to a point along an edge, so a 60 m edge with no intermediate nodes puts a user up to 10 m from where the graph thinks they are.

A skeleton edge running the length of a 60 m corridor is geometrically correct and operationally useless, because a live position can only snap to a node or to a projection onto an edge. With no intermediate nodes the snapped position is precise along the corridor and the node the router reasons about is up to 30 m away, which shows up as coarse progress reporting and imprecise “you have arrived” behaviour.

Splitting at roughly 15 m keeps worst-case node distance under 8 m and costs about 7 nodes per 100 m of corridor, which is negligible next to the ~12 nodes per space the skeleton already produces. Below about 10 m the return diminishes sharply while the node count keeps rising.

The split nodes have no semantic meaning — they are pure resolution — which is why they carry their own kind and are excluded from instruction generation. A turn-by-turn generator that treats them as waypoints will emit “continue straight” every 15 m.

Parameter Reference

Parameter Type Default Notes
spur_len float 0.6 m Minimum door-to-skeleton edge; roughly half a corridor width
merge_doors float 0.4 m Openings closer than this become one node
max_len float 15 m Corridor edges longer than this are split
junction_min_angle float 25° Branches shallower than this are skeleton noise, not junctions
space_node str representative_point Never the centroid — a centroid can fall outside an L-shaped room

The last row is a small trap with a large symptom. Polygon.centroid is the area centroid, which for an L-shaped or U-shaped room falls in the notch — outside the polygon. A space node placed there sits in a neighbouring room or in the corridor, so search results resolve to the wrong place and the room’s own door spur points somewhere strange. representative_point() is guaranteed to lie inside the polygon and costs the same.

Common Errors & Fixes

Instructions say “turn” in a straight corridor. Junction nodes are being created from skeleton noise. Simplify each skeleton segment before adding it, and apply a minimum branch angle — a branch that leaves the main run at 8° is a Voronoi artefact, not a corridor.

A wheelchair route is refused through a double doorway. The two leaves were not merged, so each is evaluated at 0.9 m against a profile minimum of 1.2 m. Merging sums the widths to 1.8 m and the route is allowed. This is worth an explicit test, because the failure is silent — the route simply takes a longer path:

def test_double_doors_merge_widths(openings):
    merged = merge_close(openings, tol=0.4)
    assert len(merged) == 1 and merged[0]["width"] >= 1.7

A room is unreachable but has a door. The door node was created but one of its space references did not resolve, giving it degree 1. assert_degrees catches this directly and names the node, which is far faster than working back from a failed route.

Snapping puts users in the wrong room. Space nodes were placed at polygon centroids. Switch to representative_point(); the symptom is characteristic in L-shaped and U-shaped rooms and absent in rectangular ones, which is a useful diagnostic in itself.

Integration Point

Node placement consumes the skeletons produced by structure choice and the openings produced by wall and door detection, and it produces the node set that edge weighting then costs. Downstream, the split nodes are what snapping noisy positions projects onto, and the junction nodes are what a turn-by-turn generator walks.

The degree assertions belong in the CI gate alongside the connectivity check, because they catch a different class of defect: connectivity says the building is reachable, degree says each node is doing the job its kind implies.

Frequently Asked Questions

Should every room really get its own node?

Every room a user might navigate to, yes — that is what a search result resolves to, and without it the best a system can do is route to the nearest door and hope. The exceptions are spaces nobody navigates to as a destination: risers, voids, ceiling plenums and other service spaces, which should be excluded on space_class rather than given a node that will never be used. Very small spaces below about 1.2 square metres are worth excluding too, since they are usually cupboards, and a node in every cupboard inflates the graph and the search index for no benefit.

How should thresholds without doors be handled?

As door nodes with a very large width and a class that distinguishes them, because topologically they are identical to a doorway: a gap in a wall that authorises movement. Giving them a distinct class matters for two reasons. Accessibility profiles treat an open threshold differently from a door leaf — there is nothing to pull or push — and turn-by-turn generation should not say “go through the door” where there is no door. The width should be the measured opening, which lets a profile with a minimum-width rule pass them trivially.

Do split nodes affect route distance?

No, and that is a property worth preserving deliberately. Splitting an edge divides its length among the pieces, so the sum along the split chain equals the original — a route through a split corridor measures exactly what it measured before. What splitting changes is resolution: where a live position can snap, and how finely progress along the route can be reported. If splitting ever changes route length, the division is wrong, and that is a one-line assertion worth having in the test suite.

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