Geofence enter and exit events
On the roadmap:Staff Engineer · step 3: Maps and location
Test points against polygons with ray casting, prefilter with a bounding box, and turn noisy location pings into stable enter and exit events.
In plain words
Given a location and a drawn area on a map, decide whether the location is inside. Then turn jumpy GPS pings into clean 'entered' and 'left' events.
Why it matters
Raw GPS jitters, so a naive check fires events again and again at an edge. A cheap box test first and a debounce afterwards keeps it fast and quiet.
Where you meet it
- Delivery and ride apps: 'driver arrived' and 'entered the airport zone'
- Store and campus notifications
- Fleet and asset tracking alerts
You will be able to
- Check a point against a polygon with ray casting
- Use a bounding box to skip most of the work
- Stop flapping events with a repeat threshold
In interviews
Comes up in 'design Uber', 'nearby friends' and any location-triggered alert.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Ray casting point-in-polygon
- A bounding-box prefilter
- A tracker that remembers which fences each device is in
- Debounce: a change must repeat before an event fires
export type Pt = [number, number];
export type Fence = { id: string; ring: Pt[] };
export function inside(p: Pt, ring: Pt[]): boolean {
let c = false;
for (let i = 0, j = ring.length - 1; i < ring.length; j = i++) {
const [xi, yi] = ring[i], [xj, yj] = ring[j];
if (yi > p[1] !== yj > p[1] && p[0] < ((xj - xi) * (p[1] - yi)) / (yj - yi) + xi) c = !c;
}
return c;
}
const box = (ring: Pt[]) => ({
minX: Math.min(...ring.map((p) => p[0])), maxX: Math.max(...ring.map((p) => p[0])),
minY: Math.min(...ring.map((p) => p[1])), maxY: Math.max(...ring.map((p) => p[1])),
});
export type Event = { device: string; fence: string; type: "enter" | "exit" };
export class GeofenceTracker {
private boxes: Map<string, ReturnType<typeof box>>;
private state = new Map<string, Set<string>>(); // device -> fences it is in
private pending = new Map<string, number>(); // device|fence -> consecutive disagreeing pings
constructor(private fences: Fence[], private confirm = 2) {
this.boxes = new Map(fences.map((f) => [f.id, box(f.ring)]));
}
ping(device: string, p: Pt): Event[] {
const now = this.state.get(device) ?? new Set<string>();
const events: Event[] = [];
for (const f of this.fences) {
const b = this.boxes.get(f.id)!;
const isIn = p[0] >= b.minX && p[0] <= b.maxX && p[1] >= b.minY && p[1] <= b.maxY && inside(p, f.ring); // box first
const was = now.has(f.id), key = `${device}|${f.id}`;
if (isIn === was) { this.pending.delete(key); continue; }
const n = (this.pending.get(key) ?? 0) + 1;
if (n < this.confirm) { this.pending.set(key, n); continue; } // debounce noisy pings
this.pending.delete(key);
if (isIn) now.add(f.id); else now.delete(f.id);
events.push({ device, fence: f.id, type: isIn ? "enter" : "exit" });
}
this.state.set(device, now);
return events;
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints geofence ok when everything passes. You need Node.js installed.
mkdir geofence && cd geofence
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Real systems do not test every fence. They index fences by area (an R-tree, or grid cells such as geohash, S2 or H3) and only test the few that are nearby.
- Large areas need curved-earth maths, and polygons with holes, such as a park around a lake, need extra handling.
- Apps also discard readings with poor accuracy and use dwell time and speed, not just a repeat count, before they fire an event.
Ways to test a location against many areas
| How it works | Cost as fences grow | Pick it when | |
|---|---|---|---|
| Bounding box, then ray casting (this lab) | A quick box test, then an exact point-in-polygon check | Grows with the number of fences | You have tens or a few hundred fences |
| Test every fence exactly | Run the exact check on all of them | Grows fastest | You have a handful of fences |
| Grid or geohash cells | Look up the cell and test only the fences touching it | Almost flat | Many fences and many devices |
| R-tree or a spatial database | A tree of nested boxes finds nearby shapes | Grows slowly | Many irregular shapes, or you already use a spatial database |
What it cannot do
It treats the earth as flat
That is fine for a campus. Over large areas the curve of the earth matters.
It trusts every ping
Real GPS readings carry an accuracy radius. A poor reading should count for less.
Polygons with holes are not handled
A park around a lake would need an extra rule for the inner ring.
No dwell time or speed
Real systems often require the device to stay inside for a while before an event fires.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Index many fences with a grid or R-tree
- Support polygons with holes
- Add a minimum dwell time before an enter event