Handling Polygon Edge Cases in High-Frequency Telemetry

High-frequency telemetry pipelines routinely ingest 5–50 Hz location streams across thousands of mobile assets. The moment those streams are intersected with geofence boundaries, the operational reality stops matching textbook GIS assumptions. Unhandled polygon edge cases rarely crash anything outright; instead they surface as gradual degradation — P99 spikes during boundary crossings, flapping zone-transition state, duplicate webhook emissions, and steady heap growth in long-running workers. This page is the boundary-stability deep dive under Memory-Constrained Spatial Processing, where the parent topic sets the hard RSS ceiling and this page keeps containment correct and deterministic underneath it. Everything here lives inside the per-event timing rules described in Core Architecture & Latency Constraints, so each mitigation is judged by whether it holds the budget at 40k–60k events/sec on a single node.

Concept & Specification #

A telemetry sample $p=(\lambda ,\varphi )$ is classified against a zone polygon $Z$ by the predicate $\text{inside}(p,Z)$. The instability engineers actually observe is not that the predicate is wrong but that it is non-deterministic near $\partial Z$, the boundary. Three intersecting realities drive it:

1. IEEE 754 quantization jitter. Double-precision arithmetic introduces micro-degree error during projection. When a coordinate lands within $\sim 10^{-9}$ degrees of an edge, the point-in-polygon evaluation kernel inside GEOS can alternate between inclusion and exclusion across successive samples because of coordinate snapping in the edge-crossing test.
2. Upstream topology debt. GIS exports frequently ship polygons with mixed winding orders, duplicate vertices, or self-intersections. Validating malformed rings at runtime costs $O(n^2)$ on the offending ring and can silently change boundary semantics, producing false-positive entries.
3. Allocation-driven GC pressure. Pipelines that build a fresh Point/Polygon per event trigger constant minor collections, fragment the heap, and grow the resident set until the worker is OOM-killed.

The objective is a classifier that is idempotent at the boundary: identical inputs yield identical states, and a coordinate hovering on $\partial Z$ does not emit a stream of transitions. The tunable parameters are small and worth fixing explicitly.

The snap step replaces $p$ with $\hat{p}=\epsilon \cdot \mathrm{round}(p/\epsilon )$, which collapses sub-centimetre jitter onto a stable grid so that repeated samples at the same physical location produce bit-identical inputs to the kernel.

Step-by-Step Implementation #

Prerequisites: Python 3.11+, shapely>=2.0 (vectorized GEOS bindings), numpy>=1.24. Zone geometries are repaired once at build time and consumed read-only by workers. Data shapes: telemetry arrives as an (M, 2) float64 array of (lon, lat); envelopes are kept as a parallel (Z, 4) array.

Stage 1 — Vectorized AABB pre-filter #

Cache each polygon envelope as a flat (minx, miny, maxx, maxy) row and reject the overwhelming majority of events with NumPy comparisons before the GEOS kernel is ever touched. In dense deployments this removes 85–95% of kernel invocations.

import numpy as np
import numpy.typing as npt

def aabb_candidates(
    points: npt.NDArray[np.float64],   # shape (M, 2): lon, lat
    envelopes: npt.NDArray[np.float64],  # shape (Z, 4): minx, miny, maxx, maxy
) -> npt.NDArray[np.bool_]:
    """Return an (M, Z) mask of point/zone pairs that survive the bbox test."""
    lon = points[:, 0][:, None]
    lat = points[:, 1][:, None]
    inside_x = (lon >= envelopes[:, 0]) & (lon <= envelopes[:, 2])
    inside_y = (lat >= envelopes[:, 1]) & (lat <= envelopes[:, 3])
    return inside_x & inside_y

Gotcha: build envelopes once and keep it resident. Recomputing polygon.bounds per event re-enters the GIL-bound Python layer and defeats the whole point of the pre-filter.

Stage 2 — Deterministic snapping with hysteresis #

Snap to the $\epsilon$ grid, then gate transitions behind a per-(asset, zone) counter so a boundary-hugging track cannot emit a webhook storm.

from dataclasses import dataclass, field

EPSILON = 1e-7  # ~1.1 cm at the equator

def snap(points: npt.NDArray[np.float64]) -> npt.NDArray[np.float64]:
    return np.round(points / EPSILON) * EPSILON

@dataclass(slots=True)
class Hysteresis:
    """Idempotent state machine: flips only after N agreeing samples."""
    window: int = 3
    state: bool = False
    _streak: int = field(default=0)
    _pending: bool = field(default=False)

    def update(self, raw_inside: bool) -> bool | None:
        """Return the new state on a confirmed flip, else None."""
        if raw_inside == self.state:
            self._streak = 0
            return None
        if raw_inside != self._pending:
            self._pending = raw_inside
            self._streak = 1
            return None
        self._streak += 1
        if self._streak >= self.window:
            self.state = raw_inside
            self._streak = 0
            return self.state
        return None

Gotcha: use numpy.isclose with an absolute tolerance, never raw ==, when comparing snapped coordinates — relative tolerance collapses to zero near the prime meridian and the equator.

Stage 3 — Build-time topology and winding enforcement #

Never repair topology at runtime. Orient exterior rings counter-clockwise, strip collinear vertices, and freeze the result. This is the same build-time debt-shifting used for polygon simplification for high-throughput streams.

from shapely import Polygon, prepare, set_precision
from shapely.ops import orient

def freeze_zone(raw: Polygon, tol: float = 1e-8) -> Polygon:
    """Repair + normalize a zone once, offline. Workers consume the result."""
    if not raw.is_valid:
        raw = raw.buffer(0)                # heal self-intersections
    clean = orient(raw, sign=1.0)          # CCW exterior, CW holes
    clean = set_precision(clean, grid_size=tol)  # snap vertices to grid
    clean = clean.simplify(tol, preserve_topology=True)
    prepare(clean)                         # cache the GEOS prepared index
    return clean

Stage 4 — Allocation-free hot path #

Reuse pre-allocated arrays and call shapely.contains on a vectorized batch instead of per-event Python objects. Pair it with GC deferral during burst windows.

import gc
import shapely

def classify_batch(
    snapped: npt.NDArray[np.float64],  # (M, 2), pre-snapped
    zone: Polygon,                     # already prepared by freeze_zone
) -> npt.NDArray[np.bool_]:
    pts = shapely.points(snapped[:, 0], snapped[:, 1])
    return shapely.contains(zone, pts)   # vectorized, single GEOS round-trip

gc.set_threshold(50_000, 500, 1000)      # defer gen-2 scans under load

Gotcha: shapely.contains is exclusive of the boundary; covers is inclusive. Pick one per deployment and document it — mixing them across services is a classic source of off-by-one-vertex disputes between teams.

Benchmark / Verification #

The fixture replays a 50k events/sec stream of mixed urban tracks, 30% of which deliberately hug zone boundaries, against 8k zones on a single node under a 1.5 GB RSS ceiling. Figures are steady-state over a 72-hour soak.

The dominant win is the pre-filter: with a rejection rate $r$, the expected per-event cost is

$$T_{\text{eval}}=\underbrace{O(1)}<em>\text{bbox}+(1-r),\underbrace{O(n)}</em>\text{GEOS edge scan}$$

so at $r\approx 0.92$ the $O(n)$ term is paid on fewer than one event in ten. Validate correctness with three synthetic datasets: coordinates exactly on vertices, coordinates at $\epsilon$ distance from edges, and rapid ingress/egress tracks. Assert that state transitions are monotonic within a crossing, that webhook rate stays within SLA, and that RSS is flat. Profile lingering hotspots with py-spy record and diff allocation with tracemalloc.take_snapshot().compare_to(prev, "lineno") every 10k events; both should show the static zone catalog dominating and zero per-event geometry growth.

Failure Modes & Edge Cases #

• NaN / infinite coordinates. A dropped GPS fix can deserialize to nan. Every comparison against nan is False, so a bad sample silently reads as outside every zone and can fire a spurious exit. Filter with np.isfinite(points).all(axis=1) before Stage 1 and route rejects to a dead-letter path rather than the classifier.
• Self-intersecting / bowtie polygons. If one slips past the build step, contains results become undefined along the crossing. The buffer(0) heal in freeze_zone is the guard; gate the build on is_valid and fail the deploy, never the worker.
• Empty or single-point geometries. Degenerate zones (zero-area rings) make every event ambiguous. Drop them at build time and emit a catalog-integrity metric.
• Antimeridian and pole wrap. A zone straddling ±180° has an envelope spanning the whole globe, so the AABB pre-filter stops rejecting anything. Split such zones into two at build time so envelopes stay tight.
• GC pressure under burst. Even with deferred thresholds, a sustained surge can starve the gen-2 collector until fragmentation climbs. When fragmentation exceeds 40%, trigger a controlled restart via graceful SIGTERM rather than waiting for the OOM killer.
• GIL contention. A single Python loop calling scalar contains serializes all cores. The batched shapely.contains call releases the GIL inside GEOS; keep batches in the 64–256 range so IPC and call overhead amortize, consistent with the offload boundaries set by the overall latency budget allocation.
• Degraded mode. When P95 breaches $L_{deg}=15$ ms, drop exact evaluation, classify on the cached AABB result alone, emit a spatial_eval_degraded metric, and queue exact reconciliation for async catch-up so ingestion never blocks.

Related #

• Memory-Constrained Spatial Processing — the parent topic: the RSS ceiling, contiguous index layout, and GC control this page’s boundary logic runs inside.
• Point-in-Polygon Algorithm Benchmarks — the ray-casting vs winding-number kernel behaviour that determines how a given polygon flaps near its edges.
• Polygon Simplification for High-Throughput Streams — the build-time vertex-reduction step that feeds the frozen, pre-validated zones used here.
• Up one level: Core Architecture & Latency Constraints — the per-event timing budget every boundary check must fit inside.