# Lesser known things about Google’s S2

by Pramod Maurya

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.

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/