Point in polygon (Wikipedia)

Ideas you will meet

Geospatial

Geohash, quadtree, H3 and location search.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Search, Analytics and Geo · 11 minGeofencing: is this point inside that area?How to test a location against a polygon with ray casting, why a bounding box and a spatial index come first, and how to turn position pings into reliable enter and exit events.Read hereClose

  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

  Related reading

  • Point in polygon (Wikipedia)Wikipedia contributors · WikipediaDocumentation
  • S2 GeometryGoogle · S2 GeometryDocumentation
  • PostGIS documentationPostGIS project · PostGISDocumentation
  • H3: Uber's Hexagonal Hierarchical Spatial IndexUber Engineering · UberCase Studies

  Show 1 moreShow fewer

  • Redis geospatial data typeRedisDocumentation

  Open this lesson with its quiz and exercise