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:

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.
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.
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).

Google S2 Visual Demo - 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.

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.

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.
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.

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).