Geometry Cleanup & Topology Repair for Indoor Maps

A parser that reads every entity correctly still hands you geometry a routing graph cannot use. Wall runs stop 7 mm short of the corner they were meant to meet, two partitions cross without sharing a vertex, a cupboard is drawn twice, and a hatch boundary produces a 0.3 m-wide face that satisfies every validity rule and is not a room. This topic sits inside Automated Floor Plan Parsing & Vectorization and covers the repair stage between parsing and graph construction: what defects survive a correct parse, which of them can be fixed deterministically, which must be reported rather than guessed at, and how the tolerances you pick decide whether a floor comes out as forty rooms or as one.

The Problem: Valid Geometry That Is Still Wrong #

The failure this stage exists to prevent is specific and expensive: a floor that validates, publishes, renders correctly, and cannot be routed across. It happens because the properties a geometry library checks and the properties a router needs are different sets.

shapely will tell you a polygon is valid — its rings close, its interiors sit inside its exterior, its edges do not self-intersect. It will not tell you that the polygon is 0.35 m wide and therefore not a room, that the corridor beside it is two polygons because a wall segment was drawn twice, or that the wall between two offices has a 7 mm gap through which the polygonizer merged both into a single 84 m² space. Each of those is valid OGC geometry and each breaks something downstream.

The five defects above cover the overwhelming majority of what real drawings produce. They share a structure worth noticing: each is a mismatch between drawing intent and drawing content. A draughter working at 1:100 sees a closed room; the file contains four segments whose endpoints differ in the fourth decimal place. Nothing in the drawing is wrong for its purpose, which was to be printed and read by a human. Cleanup is the stage that translates from that purpose to this one.

The symptom set is equally consistent. Unclosed rings produce missing rooms — the polygonizer silently returns fewer faces than expected. Unnoded crossings produce overlapping rooms, where two polygons claim the same square metres and a POI resolves ambiguously. Slivers produce phantom rooms in the search index. Bow-ties produce a TopologyException deep inside a later spatial operation, usually during routing-graph construction, several stages away from the cause. Duplicate segments produce corridors that will not connect, because the routing graph builds a node on each of the two nearly identical walls and never joins them.

Prerequisites & Dependencies #

Cleanup runs after format parsing and before graph construction, and it assumes three things are already true:

• Geometry is in metres. Tolerances in this stage are absolute distances — 0.02 m, 0.35 m² — and are meaningless against drawing units. The $INSUNITS scaling described in SVG/DWG parsing workflows must have run, and a unitless drawing must already have been rejected.
• Geometry is 2D and per level. Cleanup is a planar operation. Z coordinates are dropped (the level index carries that information after level mapping), and each level is cleaned independently — snapping a second-floor wall onto a ground-floor one is never correct.
• Provenance is retained. Every segment carries the drawing layer and entity handle it came from. Cleanup discards and merges geometry, and when a room goes missing the only useful question is which entities produced it.

The library stack is small: shapely 2.x for geometry and validity, its unary_union and polygonize for the planar work, numpy for the vectorised distance work in snapping, and rtree/STRtree for candidate lookup so snapping is not quadratic.

One dependency deliberately absent: a general topology-repair library. Cleanup rules are building-specific and cheap to write; what is expensive is the policy — which defects are fixed silently, which are fixed loudly, and which stop the build.

Architecture: Snap, Node, Polygonize, Validate #

The pipeline is four transformations and a gate, and it only works in this order.

1. Snap. Endpoints within the snapping tolerance of each other are pulled onto a shared coordinate. This is what closes the 7 mm gaps. It is done against a spatial index of existing endpoints rather than pairwise, and it is idempotent: running it twice must not move anything the first pass did not.

2. Node. Every pair of segments that cross is split at the intersection so that the crossing becomes a shared vertex. shapely.ops.unary_union on the segment collection does this as a side effect of computing the union, which is the idiomatic way to reach a planar graph. Skipping this step is the single most common cause of overlapping rooms, because a polygonizer walks rings by shared vertices and two segments that merely cross share none.

3. Polygonize. shapely.ops.polygonize walks the noded planar graph and returns every minimal enclosed face. This is where a floor becomes a set of candidate rooms. Note the word candidate: polygonisation returns faces, not rooms, and the difference is the next stage.

4. Validate and filter. Each face is checked for OGC validity (repaired with make_valid where possible), then filtered against physical plausibility: a minimum area, a minimum width measured as the ratio of area to perimeter, and a maximum area that catches the merged-floor case. Faces that fail are not deleted quietly — they are counted, classified and reported.

The gate at the end is a comparison, not an absolute: the face count and total floor area for this level are compared against the previous published version. A level that went from 43 rooms to 41 is a question; a level that went from 43 to 1 is a merged floor and blocks the build.

Step-by-Step Implementation #

The core of the stage is short. What makes it production-grade is that every discarded face is accounted for.

Step 1 — snap endpoints against a spatial index.

import logging

import numpy as np
from shapely.geometry import LineString, Point
from shapely.strtree import STRtree

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


def snap_endpoints(segments: list[LineString], tol: float = 0.03) -> list[LineString]:
    """Pull endpoints within `tol` onto a shared coordinate. Idempotent."""
    if tol <= 0:
        raise ValueError("tolerance must be positive; 0 disables closure entirely")
    ends = [Point(c) for seg in segments for c in (seg.coords[0], seg.coords[-1])]
    tree = STRtree(ends)
    canonical: dict[int, tuple[float, float]] = {}
    for i, pt in enumerate(ends):
        if i in canonical:
            continue
        near = tree.query(pt.buffer(tol))
        # the lowest index in a cluster wins, so the result does not depend on order
        target = ends[min(near)] if len(near) else pt
        for j in near:
            canonical[int(j)] = (target.x, target.y)
    out: list[LineString] = []
    for s, seg in enumerate(segments):
        a = canonical.get(2 * s, seg.coords[0])
        b = canonical.get(2 * s + 1, seg.coords[-1])
        out.append(LineString([a, *list(seg.coords)[1:-1], b]))
    moved = sum(1 for i, p in enumerate(ends) if canonical.get(i, (p.x, p.y)) != (p.x, p.y))
    logger.info("snapped %d/%d endpoints at tol=%.3f m", moved, len(ends), tol)
    return out

Step 2 — node and polygonize.

from shapely.ops import polygonize, unary_union
from shapely.geometry import Polygon


def faces_from_segments(segments: list[LineString]) -> list[Polygon]:
    """Node the segment set into a planar graph, then walk it into faces."""
    try:
        noded = unary_union(segments)          # splits every crossing into a shared vertex
    except Exception as exc:                   # GEOSException on pathological input
        logger.error("noding failed: %s", exc)
        raise
    faces = list(polygonize(noded))
    logger.info("polygonized %d segment(s) into %d face(s)", len(segments), len(faces))
    return faces

Step 3 — validate, classify and report.

from dataclasses import dataclass, field
from shapely.validation import make_valid


@dataclass
class CleanupReport:
    kept: list[Polygon] = field(default_factory=list)
    slivers: list[Polygon] = field(default_factory=list)
    repaired: int = 0
    oversized: list[Polygon] = field(default_factory=list)

    def summary(self) -> dict[str, int]:
        return {"kept": len(self.kept), "slivers": len(self.slivers),
                "repaired": self.repaired, "oversized": len(self.oversized)}


def classify(faces: list[Polygon], *, min_area: float = 1.2,
             min_width: float = 0.6, max_area: float = 4000.0) -> CleanupReport:
    """Keep plausible rooms; count everything else instead of dropping it silently."""
    rep = CleanupReport()
    for face in faces:
        if not face.is_valid:
            face = make_valid(face)
            rep.repaired += 1
            if face.geom_type != "Polygon":       # make_valid can return a collection
                continue
        width = 4.0 * face.area / face.length     # ~width of an equivalent rectangle
        if face.area < min_area or width < min_width:
            rep.slivers.append(face)
        elif face.area > max_area:
            rep.oversized.append(face)            # a merged floor, almost always
        else:
            rep.kept.append(face)
    logger.info("cleanup: %s", rep.summary())
    return rep

Step 4 — gate on the delta, not the absolute. The report is compared with the previous published version for that level, and a drop of more than a few percent in face count or total area fails the build. This is the check that catches a tolerance regression, because a tolerance that is too large produces geometry that is individually valid and collectively wrong.

Edge Cases & Gotchas #

The tolerance question deserves its own answer because it is the one number that decides whether this stage helps or hurts. The chart above is measured on a mixed portfolio: closure saturates around 0.02-0.05 m, and merging accelerates past it. But the safe ceiling is a property of the building stock, not of the algorithm — it is roughly a third of the thinnest partition you need to preserve. A hospital with 75 mm glazed partitions needs a tighter tolerance than a warehouse with 200 mm blockwork, and the right way to choose is to measure the partition thickness distribution once per portfolio and derive the number, rather than copying 0.05 from a tutorial.

The other trap is repair that changes topology silently. make_valid on a bow-tie returns a MultiPolygon of two triangles, not a repaired quadrilateral. If the calling code takes .geoms[0], half the room disappears and nothing reports it. Always check the returned geometry type and treat a type change as a defect to report, not a result to use.

Validation Output #

The stage produces two artifacts: cleaned geometry, and a report that makes the cleaning auditable.

A healthy level:

{
  "level": 2,
  "trace_id": "b7f2c1a4",
  "faces_in": 51,
  "kept": 43,
  "slivers": 7,
  "repaired": 1,
  "oversized": 0,
  "endpoints_snapped": 118,
  "total_area_m2": 2841.6,
  "delta_vs_published": {"faces": 0, "area_m2": 0.0}
}

A level where the tolerance regressed:

{
  "level": 2,
  "trace_id": "c1a99e02",
  "faces_in": 12,
  "kept": 4,
  "slivers": 8,
  "repaired": 0,
  "oversized": 1,
  "endpoints_snapped": 903,
  "total_area_m2": 2839.1,
  "delta_vs_published": {"faces": -39, "area_m2": -2.5}
}

The second is the case worth dwelling on. Total area barely moved — the floor is still the same size — but 39 rooms vanished into one oversized face, and the snapped-endpoint count jumped from 118 to 903. Any gate that watched only area would have passed it. The face-count delta is what catches it, and the endpoint count tells you immediately that the cause was the tolerance rather than the drawing.

The assertion worth putting in the test suite is the round-trip one:

def test_cleanup_is_idempotent(segments):
    once = classify(faces_from_segments(snap_endpoints(segments)))
    twice = classify(faces_from_segments(snap_endpoints(
        [f.exterior for f in once.kept])))
    assert len(twice.kept) == len(once.kept), "cleanup is not a fixed point"

A cleanup stage that is not a fixed point will produce a different topology_hash on every run, which destroys the cache invalidation the delivery layer depends on.

Performance & Scale Notes #

Cleanup is cheap relative to parsing, provided the snapping stage is indexed. The naive pairwise endpoint comparison is O(n²) and becomes the dominant cost above a few thousand segments; an STRtree query per endpoint makes it O(n log n) and keeps a dense hospital floor under a second.

Measured on a 12-core worker, per level:

The last row is worth reading carefully. Noding is superlinear in the number of intersections, not segments, and hatch geometry left in the wall layer produces intersections quadratically. The fix is not a faster algorithm — it is filtering the hatch layer out before cleanup, which takes the same floor from 44 seconds to under a second. When a level takes minutes, the cause is almost always geometry that should never have entered the stage.

Memory follows the same shape: unary_union holds the whole noded graph, so a level with 91,000 segments peaks near 700 MB while a typical floor stays under 60 MB. Cleaning levels independently (and in parallel across processes, as the async batch pipeline does) keeps that bounded regardless of how many storeys a building has.

Frequently Asked Questions #

Related #

• Fixing Invalid Polygons with Shapely — the repair rules for each OGC validity failure, and what make_valid actually returns.
• Snapping Tolerances for Floor Plan Geometry — deriving the tolerance from your own building stock instead of copying a constant.
• Detecting and Merging Duplicate Wall Segments — the collinear-overlap test that collapses a doubled wall into one.
• Wall & Door Detection Algorithms — the stage immediately downstream, which assumes this one has run.
• SVG/DWG Parsing Workflows — where the segments this stage repairs come from.

This page is part of the Automated Floor Plan Parsing & Vectorization section.