S2 Geometry

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

• Search, Analytics and Geo · 10 minNearby search with Redis GEOHow Redis stores locations in a sorted set using geohash scores, how GEOSEARCH finds nearby members, how to expire stale entries, and when to move to a spatial database.Read hereClose

  The problem

  "Show the nearest available drivers", "stores within 3 km", "friends nearby". The data is a large set of points that change often, and the question is always about a small neighbourhood. You want a fast, in-memory structure.

  How Redis does it

  Redis stores locations in an ordinary sorted set. Each member (a driver id) has a score that is a 52-bit geohash of its longitude and latitude. Geohash interleaves the bits of the two coordinates so that nearby places have nearby scores. A search turns a radius into a few score ranges, reads those ranges, then filters by exact distance.

  100%

  Figure SDA-SAG-09-1 · A nearby query in Redis · © forcsguy.com

  Typical commands:

  GEOADD drivers:blr 77.5946 12.9716 driver:42
  GEOSEARCH drivers:blr FROMLONLAT 77.60 12.97 BYRADIUS 2 km ASC COUNT 20 WITHDIST
  

  Design details

  • Partition the key. One sorted set for the whole planet is a hot spot and slow to search. Use a key per city, region or grid cell so each set is small and local, and shard keys across nodes.
  • Updates are cheap. Moving a member is another GEOADD, about O(log n). 75,000 updates per second is manageable on a few nodes.
  • Freshness. Sorted set members have no individual expiry. Keep a second sorted set lastseen with the update time as score, and run a job that removes members older than, say, 30 seconds from both sets.
  • Availability filter. Store only drivers who are available, or look up status after the search; keep the hot set small.
  • Accuracy. Redis uses a spherical model of the Earth, so distances can be off by a fraction of a percent, and results near a cell boundary rely on the exact filter. That is fine for "within 2 km", not for surveying.
  • Durability. Treat Redis as a rebuildable copy. The system of record is a database, and clients re-send their location every few seconds anyway.

  100%

  Figure SDA-SAG-09-2 · Keeping the hot set fresh · © forcsguy.com

  When Redis GEO is not enough

  Move to a spatial database such as PostGIS, or a purpose-built index, when you need polygons and fences, joins with other tables, constraints (opening hours, vehicle type) together with distance, or durable queries over history. Many systems combine them: a database for rich queries and Redis for the live, hot position data.

  Other grid systems are covered in the geofencing lesson and in the real-world reading: H3 (hexagons, good for aggregation and neighbours) and S2 (cells on a sphere).

  Real-world reading

  Related reading

  • Redis geospatial data typeRedisDocumentation
  • Redis GEOSEARCH commandRedisDocumentation
  • PostGIS documentationPostGIS project · PostGISDocumentation
  • H3: Uber's Hexagonal Hierarchical Spatial IndexUber Engineering · UberCase Studies

  Show 1 moreShow fewer

  • S2 GeometryGoogle · S2 GeometryDocumentation

  Open this lesson with its quiz and exercise