Spatial candidate and exact-predicate joins

Last updated: 6 Oct 20265 min read

tutorial

A spatial join should use cheap coarse tests to limit candidates, then evaluate the true geometry predicate on every candidate that survives.

Separate filter from answer

Suppose a delivery zone covers a curved district. A bounding rectangle and cell cover are fast to index, but both include places outside the district. First match events against the zone bounding boxes or intersecting cells; only then run the exact geometry test. Report candidate pairs and accepted pairs separately. An approximation is useful when it saves work, but a candidate false positive must not become a published delivery-zone assignment.

Include the boundary cells

Do not index a polygon only by cells whose centers lie inside it. Narrow portions and border strips can disappear entirely. Build a conservative cover of every cell intersecting the polygon, or expand the search with a verified neighbor rule. After the exact predicate, choose whether a point on the border belongs to one zone, both zones or neither. The ownership rule belongs in the dataset contract, not an accidental library default.

Control duplicate matches

Overlapping sales territories can legitimately yield two matches for one event. A dispatch zone may require exactly one winner with a deterministic priority and effective-date rule. Never hide overlaps with an arbitrary first row from an unordered join. Fact grain determines whether one event can contribute to more than one output total; validate that rule before aggregation.

Version the shapes

A boundary revision changes historical assignments even if no event moved. Store a shape version and effective interval, then join each event to the version valid for its business time or explicitly reprocess affected history. A current map polygon cannot explain an older daily total. Record input event generation, zone-set generation and output generation in the release evidence.

Measure selectivity and skew

Count the ratio of candidate pairs to exact matches, exact predicate CPU time, cells scanned and the hottest zone. If the coarse cover returns nearly every shape, it is not reducing work. If one dense zone dominates, subdivide it or process its candidates in bounded shards. Reconcile the final set by stable event ID, zone ID and shape version to catch losses at cell edges.

Implementation

# Coordinates are in one local projected plane for this small fixture.
events = {"delivery-47": (4, 3), "delivery-48": (8, 8)}
zones = {"zone-west": [(0, 0), (6, 0), (0, 6)],
         "zone-east": [(7, 7), (12, 7), (12, 12), (7, 12)]}

def inside_polygon(point, vertices):
    east, north = point
    inside = False
    for index, (start_east, start_north) in enumerate(vertices):
        end_east, end_north = vertices[index - 1]
        if (start_north > north) != (end_north > north):
            crossing = start_east + (north - start_north) * (end_east - start_east) / (end_north - start_north)
            if east < crossing:
                inside = not inside
    return inside

def zone_matches(event_points, zone_polygons):
    candidates, matches = [], []
    for delivery_id, point in event_points.items():
        for zone_id, polygon in zone_polygons.items():
            easts, norths = zip(*polygon)
            if min(easts) <= point[0] <= max(easts) and min(norths) <= point[1] <= max(norths):
                candidates.append((delivery_id, zone_id))
                if inside_polygon(point, polygon):
                    matches.append((delivery_id, zone_id))
    return candidates, matches

candidate_pairs, exact_pairs = zone_matches(events, zones)
assert candidate_pairs == [("delivery-47", "zone-west"), ("delivery-48", "zone-east")]
assert exact_pairs == [("delivery-48", "zone-east")]

Performance and operating cost

A naive join costs O(E × Z) bounding checks for E events and Z zones; an indexed cell or rectangle lookup reduces candidate generation toward the number of actual nearby pairs. Exact predicate cost grows with candidate count and polygon complexity. Building a cover adds storage and update work when boundaries change, so track both false-positive rate and missed-match tests.

Common Mistakes

Do not publish bounding-box matches as exact polygon matches.
Do not omit intersecting border cells just because their centers are outside.
Do not collapse legitimate overlapping-zone matches without a documented winner rule.