Detecting and Merging Duplicate Wall Segments

Part of Geometry Cleanup & Topology Repair: the pass that finds walls the drawing contains twice and collapses them into one, without touching the parallel faces that are a wall’s thickness rather than a mistake.

Where Duplicate Walls Come From #

Duplicates are not drafting errors so much as drafting history. The recurring sources are all mundane:

• Layered exports. An architectural base drawing and a fit-out drawing both contain the core walls. Export both layers and every core wall appears twice, offset by whatever coordinate noise the two files carry.
• Copy-paste revisions. A wing is duplicated to create a mirrored floor, edited, and the original left in place on a frozen layer that the export includes.
• Block explosion. A wall assembly block is both referenced by an INSERT and present as exploded geometry, which happens when someone explodes a block to edit it and the reference is not removed.
• Trace-over. A raster underlay is traced, and the resulting vector geometry is exported alongside a partially vectorised earlier attempt.

In every case the two copies are within a few centimetres of each other, and neither is marked as redundant.

The cost is not primarily storage. Two parallel wall runs a few centimetres apart produce two parallel chains of routing nodes, and because the chains never share a vertex the routing graph gains a disconnected component for every doubled corridor. The floor above went from fourteen components to one purely by merging duplicates — no geometry was moved, and nothing else changed.

The Three Tests #

Merging is guarded by three independent tests, and a pair is merged only when all three say “these are the same wall”. The asymmetry is deliberate: a missed duplicate is a redundancy, while a wrongly merged pair destroys a partition.

1. Bearing. The two segments must be near-parallel — within about 2°. Real building geometry contains plenty of nearly-parallel-but-not walls: splayed reveals, chamfered corners, ramped edges. A tighter threshold than 2° misses duplicates that carry rotation noise from a trace; a looser one starts merging genuine splays.

2. Perpendicular separation. The distance between the two lines, measured perpendicular to their shared bearing, must be below about three times the snapping tolerance — a few centimetres. Anything larger is a wall pair expressing thickness, which wall and door detection needs intact.

3. Longitudinal overlap. Projected onto their shared axis, the two segments must actually overlap. Two collinear segments with a gap between them are a wall with a doorway in it, and the gap is the single most important feature on the floor.

Minimal Working Example #

import logging
import math

import numpy as np
from shapely.geometry import LineString

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


def _bearing(seg: LineString) -> float:
    """Bearing in degrees, folded to [0, 180) so direction does not matter."""
    (x0, y0), (x1, y1) = seg.coords[0], seg.coords[-1]
    return math.degrees(math.atan2(y1 - y0, x1 - x0)) % 180.0


def is_duplicate(a: LineString, b: LineString, *, max_bearing: float = 2.0,
                 max_sep: float = 0.075, min_overlap: float = 0.5) -> bool:
    """True only when all three duplicate tests agree. Biased towards keeping both."""
    if a.is_empty or b.is_empty:
        raise ValueError("empty geometry reached duplicate detection; clean upstream")

    d_bearing = abs(_bearing(a) - _bearing(b))
    d_bearing = min(d_bearing, 180.0 - d_bearing)
    if d_bearing > max_bearing:
        return False                                   # test 1: not collinear

    # perpendicular separation: distance from b's midpoint to a's infinite line
    if a.distance(b.interpolate(0.5, normalized=True)) > max_sep:
        return False                                   # test 2: a real wall pair

    axis = np.array(a.coords[-1]) - np.array(a.coords[0])
    axis = axis / (np.linalg.norm(axis) or 1.0)
    proj = lambda p: float(np.dot(np.array(p) - np.array(a.coords[0]), axis))
    a0, a1 = sorted((proj(a.coords[0]), proj(a.coords[-1])))
    b0, b1 = sorted((proj(b.coords[0]), proj(b.coords[-1])))
    overlap = min(a1, b1) - max(a0, b0)
    if overlap < min_overlap:
        return False                                   # test 3: a doorway between them

    return True


def merge_pair(a: LineString, b: LineString) -> LineString:
    """Replace a duplicate pair with one segment spanning the union of both."""
    pts = list(a.coords) + list(b.coords)
    axis = np.array(a.coords[-1]) - np.array(a.coords[0])
    axis = axis / (np.linalg.norm(axis) or 1.0)
    keyed = sorted(pts, key=lambda p: float(np.dot(np.array(p) - np.array(a.coords[0]), axis)))
    merged = LineString([keyed[0], keyed[-1]])
    logger.info("merged duplicate: %.2f m + %.2f m -> %.2f m", a.length, b.length, merged.length)
    return merged

Note what merge_pair does with the geometry: it spans the union of the two segments rather than keeping the longer one. Duplicates frequently disagree at their ends — one copy stops at the column, the other runs past it — and taking the union preserves the full wall run, which is what polygonisation needs to close the ring.

Parameter Reference #

record_handles matters more than it looks. When a wall turns out to be missing from the published map, the question is which drawing entity produced it — and if a merge discarded one of the two handles, half the answers are unavailable. Carrying both on the merged segment costs a list and makes the merge reversible in diagnosis if not in data.

Common Errors & Fixes #

Wall thickness disappears across a whole building. max_sep was set larger than the building’s partitions. The symptom is distinctive: wall and door detection suddenly finds almost no offset pairs, because the pairs were merged into single centrelines before it ran. Derive max_sep from the same partition-thickness distribution that sets the snapping tolerance and keep it strictly below the fifth percentile.

Doorways vanish. min_overlap was set to zero or the overlap test was skipped, so two collinear runs either side of a door were merged across the opening. The opening is then invisible to detection and the two rooms never connect. This is the most damaging failure in the whole cleanup stage, because the resulting map looks complete and is unroutable, and it is worth a dedicated assertion in the test suite:

def test_doorway_survives_merging(wall_left, wall_right):
    assert not is_duplicate(wall_left, wall_right), "a doorway was merged shut"

The pass is quadratic and takes minutes. Every segment is being compared with every other. Use an STRtree over segment bounding boxes expanded by max_sep, and compare only candidates it returns; on a 7,000-segment floor that takes the pass from roughly 25 seconds to under 200 ms.

Integration Point #

Duplicate merging runs after snapping and before noding. The ordering is load-bearing in both directions: snapping first means the two copies of a wall have already had their endpoints pulled together, which makes the overlap test cleaner; merging before noding means the noder does not have to resolve the many near-parallel intersections that duplicates generate, which is where its superlinear cost comes from.

Its output feeds polygonisation, and its report feeds the same delta gate as the rest of the cleanup stage: a level whose merged-segment count changes sharply between builds has had something change in the export, and that is worth a human look before the map is published.

Frequently Asked Questions #

Related #

• Geometry Cleanup & Topology Repair — the stage this pass belongs to and the order it runs in.
• Snapping Tolerances for Floor Plan Geometry — where the separation threshold used here is derived.
• Automating Wall and Door Detection in CAD — the consumer that needs genuine wall pairs left intact.

This page is a companion to Geometry Cleanup & Topology Repair, part of the Automated Floor Plan Parsing & Vectorization section.