Lesser known things about Google’s S2

by Pramod Maurya

pic credit: https://opensource.googleblog.com/2017/12/announcing-s2-library-geometry-on-sphere.html

In this article, I will majorly be focusing on use-cases of Google’s S2 library. Google’s S2 library is a real treasure, mainly due to its capabilities for spatial indexing. As you put more and more geospatial data in a map, your ability to query it in a timely and effective manner reduces dramatically. This is a problem for the likes of Uber, Foursquare, Yelp and last year’s Pokemon Go who deal with colossal amounts of spatial data. This library was released 7 years ago, but this library didn’t get much attention what it deserves maybe because of not enriched documentation. Here I will try to guide through the implementation of radial search using S2.

What’s inside Google’s S2?

The S2 library attempts to resolve this using a very clever construct called the Hilbert Curve(also known as a Hilbert space-filling curve) which is a continuous fractal space-filling curve. It’s basically a curve that occupies a space, covering all the areas within that space. Hilbert curve is useful because it gives a mapping between 1D and 2D space that fairly well preserves locality. If (x, y) are the coordinates of a point within the unit square, and d is the distance along the curve when it reaches that point, then points that have nearby d values will also have nearby (x, y) values. The converse can’t always be true. There will sometimes be points where the (x, y) coordinates are close but their d values are far apart. This is great news for searching because it’s a lot easier to find points that are near to each other on a map when you can access them via their indexes and they are still close together. It means you don’t have to scan the whole list of points to find ones that are geographically close, but just a few either side of where your starting position is.

gif credit: https://upload.wikimedia.org/wikipedia/commons/7/7c/Hilbert-curve_rounded-gradient-animated.gif

Follow this link to play with Hilbert curve’s 2D to 1D representation

Why S2?

• S2 cells have a level ranging from 30 ~0.7cm² to 0 ~85,000,000km².
• S2 cells are encoded on an uint64, easy to store.
• The main advantage is the region coverer algorithm, give it a region and the maximum number of cells you want, S2 will return some cells at different levels that cover the region you asked for, remember one cell corresponds to a range lookup you’ll have to perform in your database.

RegionCoverer allows arbitrary regions to be approximated as unions of cells (CellUnion). This is useful for implementing various sorts of search and pre-computation operations. This will let you specify the minimum/maximum cell level and the maximum number of cells used for covering the 2D region.

type RegionCoverer struct {
   MinLevel int // the minimum cell level to be used.
   MaxLevel int // the maximum cell level to be used.
   LevelMod int // the LevelMod to be used.
   MaxCells int // the maximum desired number of cells in the approximation.
}

With the RegionCoverer defined with all the required constraints, we will be using covering method to get the list of CellID which is CellUnion.

func S2CellIdsCoveringGivenRadius(radius float32) s2.CellUnion {
   // LatLngFromDegrees returns a LatLng for the coordinates given in degrees
   latLng := s2.LatLngFromDegrees(point.Lat, point.Lng)   // PointFromLatLng returns an Point for the given LatLng   
   s2Point := s2.PointFromLatLng(latLng)
   
   angle := s1.Angle(radius / s2s.earthRadiusInMeter)
   
   // CapFromCenterAngle constructs a cap with the given center and angle
   sphereCap := s2.CapFromCenterAngle(s2Point, angle)
   
   region := s2.Region(sphereCap)
   
   // Covering returns a CellUnion that covers the given region and satisfies the various restrictions
   covering := s2s.rc.Covering(region)
   return covering
}

Assuming I have a list of locations stored in map[int]*DataPoint in which key can be UserId and value is DataPoint which looks like:

type DataPoint struct {
   point Point // Point is a struct with lat and lng attribute
   description string
   type string
   code string
   ...
}

Finally, to get all the nearby users we just need to use S2CellIdsCoveringGivenRadius method and to filter users from the aforementioned map.

func GetNearbyUsers(covering *s2.CellUnion, dataPoints map[string]*DataPoint) []string {
   var userIds []int
   for userId, dataPoint := range dataPoints {
      latLng := s2.LatLngFromDegrees(dataPoint.point.Lat, dataPoint.point.Lng)
      s2CellId := s2.CellIDFromLatLng(latLng)
      if covering.ContainsCellID(s2CellId) {
         userIds = append(userIds, userId)
      }
   return userIds
}

Congrats guys, we have solved the problem of radial/nearby search using S2. Hope this article helps you to unlock the mystery behind what’s inside Google’s S2.

Resources:

https://opensource.googleblog.com/2017/12/announcing-s2-library-geometry-on-sphere.html
https://news.ycombinator.com/item?id=10066616
https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view?pli=1#slide=id.i0
http://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/
https://blog.nobugware.com/post/2016/geo_db_s2_geohash_database/