Medial Axis vs. Visibility Graph for Indoor Routing

Part of Indoor Routing Graph Construction: the choice between two ways of turning a space into a network, why it is made per space rather than per building, and the quadratic term that decides where the boundary sits.

What the Two Structures Claim #

A medial axis is the set of points equidistant from two or more boundary edges — the skeleton of the space. Routing on it produces paths that stay in the middle of whatever they traverse, which in a corridor is exactly where people walk.

A visibility graph connects every pair of vertices that can see each other without crossing an obstacle. Routing on it produces the shortest unobstructed path, which in an open space is the diagonal a person actually takes and which a medial axis cannot express.

The two make different claims. The medial axis says this is where the walkable space is; the visibility graph says these are the moves available. In a 1.8 m corridor the two answers coincide to within a few centimetres. In a 40 m concourse they differ by tens of metres, and the medial axis is the one that is wrong — it will route a user around the perimeter of a hall they would walk straight across.

Minimal Working Example #

Both structures from the same polygon, so they can be compared directly:

import itertools
import logging

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

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


def visibility_graph(space: Polygon, extra: list[Point] | None = None,
                     clearance: float = 0.05) -> nx.Graph:
    """Connect every mutually visible vertex pair. O(V^2) edges — apply per space only."""
    if not space.is_valid:
        raise ValueError("visibility_graph needs a valid polygon")

    verts = [Point(c) for c in space.exterior.coords[:-1]]
    for ring in space.interiors:                       # columns, service cores
        verts += [Point(c) for c in ring.coords[:-1]]
    verts += list(extra or [])

    inner = space.buffer(-clearance)                   # keep sight lines off the wall face
    g = nx.Graph()
    for i, p in enumerate(verts):
        g.add_node(i, x=p.x, y=p.y)

    checked = blocked = 0
    for (i, a), (j, b) in itertools.combinations(enumerate(verts), 2):
        checked += 1
        sight = LineString([a, b])
        if inner.contains(sight):
            g.add_edge(i, j, length=a.distance(b), cls="open")
        else:
            blocked += 1
    logger.info("visibility: %d node(s), %d/%d sight line(s) clear",
                len(verts), checked - blocked, checked)
    return g


def choose_structure(space: Polygon, *, narrow: float = 4.0, open_max: float = 800.0) -> str:
    """Pick the structure this space should use, by shape and size."""
    width = 4.0 * space.area / space.length           # equivalent-rectangle width
    aspect = (space.length ** 2) / (4.0 * space.area) # crude elongation measure
    if width < narrow or aspect > 3.0:
        return "medial_axis"
    if space.area <= open_max:
        return "visibility"
    return "navmesh"

choose_structure is deliberately crude, and that is fine: the two measurements it uses — equivalent-rectangle width and elongation — separate corridors from halls reliably, and the consequence of a wrong call on a borderline space is a slightly odd path rather than a broken one.

Scaling and the Crossover #

The medial axis grows linearly with the size of the space, because it is a skeleton: doubling the area roughly doubles the length of centreline and therefore the node count.

The visibility graph grows quadratically, because it considers every vertex pair. A 500 m² space with a few hundred boundary vertices produces around 100,000 edges; a 2,000 m² space produces 1.6 million. Both the construction (every pair needs a line-of-sight test) and the solve (more edges to relax) become impractical well before a whole floor plate.

That is the entire reason the choice is made per space. A building with 40 corridor-shaped spaces and one 600 m² lobby gets a medial axis in 40 places and a visibility graph in one, and the resulting graph is a few thousand nodes rather than a few million.

Comparison Reference #

The turn-instruction row is the underrated one. A medial axis has junction nodes where the skeleton branches, which map directly onto “turn left at the junction”. A visibility graph has no such structure — every vertex is a potential turn and the path is a sequence of bearing changes — so generating usable instructions from it requires a separate simplification pass.

Common Errors & Fixes #

A hall routes around its perimeter. The medial axis was applied to an open space. The skeleton of a large convex area is a short segment near its centre, so every entrance connects to that stub and the path from one door to another runs in and back out again along the walls. Switch that space to a visibility graph or a navmesh; the door nodes stay identical, so nothing else changes.

Visibility construction takes minutes on one space. The boundary is over-densified. A visibility graph should use the polygon’s actual corners, not an interpolated point every 0.35 m — densification is a medial-axis requirement and is actively harmful here, since it multiplies the vertex count that the edge growth is quadratic in. Simplify the boundary first.

Sight lines cut through a wall. The containment test used the raw polygon rather than a negatively buffered one, so a line running exactly along a wall face counts as inside. Buffer inward by a few centimetres before testing, as in the example above.

Paths inside a hall clip its columns. Interior rings were not included in the vertex set. Columns and service cores appear as interiors of the space polygon, and both their vertices and their blocking effect are needed — omitting them produces sight lines straight through structure.

Integration Point #

Structure choice sits inside the skeletonisation stage of routing graph construction, applied per space before node placement. Whatever structure a space uses, it exposes the same interface to the next stage: a set of interior nodes and edges, onto which door nodes attach via spurs. That uniform interface is what makes mixing structures free — the composition step does not know or care which space used which.

The choice is also recorded per space in the build report, because it affects how routes through that space read to a user, and a complaint about an odd path is much faster to diagnose when the structure is known.

Frequently Asked Questions #

Related #

• Indoor Routing Graph Construction — where structure choice sits in the wider build.
• Building a Routing Graph from Room Polygons — the implementation that calls this choice per space.
• Weighting Indoor Routing Edges by Distance and Turn Cost — why direct paths are not always the ones people prefer.

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