`mapillary/s2geometry`: The 64-Bit Index That Makes the Earth Queryable
A deep dive into the spherical data structure behind fast geospatial search, local neighborhood lookups, and the surprisingly elegant math that replaces flat maps with a hierarchical planet.
- S2 turns the Earth into a locality-preserving integer index, which makes spatial search feel like database work instead of geometry work.
- Its real trick is not just spherical accuracy, but the ability to navigate hierarchy, containment, and neighbors with one 64-bit cell ID.
- Compared with H3 and Geohash, S2 is the strongest fit when strict containment and robust spherical indexing matter more than hex-grid smoothing or simplicity.
- The Mapillary use case shows why this matters in practice: indexed geometry scales better than ad hoc latitude and longitude bookkeeping.
The unusual thing about mapillary/s2geometry is not that it understands maps. It is that it makes the planet look like an index key. Once location becomes a 64-bit cell ID, you can ask database-style questions about geography: what is nearby, what contains what, what overlaps what, and what can be pruned before anyone does expensive math?
The Earth, Reduced to a 64-Bit Integer
That is the core idea behind S2. Instead of treating latitude and longitude as the final answer, the library maps the sphere onto six cube faces, then subdivides those faces into a recursive hierarchy of cells. The result is a compact identifier that preserves locality well enough to support fast search and range scans.
The payoff is bigger than convenience. A place on Earth becomes something you can sort, compare, store, and traverse with bit operations. That is a rare combination in geospatial systems, where precision and speed usually fight each other.
Why Flat Maps Fail at Planet Scale
| System | Cell shape | Hierarchy | Strength | Weakness | Best fit |
|---|---|---|---|---|---|
| S2 | Square cells on cube faces | Strict parent-child containment | Strong spherical indexing and robust containment | More complex mental model | Spatial search, indexing, and geofencing |
| H3 | Hexagons | Hierarchical, but different containment trade-offs | Smooth neighborhood behavior and flow analysis | Less exact containment semantics | Aggregation and movement analysis |
| Geohash | Rectangular grid | Simple string encoding | Easy to implement and explain | Distortion and edge discontinuities | Basic coarse indexing |
Flat projections are convenient until they are not. Mercator-style thinking makes the poles weird, the dateline awkward, and distance comparisons harder than they should be. S2 avoids that entire category of bugs by working natively on the sphere, then using a hierarchy that is built for computation rather than cartography.
This is why the library feels more like a data structure than a map package. It is not trying to draw the world. It is trying to make the world queryable.
The Trick: Cube Faces, Then a Hilbert Curve
The design starts with a simple compromise: approximate the sphere with six cube faces. Each face is recursively subdivided, and a Hilbert curve orders the cells so that nearby places tend to stay nearby in the encoded space. That locality is the whole game.
The important detail is not just that the IDs are compact. It is that the ordering supports useful traversal. Nearby cells are not random neighbors in ID space, so range scans can approximate geographic neighborhoods without brute force searches.
Why S2CellId Is the Real Product
The headline object in this codebase is S2CellId. The rest of the library builds around it. It encodes face, position, and level in a single 64-bit integer, which means parent, child, and neighbor operations can be expressed with very cheap bit logic.
S2CellId id = S2CellId::FromPoint(point);
if (id.is_valid()) {
S2CellId parent = id.parent(id.level() - 1);
S2CellId next = id.next();
S2Point center = id.ToPoint();
}This is the implementation story in miniature. You do not build a heavy tree object just to ask where a cell belongs. You manipulate the encoded integer directly, and the hierarchy falls out of the bits.
That choice matters for performance and for ergonomics. When the hierarchy is encoded in the identifier itself, traversal becomes cheap, and the data model stays small enough to use everywhere.
S2Point and S2Cell: Precision Without the Geometry Tax
S2Point handles the 3D vector math. S2Cell handles the geometric work such as subdivision, bounds, and area. That split keeps the low-level index lightweight while giving higher-level operations a place to live.
The 3D approach is doing a lot of work here. By representing points as unit vectors on the sphere, the code avoids many of the singularities and special cases that plague latitude and longitude math. The result is less brittle geometry.
The library also spends real effort on speed. The implementation notes in s2cell.cc describe subdivision paths that are tuned to avoid unnecessary reconstruction, which is exactly the kind of detail that separates a good geometry system from a toy one.
How Queries Get Fast
Fast geometry is mostly about pruning. S2’s shape index and query APIs can rule out large regions before they do expensive edge tests. That is how the library supports spatial joins, nearest-edge queries, and containment checks at scale.
The pattern is familiar to database people. Use the index to get close, then do exact work on the narrowed candidate set. S2 makes that pattern natural for geography.
This is also why the Mapillary use case makes sense. Street-level imagery lives and dies by adjacency, neighborhood lookup, and spatial organization. S2 gives the product a way to treat camera captures like indexed entities instead of raw coordinates.
MapillaryJS needs a scalable way to index camera captures when determining adjacency. It uses discrete S2 geometry cells to solve that in the S2GeometryProvider.
S2 vs H3 vs Geohash
The comparison is not about declaring a universal winner. It is about choosing the right geometry model for the job. S2 is strongest when strict containment and spherical correctness matter most.
| System | Shape | Hierarchy | Containment | Distortion | Typical advantage |
|---|---|---|---|---|---|
| S2 | Squares on cube faces | Very strong | Exact parent-child nesting | Low on the sphere | Robust indexing and pruning |
| H3 | Hexagons | Strong but different | Less strict than S2 | Low, but with hex trade-offs | Flow, aggregation, smoothing |
| Geohash | Rectangles | Simple | Coarse and uneven | High near poles and edges | Quick implementation |
If you need a tidy string representation and can tolerate approximation, Geohash is fine. If you want hexagonal neighborhood behavior, H3 is compelling. If you want a spherical index that behaves like a serious containment system, S2 is the one that keeps showing up.
Why Mapillary Cares
A unique feature of the S2 library is that unlike traditional geographic information systems, which represent data as flat two-dimensional projections (similar to an atlas), the S2 library represents all data on a three-dimensional sphere (similar to a globe).
That globe-first model is exactly why Mapillary would care. A street-level imagery platform needs adjacency, containment, and fast neighborhood lookup across huge datasets. S2 gives it a durable spatial language for those operations.
So the library is not just an implementation detail. It is infrastructure for the product’s spatial brain. Without something like S2, the system would spend far more time compensating for the geometry of the Earth.