Geofencing: is this point inside that area?

The problem

A geofence is a virtual boundary, usually a polygon on a map: a store's delivery area, an airport, a city. Apps ask two things: "is this point inside that fence?" and "tell me when a device enters or leaves one". The first is geometry; the second is geometry plus state over time.

The geometry: ray casting

Draw a ray from the point in any direction, say to the east. Count how many polygon edges it crosses.

• Odd number of crossings: the point is inside.
• Even (including zero): the point is outside.

100%

Figure SDA-SAG-08-1 · Ray casting test · © forcsguy.com

type Pt = [number, number]; // [x, y] or [lng, lat]
function inside(p: Pt, poly: Pt[]): boolean {
  let c = false;
  for (let i = 0, j = poly.length - 1; i < poly.length; j = i++) {
    const [xi, yi] = poly[i], [xj, yj] = poly[j];
    if ((yi > p[1]) !== (yj > p[1]) && p[0] < ((xj - xi) * (p[1] - yi)) / (yj - yi) + xi) c = !c;
  }
  return c;
}

Edge cases to decide on: a point exactly on an edge or vertex, polygons with holes (inside the outer ring and not inside any hole), fences that cross the antimeridian (longitude 180), and very large fences where straight lines on a flat map are not straight on a sphere. For city-sized fences, treating longitude and latitude as flat coordinates is usually fine.

Scale: do not test every fence

Testing a point against 200,000 polygons is too slow. Narrow down first:

1. Bounding box: reject fences whose box does not contain the point. Four comparisons.
2. Spatial index: an R-tree over bounding boxes, or cover each fence with grid cells (geohash, S2, H3) and look up the ping's cell to get a short candidate list.
3. Exact test: run ray casting only on the few candidates.

100%

Figure SDA-SAG-08-2 · Geofence matching pipeline · © forcsguy.com

Turning pings into events

An event is a change, so you must remember the previous answer per device: the set of fences it was inside. On each ping, compute the new set, then:

• fences in the new set but not the old produce enter events;
• fences in the old set but not the new produce exit events.

GPS is noisy, especially in cities, so a stationary phone can appear to cross a boundary. Reduce flicker with hysteresis: require a minimum distance outside before exit, or several consecutive pings, or a dwell time. Choose the debounce to match the use case; a "driver arrived" notice tolerates less delay than a billing zone.

Operational notes

• Partition the state by device id so one worker owns it and events stay in order.
• Make event handlers idempotent, since a ping may be processed twice.
• Version fences: when a polygon is edited, decide whether devices inside get re-evaluated immediately.
• Respect privacy: location is sensitive; keep only what you need and for as long as you need.

Real-world reading