Half-open delivery zones: the shared street belongs to exactly one

14 October 2026 · 9 min read

Draw two delivery zones against the same street and you get a line of addresses sitting exactly on the boundary, and a containment test that is inclusive on both sides hands those doorsteps to two stores at once. Make it exclusive on both sides and nobody gets them. The seam between two zones is not a business question, so a business rule should not be the thing that answers it: the crossing test itself can be half-open, and then a shared edge belongs to exactly one zone by construction.

An overlap is deliberate; a seam is arithmetic#

Overlapping coverage is normal, and we design for it. A city-wide hub ring and one store's own ring routinely cover the same district, and which of them serves an address is a rule the business owns: priority, smallest area, nearest store. Our delivery-zones library (https://github.com/shipmindlabs/delivery-zones) keeps that separation. zones_containing collects every match in the order the zones were declared and hands the list to a policy, and the default policy keeps all of them, because picking a winner belongs to the caller rather than to the index.

A seam looks like the same problem and isn't. Two districts cut from one boundary set share an edge, not an area. The addresses along that edge are not contested coverage, they are an artefact of where the arithmetic falls. If a lookup returns both zones for them, a policy will still produce an answer, and the answer will be wrong in a way you cannot see from outside. by_priority(TieBreak.FIRST) ends up resolving the seam by declaration order, so a doorstep changes store the moment somebody appends an unrelated feature to the catalogue file. by_smallest_area(TieBreak.RAISE) compares two districts that have no relationship to each other and picks whichever is smaller, or refuses the order. Neither outcome is a decision anyone made.

So the seam has to be gone before the policy ever runs.

The decision lives in two strict comparisons#

The containment test is an even-odd crossing count. You cast a ray east from the position and count how many edges of the ring it crosses. Both of its comparisons are strict, and that is the whole mechanism.

def wraps(self, lon: float, lat: float) -> bool:
    """Even-odd crossing count of a ray running east from the position."""
    inside = False
    for lat_start, lat_end, lon_start, slope in self.edges:
        if (lat_start > lat) != (lat_end > lat):
            if lon < lon_start + (lat - lat_start) * slope:
                inside = not inside
    return inside

The first comparison decides whether an edge spans the ray's latitude at all. Because both halves use a strict >, an edge counts only when exactly one of its endpoints sits strictly above the ray, so an endpoint lying exactly on the ray contributes through the edge that continues upward past it and not through the edge that ends there. A ray passing through a vertex is therefore counted once, a ray grazing a local minimum or maximum is counted twice or not at all, and the parity stays correct with no special case for vertices.

The second comparison decides which side of the edge the position is on, and lon < means a position lying exactly on an edge is treated as being immediately east of it. That single asymmetry is what makes borders half-open. For a ring, the consequence is fixed and you can check it:

Two zones meeting along a street cannot both claim it, because the street is one zone's eastern or northern edge and the other's western or southern one.

Two rectangles and the street between them#

from delivery_zones import ZoneIndex, zones_from_geojson


def rect(zone_id, store_id, min_lon, min_lat, max_lon, max_lat):
    return {
        "type": "Feature",
        "id": zone_id,
        "geometry": {
            "type": "Polygon",
            "coordinates": [
                [
                    [min_lon, min_lat],
                    [max_lon, min_lat],
                    [max_lon, max_lat],
                    [min_lon, max_lat],
                    [min_lon, min_lat],
                ]
            ],
        },
        "properties": {"store_id": store_id, "fee_tier": "standard"},
    }


catalogue = {
    "type": "FeatureCollection",
    "features": [
        rect("west", "store-west", 13.37, 52.51, 13.40, 52.54),
        rect("east", "store-east", 13.40, 52.51, 13.43, 52.54),
    ],
}

index = ZoneIndex(zones_from_geojson(catalogue))

# an address on the shared street, longitude 13.40
[zone.zone_id for zone in index.zones_containing((13.40, 52.52))]  # ["east"]
index.covers((13.40, 52.52))                                       # True

The western zone is not excluded by a cheap pre-filter, incidentally. Its bounding box does contain the position (BoundingBox.contains is inclusive on all four sides), so the lookup has to examine it as a candidate, and the ring is what refuses it. That division is deliberate: an envelope only widens the candidate set, so it can afford to be generous, while the crossing test is the one place where exactness matters. A horizontal seam behaves the same way along latitude. The southern zone's northern edge is outside it and the northern zone's southern edge is inside, so a point on a shared east-west street resolves to the northern zone. For a one-off check against a single polygon, without building an index, there is point_in_polygon.

With the seam closed, the policy recovers its real meaning. More than one match now implies an overlap somebody drew on purpose, which makes by_priority(TieBreak.RAISE) usable as an assertion over the catalogue rather than a dispatch nicety: two zones cover this address and neither claims precedence (priority is 0 when undeclared), so the catalogue is incomplete, and we would rather find that in CI than in a dispatcher's queue.

The seam the test cannot close#

Half-open borders decide a shared edge only when it is genuinely shared, when both rings use the same coordinate values along it. Two districts digitised separately, or one of them re-exported through a tool that rounds, leave a sliver nobody covers, and no containment rule can repair that, because the geometry is simply missing. Some of the damage a re-export does is already absorbed. A repeated closing position is discarded when a ring is built, a repeated vertex and an unclosed ring read exactly the same as a clean closed one, and a ring with fewer than three distinct positions raises GeometryError at load instead of quietly dropping out of coverage. A moved coordinate is a different polygon, though, and it will be treated as one.

What we can do is find the hole before a customer does:

from delivery_zones.coverage import scan_coverage

report = scan_coverage(index, spacing=0.0007)
assert report.is_complete, report.describe()

The scan samples a lattice over the envelope of the indexed zones and clusters adjacent misses, so one hole is reported once instead of once per sample, and describe() hands the assertion a line naming how many positions are uncovered, how large the worst gap is and a representative position inside it. Three limits are worth stating plainly rather than discovering later. A gap narrower than the spacing slips between samples. A sample landing exactly on a border falls to whichever side the half-open rule gives it, which is well defined but means a spacing aligned with the rings tells you less than one that isn't. And the default envelope finds holes inside the catalogue, not a district that was forgotten entirely, so for that you pass an explicit area.

What it costs to run#

Building the index pays the preparation once. Each ring is flattened into an edge table of (lat_start, lat_end, lon_start, inverse_slope) tuples with horizontal edges dropped, since a horizontal ray never crosses one, which also makes the slope division safe to precompute. The inner loop is then two comparisons and one multiply-add per edge, with no division and no tolerance. Polygons are bucketed into a uniform grid keyed by their envelopes, at most _MAX_GRID_SIDE cells a side, so a lookup examines only the polygons registered in the address' cell and tests each one's bounding box before its rings. An index is a snapshot that prepares every ring once, and when the catalogue changes we build a new one rather than mutating it.

The honest limits are geometric, not performance-related. Coordinates are planar degrees, so nothing wraps at the antimeridian, which a city catalogue does not touch, and we would rather say that out loud than imply coverage we do not have. Polygon area is in square degrees, which does not measure ground area but orders nearby polygons the same way metres would, and that ordering is all that ranking overlaps needs. Distance to a serving store is a great-circle line (EARTH_RADIUS_M = 6371008.8), a line over the ground rather than a route along it. Travel time stays a hook, because streets, traffic and vehicle are not in a polygon, and the constant-speed estimator shipped next to it is for tests and rough delivery tiers, not routing.

Close#

The boundary case is the common case here. Every street that separates two zones is made of addresses, and all of them land on the line. A tie-break policy can produce an answer for them, but it cannot produce a stable one, because it is answering a question nobody asked. Make the crossing test half-open and the seam stops being a decision at all, which leaves the policy for the overlaps you actually drew.