Test a delivery catalogue for the places no zone reaches

19 October 2026 · 8 min read

A delivery catalogue built from polygons answers one question well: which zones reach this address. That shape makes overlaps announce themselves and leaves gaps silent. Ask about a street covered by both a city hub and a store's own ring, and the lookup hands back both matches, so you are forced to decide which one wins. Ask about the strip between two rings that almost meet and you get an empty list, indistinguishable from an address in another country. Nobody finds out which of the two it was until an order lands on it.

We hit this while building delivery-zones, a small Python library of ours for point-in-zone lookups over overlapping polygons (https://github.com/shipmindlabs/delivery-zones). The lookup side was the easy half. The half that keeps operations from having a bad evening is a test that asks the catalogue about the places nobody drew.

The constraint: you cannot ask a lookup where it is empty#

An index answers per position. Turning that into "where is coverage missing" exactly would mean computing the complement of a union of polygons with holes, a different and much heavier problem than a crossing test, and one whose answer is a geometry you still cannot usefully assert on in a test suite. What a reviewer wants in CI is not a multipolygon. It is a line that says "these places are unserved, start with this coordinate."

So we sample. A scan lays a lattice over an area, asks the index about every position, and groups the misses. That trades exactness for something a catalogue author can run on every change:

from delivery_zones import BoundingBox, ZoneIndex, scan_coverage, zones_from_geojson

index = ZoneIndex(zones_from_geojson(document))

report = scan_coverage(index, spacing=0.2, area=BoundingBox(0.1, 0.1, 2.9, 0.9))

assert report.is_complete, report.describe()

is_complete is deliberately not a threshold on a percentage; it is simply whether the report holds any gaps at all. A catalogue either reached every sampled position or it did not, and describe() is there to explain the failure at the moment the assertion fires.

Spacing is a required argument, because it is the resolution of the test#

There is no sensible default for spacing. It is not a tuning parameter, it is the size of the smallest hole the scan is able to see. A scan at a coarse spacing over a dense city will report complete coverage while a block-sized hole sits between two samples, and a scan fine enough to catch that hole over a national envelope will not finish. Only the person who knows what the zones represent can pick that number, so the library makes them pass it and refuses anything that is not a finite positive number:

scan_coverage(index, spacing=0.0)   # CoverageError

The same reasoning applies to the area. If you do not pass one, the scan falls back to the envelope around every polygon of every zone, via zones_envelope. That is the right default for one contiguous city and the wrong one for a catalogue of two distant clusters, where the envelope stretches across everything in between and the scan dutifully reports the countryside as an enormous gap. The default is a convenience, not a judgement about what you intended to serve. An empty catalogue has no envelope at all, and says so rather than scanning nothing:

scan_coverage(ZoneIndex([]), spacing=0.5)   # CoverageError: no zones to bound

Counting lattice positions is a floating-point problem#

The lattice step count looks like arithmetic you would write without thinking, and it is the one place in the scan where naive code silently loses the part of the area most likely to be broken, the far edge.

>>> (0.3 - 0.0) / 0.1
2.9999999999999996

A box three steps wide needs four sampled positions per axis, both ends included. Truncate that quotient and you get three, and the entire last column (the eastern boundary of the service area, where a ring tends to stop short) never gets tested. So the step count rounds span / spacing to the nearest whole number when the two differ by less than 1e-9, and only then adds one so both ends are sampled. A span that is an exact multiple of the spacing keeps its final column instead of donating it to binary floating point. Positions are then clamped to the box, so the lattice never reports a miss outside the area it was asked about.

This is the kind of detail that does not show up in a demo and shows up permanently in production. We take the same view of the crossing test itself, where the seam between two zones that share an edge is an arithmetic artefact rather than contested coverage, and has to be removed before any business rule runs.

A sample budget refuses the scan instead of running it#

Multiply a tight spacing by a wide envelope and you ask for billions of point-in-polygon tests. The failure mode we did not want is a test suite that hangs: no output, no error, someone cancels the job and the scan gets quietly deleted from CI.

So the scan computes columns times rows first and compares it against max_samples, whose default DEFAULT_MAX_SAMPLES is 1_000_000. If the product is over budget it raises before touching the index at all, and the message names the two things the caller can actually do about it: widen the spacing or shrink the area.

scan_coverage(index, spacing=0.5, max_samples=8)   # CoverageError

Refusing up front is the reason the budget exists. A scan that fails in a millisecond with an explanation is a usable tool, and a scan that runs for forty minutes and then reports coverage is not, however correct its answer.

Adjacent misses are one gap, not two hundred points#

A raw list of uncovered coordinates is nearly useless to the person who has to fix the catalogue. Twenty-five misses in the strip between two rings are one problem with one cause, and the report should say so. Misses are keyed by their (column, row) lattice position, and a flood fill over four-neighbour adjacency merges each connected run into a CoverageGap. Gaps come back sorted largest first, so the first entry is the one worth looking at:

report.samples            # 75
report.covered            # 50
report.uncovered          # 25
report.covered_fraction   # 0.6666666666666666
len(report.gaps)          # 1

gap = report.gaps[0]
gap.size                  # 25 sampled positions
gap.bbox                  # the envelope of those positions
gap.representative        # the sample nearest the gap's centre

Four-neighbour adjacency means two holes touching only at a diagonal are reported as two gaps. We prefer that, because diagonal contact at lattice resolution says nothing reliable about whether the underlying unserved areas are one region, and over-merging would hide the second cause behind the first.

representative is the member nearest the gap's bounding-box centre, and it exists for one reason: it is the coordinate you paste into a bug report or back into index.zones_containing(...) to see the hole for yourself. Reporting a bounding box alone would leave you to guess a position inside it, which for a crescent-shaped gap is not guaranteed to be uncovered at all.

That is what makes the one-line form worth having. describe() names the uncovered count out of the total, the number of gaps, the size of the largest and the coordinate at its centre, which is exactly enough for a failing assertion to be actionable from the CI log without anyone reproducing it locally.

Addresses you already have are a different question#

A lattice tests the area. It does not test the addresses that were actually refused last week, and those are the better regression corpus, because each one was somebody's order. For that there is uncovered_points, which checks the positions you hand it and returns the misses in the order supplied:

from delivery_zones import uncovered_points

missing = uncovered_points(index, refused_addresses)
assert not missing, missing[:5]

Order preservation is not cosmetic. When the input is a list read from a file or a query, the output lines up with it, and whoever is reading the failure can find the original row.

What it costs to run#

The scan's cost is the sample count, and nothing else grows with it: the index prepares each ring into an edge table and buckets polygons into a uniform grid once, so every covers call tests only the polygons registered in that cell rather than the whole catalogue. A fresh scan per catalogue change, at a spacing matched to the smallest zone you care about, is cheap enough to live in the normal test run, which is where it belongs. The honest limitation of sampling is that a hole smaller than the spacing can pass, and a scan that only runs before a release is probably a scan whose spacing nobody revisits.

The close is the same one we reach on most data-shaped bugs. A lookup is a question about one address, and no number of correct answers to it adds up to a statement about the catalogue. The statement has to be asked for separately, at a resolution the author chooses, with a budget that refuses the impossible version, and then it can fail a test run instead of an order.