Geofencing - many points against many polygons

Two million moving points, three million fences, and a customer system that will act on every event we emit. The requirements divide neatly into "make the matching possible" and "make the events trustworthy", and the second is harder.

Ask these before designing

• How many fences, and how big? Three million small fences and three thousand enormous ones are different indexes. A covering that produces 40,000 cells for one national-park-sized fence will quietly dominate the whole index.
• Is an enter event worth money? If it triggers billing, a duplicate is a refund and a missed one is a dispute, and the whole board tightens. If it turns a light on, at-least-once is fine and half this design is unnecessary.
• Does the crossing itself matter, or only the state? "Tell me when it enters" needs transition detection. "Tell me which devices are inside now" is a query and needs almost none of the hysteresis machinery.
• How long may an event be late? Two seconds means evaluating on the hot path of ingest. Two minutes permits a batch, and a batch is an order of magnitude cheaper.
• What counts as being inside? Inside the polygon, inside it for thirty seconds, or inside it with the engine off? Every product means the third and every spec says the first.
• Who owns the false positives? GPS is noisy by 5-50 m depending on sky. Somebody must choose between late events and duplicated ones, and that person is not the engineer.

Functional

• Define fences as circles or polygons, with an owner, a rule and an endpoint.
• Evaluate every incoming position against the fences that could contain it.
• Emit ENTER, EXIT and DWELL events with the position and time that caused them.
• Suppress events caused by GPS noise rather than by movement.
• Deliver each event to the owner’s endpoint with retries and an idempotency key.
• Answer "which devices are inside this fence now" without replaying anything.

Non-functional

• Event latency p95 under 3 s from the position that caused it.
• No duplicate ENTER for one crossing, enforced by a compare-and-set on the state row rather than by the evaluator being careful.
• Evaluation must be O(candidate fences), never O(all fences) - this is the requirement the whole index exists to satisfy and it should be stated as one.
• 99.95% for evaluation; delivery 99.9% with retries over 24 hours.
• Fence changes live within 60 s, including the re-covering of a redrawn polygon.
• Evaluation is idempotent per (device, fence, position timestamp), because the position stream will be replayed.

Explicitly out of scope

Producing the positions (that is the fleet-tracking board), routing and ETA, proximity search over points, indoor positioning and Bluetooth beacons - which solve the same product problem with entirely different physics.