Validating a Tessellation Against Its Source Boundary

The tessellation’s total area matches the source polygon’s to eight decimal places. It also covers a strip of sea on one side and misses an equal-sized wedge inland, and the area check cannot tell the difference.

Part of Polygon Tessellation Algorithms: generating a partition is one problem, and proving it is one is another — the checks people reach for first are the ones that a compensating pair of errors passes cleanly.

Root Cause: Aggregate Comparisons Are Blind to Compensating Errors

Three checks are commonly used, and two of them are unsound.

Comparing total areas. An overlap and a gap of equal size cancel exactly. This is not a contrived case: a tessellation clipped against a slightly generalised copy of the source boundary produces overlaps on convex stretches and gaps on concave ones, and their areas are of similar magnitude by construction.

Comparing bounding boxes. Two very different geometries share a bounding box whenever the extremes coincide, which they usually do since the extreme cells are clipped to the source.

Checking the cells are individually valid. Necessary, and entirely silent about whether they tile anything. A set of perfectly valid polygons with a hole in the middle passes every per-geometry validity test in existence.

The sound comparison is the symmetric difference between the union of the cells and the source polygon: the area covered by one and not the other, counted in both directions and not allowed to cancel.

Five tessellation checks against four failure classes A matrix with five checks as rows and four failure classes as columns. Comparing total areas catches a plain gap and a plain overhang, and misses both a compensating gap-and-overlap pair, whose areas cancel exactly, and a pair of cells that overlap each other inside the source. Comparing bounding boxes catches almost nothing, because the extreme cells are clipped to the source and so the extremes coincide whatever happens in the interior. Per-cell validity catches none of the four: a set of individually valid polygons can have any relationship to each other and to the source. Symmetric difference between the union and the source catches gaps, overhangs and the compensating pair, because the two directions are counted separately and not allowed to cancel — but it does not see two cells overlapping each other inside the source, since the union is unaffected by that. A pairwise overlap scan catches exactly that remaining case. The note underneath states the conclusion: the last two rows together are the minimum sound check, and either one alone leaves a real failure class invisible. The last two rows together are the minimum sound check check gap overhang gap + overlap cells overlap total area matches catches catches misses cancels misses bounding box matches misses misses misses misses per-cell validity misses misses misses misses symmetric difference catches catches catches misses union unchanged pairwise overlap scan misses misses catches catches Symmetric difference alone is not sufficient: two cells overlapping each other inside the source leave the union unchanged, so the comparison against the source sees nothing. The pairwise scan alone is not sufficient either — it says nothing about the source. Both, every build, is the standard.
Five validation checks against four failure classes: only symmetric difference and pairwise overlap catch all of them.

Prerequisite Check: Decide the Tolerance From the Coordinate Precision

A tessellation will never match its source exactly in floating point, so the check needs a tolerance — and it should come from the precision grid rather than from whatever number made the test pass.

python
def area_tolerance(source, grid: float, safety: float = 4.0) -> float:
    """The largest discrepancy the precision grid can produce along the boundary."""
    perimeter = source.length
    return perimeter * grid * safety

The reasoning is direct: snapping to a grid of size g can move any boundary vertex by up to g, so a boundary of length L can sweep an area of roughly L·g. A tolerance derived this way is a few square metres on a national boundary at a 1e-7 degree grid, and any discrepancy larger than that is a real geometric error rather than a rounding artifact.

Choosing the tolerance from the geometry rather than from experiment is what makes the check meaningful. A tolerance loosened until the tests pass is a tolerance that will not fail when it should.

Fix: Four Assertions That Together Prove a Partition

1 — Coverage: nothing in the source is unclaimed

python
def uncovered(cells, source, tol_area: float):
    """Parts of the source no cell covers."""
    gap = source.difference(unary_union(cells))
    pieces = [g for g in explode(gap) if g.area > tol_area]
    return sorted(pieces, key=lambda g: -g.area)

Returning the pieces rather than a boolean is what makes this usable. A gap’s location and shape say what caused it — a thin one along an edge is a snapping artifact, a chunky one is a missing seed or a failed clip.

2 — Containment: nothing extends beyond the source

python
def overhang(cells, source, tol_area: float):
    """Parts of the cells that fall outside the source polygon."""
    excess = unary_union(cells).difference(source)
    return [g for g in explode(excess) if g.area > tol_area]

3 — Disjointness: cells do not overlap each other

python
def overlaps(cells, tol_area: float, index):
    """Pairwise intersections with more than trivial area."""
    out = []
    for i, cell in enumerate(cells):
        for j in index.query(cell.bounds):
            if j <= i:
                continue
            inter = cell.intersection(cells[j])
            if inter.area > tol_area:
                out.append((i, j, inter.area))
    return out

The spatial index is not an optimisation here — a naïve pairwise loop over a hundred thousand cells is ten billion intersection tests, which turns a check that should run on every build into one that runs never.

4 — Accounting: the numbers agree with the geometry

python
def partition_report(cells, source, grid: float) -> dict:
    tol = area_tolerance(source, grid)
    gaps, over, dups = uncovered(cells, source, tol), overhang(cells, source, tol), None
    return {
        "cells": len(cells),
        "symmetric_difference": sum(g.area for g in gaps) + sum(g.area for g in over),
        "tolerance": tol,
        "gap_pieces": len(gaps),
        "overhang_pieces": len(over),
        "area_ratio": sum(c.area for c in cells) / source.area,
    }

Reporting area_ratio beside the symmetric difference is deliberate: seeing a ratio of exactly 1.0000 next to a large symmetric difference is the clearest possible demonstration of why the ratio was never sufficient.

A matching total area concealing a compensating gap and overhang On the left a source polygon is drawn as a closed outline. The union of a tessellation is overlaid on it. Along one convex stretch the tessellation extends beyond the source, producing a lobe of overhang shaded in one colour. Along a concave stretch on the opposite side the tessellation falls short of the source, leaving a wedge-shaped gap of very similar area shaded in another. Because the two regions have nearly equal area, the total area of the tessellation matches the source almost exactly. On the right two figures are printed: the area ratio, which reads as one to four decimal places and looks like a clean pass, and the symmetric difference, which is large and unambiguous. Beneath them the cause is named — clipping against a generalised copy of the boundary produces overhang on convex stretches and gaps on concave ones, so the two errors arrive together and of similar magnitude by construction. The note underneath explains why this is the normal case rather than a contrived one. Area ratio 1.0000, symmetric difference large — both are true overhang gap of equal area source boundary tessellation union what the checks report area ratio 1.0000 ✓ passes symmetric diff. large ✗ fails why they arrive together clipping against a generalised boundary overhang on convex stretches gap on concave ones similar magnitude by construction This is the normal case, not a contrived one. Any clip against a boundary that differs slightly from the source — a generalised copy, a different densification, a reprojection — produces both errors at once, and their areas are of similar magnitude because they come from the same displacement.
A tessellation with a matching total area and a large symmetric difference: where the compensating gap and overlap sit.

Verification Step: Wire the Four Assertions Into the Build

python
def test_no_gaps(cells, source, grid):
    tol = area_tolerance(source, grid)
    gaps = uncovered(cells, source, tol)
    assert not gaps, f"{len(gaps)} gap(s), largest {gaps[0].area:.4f}"


def test_no_overhang(cells, source, grid):
    assert not overhang(cells, source, area_tolerance(source, grid))


def test_no_overlaps(cells, grid, index):
    tol = area_tolerance(unary_union(cells), grid)
    dups = overlaps(cells, tol, index)
    assert not dups, f"{len(dups)} overlapping pair(s), worst {max(d[2] for d in dups):.4f}"


def test_symmetric_difference_within_tolerance(cells, source, grid):
    rep = partition_report(cells, source, grid)
    assert rep["symmetric_difference"] < rep["tolerance"], rep


def test_cell_count_is_stable(cells, expected):
    """A partition that silently loses a cell still tiles — badly."""
    assert len(cells) == expected, f"{len(cells)} cells, expected {expected}"

The last one catches a failure the geometric checks do not. Two adjacent cells merged by an over-eager cleanup step still tile the source perfectly, and the only symptom is a count that no longer matches the seed count.

Reading tessellation residuals back to their cause A table with five residual signatures as rows. A long thin ribbon following the source boundary points at a precision-grid mismatch between the clip and the source, and the fix is to snap both to the same grid before clipping rather than to widen the tolerance. A thin ribbon along an interior cell edge is the classic sliver from two cells snapped independently, and it is fixed at the noding step. A chunky polygon in the interior means a seed produced no cell at all, usually because it was duplicated or fell outside the window, and the fix is upstream in seed generation. A residual matching a whole cell's footprint means a cell was dropped after generation, typically by a cleanup pass that removed it as invalid. A residual that appears only around an interior ring means the hole was not carried through the clip, which is a different bug from all of the above and is invisible to a check written against the exterior ring alone. The note underneath makes the case for returning residual geometries rather than a boolean, since the shape is the diagnosis. Return the residual geometry — its shape names the step that produced it residual signature produced by fix at thin ribbon along the source edge precision-grid mismatch clip vs source snap both, then clip thin ribbon on an interior edge independent snapping the sliver case the noding step chunky polygon in the interior a seed produced no cell duplicate or outside seed generation residual the shape of one cell a cell dropped after build cleanup removed it the validity pass residual only around a hole interior ring not carried hole lost in clip the clip itself This is the argument for returning residual geometries rather than a boolean or an area. The number tells you the check failed; the shape and location tell you which of five different bugs you have, and that difference is most of the time spent fixing it.
What each residual shape tells you: gap and overhang geometry mapped to the step that produced it.

Edge Cases & Gotchas

Multi-part sources. A boundary with islands has to be validated part by part as well as in aggregate, because a tessellation that omits a small island entirely can still pass a whole-source symmetric-difference check if the island is smaller than the tolerance.

Interior rings. A source with a hole — a lake, an enclave — needs the hole checked as explicitly as the exterior. Cells covering the hole are overhang, and a check written against the exterior ring alone will not see them.

Curved boundaries. A boundary defined as an arc in the source format and densified to a polyline for tessellation is a different geometry, and the symmetric difference between them is real rather than an error. Densify once, validate against the densified version, and record which one the release’s boundary is.

Geographic coordinates. Areas computed in degrees are meaningless for a tolerance derived from a perimeter. Do the whole check in a projected CRS, or the tolerance will be wrong by a factor that varies with latitude.

Scale. On very large tessellations the union is the expensive step, and it is usually avoidable: validating tile by tile against the corresponding clip of the source gives the same answer, parallelises, and keeps memory bounded — the same windowing argument as everywhere else.

What to Do When the Check Fails on a Real Release

The checks are cheap; the decision after one fails is where the time goes, and there are only three sound outcomes.

Fix the geometry. Right whenever the residual maps to an identifiable step — a precision mismatch, a lost hole, a dropped cell. The residual shape names the step, the fix is local, and the check passes afterwards for the right reason. This covers most failures.

Accept and record. Legitimate when the residual is real and inherent: a source boundary defined with curved segments, a coastline whose definition genuinely differs between the source and the working CRS. The correct response is a recorded, quantified exception naming the affected region and its area, not a widened global tolerance — because a widened tolerance also hides the next unrelated failure.

Reject the release. Right when the residual is large and its cause is unknown. A tessellation that fails a soundness check for reasons nobody understands is a tessellation whose cells cannot be trusted individually either, and every downstream aggregate built on it inherits the doubt.

The outcome that is never sound is loosening the tolerance until the check passes. It converts a specific, located, reproducible failure into a silent one, and it does so in the artifact that every later validation run will use as its baseline. If the tolerance derived from the precision grid is genuinely too tight, the fix is to change the precision grid — deliberately, recorded, and with the check re-derived from the new value.