Bounding-Box Prefilters Before Exact Containment

An index answers a cheaper question than the one the pipeline is asking. An R-tree or quadtree returns the fences whose bounding boxes contain the query point, and for the irregular administrative and delivery-zone polygons a real geofencing platform holds, a bounding box is a poor approximation: a diagonal river-bank zone can fill under 20% of its own MBR, so four out of five candidates it returns are false. The exact containment kernel then spends most of its time proving negatives. This page sits under point-in-polygon algorithm benchmarks within Core Architecture & Latency Constraints, and it covers the cheap tests that sit between the index and the ring walk.

Concept and specification #

The technique is a filter cascade: a sequence of tests of increasing cost, each of which can produce a definite answer for some inputs and defers the rest. The cascade is worth building when each stage is much cheaper than the next and rejects (or accepts) a meaningful share.

Two kinds of stage exist and both are needed. A conservative outer bound — the MBR, the convex hull — can prove a point is outside but never that it is inside. A conservative inner bound — the largest inscribed circle, an inscribed rectangle — can prove a point is inside but never that it is outside. Most implementations have only the first kind, which is why they still run the full ring walk on every true positive, and true positives are the expensive case because the ray-casting loop cannot exit early for them.

$$C_{\text{total}}=c_1+(1-r_1),c_2+(1-r_1)(1-r_2),c_3+\prod _i(1-r_i),c_{\text{exact}}$$

where $c_i$ and $r_i$ are the cost and resolution rate of stage $i$. The cascade wins when $c_1\ll c_{\text{exact}}$ and $r_1$ is large, and it loses when a stage is expensive and rarely decides — which is the case against a stage many teams add first, the bounding circle, whose resolution rate on rectangular-ish fences is close to zero.

Ordering the stages by cost is not quite right; they should be ordered by cost per unit of resolution, and the inscribed circle is second on that measure despite deciding fewer cases, because it resolves the expensive case — a true positive that the ring walk would otherwise have to prove the hard way.

Step-by-step implementation #

1. Precompute the bounds when the fence is authored, never at query time. All three structures are pure functions of the geometry, so they belong beside it in the index payload and must be invalidated together with it.

from __future__ import annotations
from dataclasses import dataclass
import math
from shapely.geometry import Polygon

@dataclass(slots=True, frozen=True)
class FenceBounds:
    """Conservative outer and inner bounds, computed once at authoring time."""
    minx: float; miny: float; maxx: float; maxy: float     # outer: MBR
    cx: float; cy: float; r2: float                        # inner: circle, r squared
    hull: tuple[tuple[float, float], ...]                  # outer: simplified hull

def build_bounds(poly: Polygon, hull_max: int = 12) -> FenceBounds:
    minx, miny, maxx, maxy = poly.bounds
    # Largest inscribed circle: the point of maximum distance to the boundary.
    # polylabel gives it directly; a fallback is the centroid when it is inside.
    from shapely import ops
    try:
        pole = ops.polylabel(poly, tolerance=1.0)
    except Exception:
        pole = poly.representative_point()
    r = poly.exterior.distance(pole) if poly.contains(pole) else 0.0
    hull = poly.convex_hull.simplify(0.0).exterior
    coords = list(hull.coords)[:-1]
    if len(coords) > hull_max:                 # keep the cascade cheap
        step = len(coords) / hull_max
        coords = [coords[int(i * step)] for i in range(hull_max)]
    return FenceBounds(minx, miny, maxx, maxy,
                       pole.x, pole.y, r * r, tuple(coords))

2. Run the cascade in cost-per-resolution order, and short-circuit hard.

UNKNOWN, INSIDE, OUTSIDE = 0, 1, 2

def prefilter(b: FenceBounds, x: float, y: float) -> int:
    if x < b.minx or x > b.maxx or y < b.miny or y > b.maxy:
        return OUTSIDE                          # 4 ns, decides 41%
    dx, dy = x - b.cx, y - b.cy
    if dx * dx + dy * dy <= b.r2:
        return INSIDE                           # 9 ns, decides the expensive case
    if not _in_hull(b.hull, x, y):
        return OUTSIDE                          # 61 ns, decides another 12%
    return UNKNOWN                              # only now pay 1,900 ns

3. Simplify the hull, and keep the simplification conservative. A convex hull with 400 vertices costs more than the ring walk it was meant to avoid. Reducing it to at most a dozen vertices keeps the stage cheap — but the reduction must expand the hull rather than shrink it, or the stage stops being conservative and starts producing false negatives. Sampling vertices as above is safe only because a subset of a convex polygon’s vertices spans a shape contained within it, so the correct form takes the expanded hull: offset the simplified hull outward by the maximum deviation. In practice, computing the simplified hull and then buffering it by the simplification tolerance is the cheap way to stay safe.

4. Skip the cascade for fences that do not benefit. A near-rectangular fence has an MBR fill ratio near 1, so the MBR stage decides almost nothing and the hull stage decides nothing at all — the cascade is pure overhead. Store the fill ratio at authoring time and enable the hull stage only for fences below about 0.6.

5. Apply the same cascade to segment queries. The segment predicate has a larger candidate set and benefits more, with the slab clip replacing the point-in-MBR test.

Benchmark and verification #

Measured on 12 million queries against 1.2M polygons, mean MBR fill ratio 0.47, using ray casting as the exact kernel:

The exact-test column tells the story: the cascade removes 81% of ring walks, and the throughput improves 4.9× — a larger gain than switching the exact kernel from ray casting to a vectorised winding-number implementation, which the algorithm comparison measures at 2.1×. Removing work beats speeding it up, and the two compose.

The P99 column improves more than the mean, from 31 µs to 6 µs, because the tail was dominated by queries against complex polygons whose ring walk is long. Those are exactly the polygons where the inscribed circle resolves the true positives and the hull resolves the near misses.

Verification must be exhaustive on the conservativeness property, because a prefilter bug produces wrong answers rather than slow ones. Assert over a large random sample that prefilter returning OUTSIDE implies the exact test returns false, and INSIDE implies true; property-based testing with points drawn from the MBR is the right tool, and the assertion is cheap enough to leave enabled in staging permanently.

Failure modes and edge cases #

The hole case in the second row is the one that silently produces wrong triggers. polylabel on a polygon whose exterior ring is passed alone returns a point that may sit inside a hole — a courtyard excluded from a delivery zone, a lake excluded from a park — and the resulting circle asserts INSIDE for positions that are genuinely outside the fence. Always compute the inscribed circle against the full polygon including its interior rings, and verify with poly.contains(pole) before trusting the radius, as the code above does.

The multipart case is worth a similar caution because it is common in administrative boundaries. A borough consisting of a mainland part and an island has an MBR spanning the water between them, so the MBR stage rejects almost nothing and the hull stage covers open sea. Splitting multipart geometry into separate index entries fixes both, and it also improves the index’s own selectivity — the same argument made for overlap handling in handling polygon overlaps in quadtree partitions.

Related #

• Point-in-Polygon Algorithm Benchmarks — the parent topic and the exact kernels this cascade defers to.
• Optimizing Ray Casting vs Winding Number for GPS Streams — the kernel speedup this composes with.
• Segment-Crossing Detection Between GPS Samples — the same cascade with a slab clip at the front.