# Design Choices for Location Based Services III

Let’s jump back in where we left off with Quad Trees. You remember those, right? Or **you are** experiencing memory leaks just like me?

Need a refresher? didn’t you read the blog I sent you? I know you didn’t. Ah! no worries, we’ll figure it out.

# Google S2 Geometry

S2 (aka S2 Geometry Library) is **a** **spherical geometry library** and **spatial indexing system**. It is an open-source C++ library developed and used extensively by Google.

It **works directly on a sphere** instead of projecting the world onto a flat 2D plane. This makes it robust for global applications, avoiding the distortions or seams—like **those at the** Poles or the International Date Line—that plague flat maps.

Internally, S2 is a set of math functions mapping 2D (latitude, longitude) points into S2 cell IDs. **This simplifies** 2D coordinates (double, double) into **highly cacheable,** 1D 64-bit integer lookups.

The S2 library solves a fundamental problem in global mapping: **how to represent and query locations (like points, lines, and polygons)** anywhere on Earth without the distortion, discontinuities, and singularities that occur when using traditional planar map projections (like the Mercator projection).

## S2 Architecture

S2 performs a 3-step transformation:

1. **Sphere to Cube:** It projects the Earth onto the six square faces of a cube. This avoids the singularities at the poles and reduces the distortion found in traditional map projections.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765823538764/d9e5d2c0-7d0c-4d0f-afe2-3531dc155c88.png align="center")
    
2. **Hierarchical Decomposition:** Each face is divided into a **quadtree**. This subdivision can go as deep as **Level 30**, where a single leaf node represents roughly **0.74 cm² to 1 cm²** of the Earth's surface.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765823554077/03aa247a-f25a-409e-abbe-7b7bace3dc59.png align="center")
    
3. **Linearization:** Finally, S2 uses a **Hilbert Space-Filling Curve** to traverse and number the cells. This converts 2D positions into a 1D index (the Cell ID).
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765823605307/38c1aa71-aa1c-48f1-9e3d-1850a15c68af.png align="center")
    

### **Google S2 Visual Demo** - [https://s2viz.pavittarx.com/](https://s2viz.pavittarx.com/)

### **What is Hilbert Curve?**

The **Hilbert Curve** is the secret sauce of the S2 Library. It is used to map the sphere onto a **1D index**.

The Hilbert Curve has a crucial property: two points that are close on the curve will also be close on the map. Hence, the Hilbert Curve **preserves spatial locality**.

Google S2 powers a variety of applications and systems. It is employed by **Google Maps** and **MongoDB** (for its geospatial indexing). It is famously used by **Pokémon Go** for the placement and distribution of in-game assets.

# Uber H3

Uber’s H3 (Hexagonal Hierarchical Spatial Index) is designed for smoothing, movement, and analytics, whereas S2 is tailored more towards storage and containment. H3 utilizes a hexagonal system for geospatial indexing, a departure from the traditional square-based approach used in previous algorithms.

**Uber H3 (Hexagonal Index)** is built for **analyzing movement—like tracking rides or visualizing traffic**. S2, on the other hand, **is better for just storing location data.**

Quadtrees use squares, which have **8 neighbors (4 distinct edges and 4 corners)**. Consequently, moving **diagonally covers more distance** than moving horizontally, causing **heatmaps to look blocky**—much like Minecraft. Hexagons, conversely, create smooth and balanced grids. A **hexagon has 6 neighbors**, each **equidistant from the center,** meaning neighbor traversal uses the same math in every direction. This results in uniform movement and heatmaps that look smooth and natural.

## H3 Architecture

Standard maps often use cylindrical projections (like Mercator) which distort size near the poles. H3 takes a completely different approach to minimize this distortion.

1. **Sphere to Icosahedron (20 sided die)**
    
    It projects the Earth's spherical surface onto these 20 flat triangular faces. Because an icosahedron approximates a sphere much better than a cylinder or a cube does, the distortion of landmasses is significantly lower.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765827475704/b4af2434-009a-4659-a214-23a73d52f194.png align="center")
    
      
    
2. **Hexagons replace triangles**
    
    H3 fills these faces of Icosahedron with hexagons. A single triangle on a grid actually only has 3 edge neighbors, but the *vertices* of the icosahedron meet in complex ways (**5 triangles meet at a point)** this results in **(12) neighbors** which makes it **harder to calculate movement**. Additionally, **hexagons are equidistant. distance from center of one hexagon is equal to another.**
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765827455967/5a0d9eb4-7a85-4cab-bc82-c71785058a0d.png align="center")
    
3. **Aperture-7 System**  
    H3 has 16 levels of resolution, and each child splits into 7 child hexagons. H3 uses fuzzy containment, as 7 hexagons **do not** fit perfectly inside a larger hexagon. They spill over the edges slightly. You cannot say a child is 100% inside parent. It is excellent for gradients which naturally blur data, exactly what is needed for heatmaps or pricing. you want them to transition smoothly not cut sharply.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765827443779/237232c2-61b4-4860-9c20-90f144f91c67.png align="center")
    

Pentagon is here.. Well, the mathematical one, not the military.

In order to make the math work, H3 hides 12 pentagons (5 sided polygon) at specific points on Earth (mostly at oceans) to close the sphere. Why you ask? You cannot tile a sphere *perfectly* with only hexagons (mathematically impossible; it's Euler's formula).

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765827422180/9085978f-3a72-41e8-b491-33f707ca5c15.png align="center")

If a cell has high demand, Uber smoothens out the surge to neighboring cells, so you do not need sharp increase in price just walking 10 meters.

## H3 Visualizer - [https://h3viz.pavittarx.com/](https://h3viz.pavittarx.com/)

**Related Links ...**

* [Why every world map is wrong - Kayla Wolf](https://www.youtube.com/watch?v=eTYsIePy5zg)
    
* [How the World Map Looks Wildly Different Than You Think](https://www.youtube.com/watch?v=lPNrtjboISg)
    
* [Hilbert Curve](https://www.youtube.com/watch?v=3s7h2MHQtxc)