A5 v1.0: a global grid of pentagons with cells of identical area

When you work with geographic data at scale, sooner or later you end up using a global grid: splitting the planet into cells, each with a numeric identifier, and assigning every point, line or polygon to the cells it belongs to. From then on, combining two different datasets is as simple as a JOIN on the cell ID. The best known are H3, from Uber, with hexagons, and S2, from Google, with quadrilaterals.

Felix Palmer, a colleague at CARTO, has spent a year and a half working on an alternative with pentagons: A5. This week he released version 1.0, which freezes the grid definition and brings quite a few new features. It seemed like a good time to explain what it is and how it differs from the others.

What A5 is

A5 is what’s known as a DGGS (Discrete Global Grid System). It splits the world into pentagonal cells with 31 resolution levels, from a handful of cells covering the whole planet down to cells smaller than 30 mm². Each cell is identified by a 64-bit integer.

The geometric basis is curious: a tiling of irregular pentagons that together form a regular pentagon. Twelve copies of that tiling form a dodecahedron, which is then projected onto the sphere. The resulting polyhedron is called the Teohedron.

Its strong point is that every cell at a given resolution has exactly the same area. It sounds like a detail, but it isn’t.

Why equal-area cells matter

In H3, cells at the same resolution don’t all measure the same. The A5 documentation includes a very illustrative comparison: computing the density of holiday rentals in several cities around the world and ranking them.

With A5, counting rentals per cell is equivalent to counting rentals per km², because every cell is the same size. With H3 it isn’t: unless you normalise by each cell’s area, the ranking comes out wrong. In the example, Buenos Aires drops out of the ranking because its cells are smaller there (about 0.07 km²), and Hawaii and Rome swap places. They also point out that size variation in H3 doesn’t depend only on latitude, but shows up everywhere.

The fix with H3 is to always divide by each cell’s area, but it’s a step that’s easy to forget. With an equal-area grid, that mistake can’t happen.

On top of that, in v1.0 every cell has the same topology: pentagons with five neighbours. Hexagonal grids always need 12 pentagons scattered around the globe, because a sphere can’t be covered with hexagons alone, and those special cells complicate the algorithms.

What’s new in v1.0

Stable IDs

This is the most important change for production use: the grid and the cell IDs are frozen. An A5 ID stored in a database today will refer to the same place in the future.

The price is that IDs have changed compared to the 0.x versions. The shape and position of the cells are the same, but their numbering isn’t. There’s a migrate function to convert old IDs, although the simplest option is to reprocess the original data if you still have it.

A curve that never crosses itself

Most of the improvements come from a new space-filling curve, the teohedral curve, which defines the order in which cells are numbered. It runs across the whole planet without ever crossing itself, and groups cells so that they form an approximate spatial hierarchy.

Not crossing itself enables very efficient tricks. To fill a polygon with cells, the polygon’s boundary cuts the curve at a series of points, and everything between those cuts is inside. There’s no need to explore cell by cell: a polygon becomes a few ranges of IDs.

The benchmarks in the announcement, filling the outlines of several countries, are clear. Before v1.0, A5 became impractical above a million cells, just like H3 today. v1.0 reaches a billion cells, like S2, which is no coincidence either: S2 uses a Hilbert curve, which doesn’t cross itself.

Coverings with set operations

A covering is a set of cells representing a region, like a country, a land parcel or a radius around a point. v1.0 adds:

• Set operations: union, intersection and difference.
• Predicates: contains and overlaps.
• Measures: cell count and area.

Everything works on compacted data, that is, using large cells where possible instead of many small ones, without having to uncompact it first. That way billions of cells can be processed efficiently. A typical flow would be to union several coverings coming from database queries, intersect them with a polygon and filter a collection of points against the result.

Hierarchy

A pentagon can’t be split exactly into smaller pentagons (nor a hexagon into hexagons), so A5’s hierarchy is logical and only approximately spatial: a cell’s “children” don’t cover it exactly. For cases that need precision, like resampling data, v1.0 adds cellToSubcells, which returns a correct covering of the cell, and its inverse cellToSupercell.

Trying it with DuckDB

There are official libraries for TypeScript, Python and Rust, and integrations with DuckDB, PostgreSQL, R, QGIS and deck.gl. With the DuckDB community extension you can try it in a minute:

INSTALL a5 FROM community;
LOAD a5;

SELECT
    a5_lonlat_to_cell(-3.7038, 40.4168, 10) AS cell,
    a5_cell_area(10) AS area_m2;

At resolution 10, Madrid falls in a cell of about 32.4 km², and every cell at that resolution measures exactly the same, wherever it is. Aggregating points per cell is a good old GROUP BY:

SELECT
    a5_lonlat_to_cell(lon, lat, 10) AS cell,
    count(*) AS n
FROM points
GROUP BY cell
ORDER BY n DESC;

Watch out for examples floating around: IDs computed with versions before 1.0 don’t match the new ones.

A real example of what can be built is the FIRMS Explorer, which uses A5 to aggregate the 631 million fires detected by satellite worldwide since 2000.

A warning if you use deck.gl

The upgrade guide warns about a detail that can give you a nasty surprise. deck.gl 9’s A5Layer depends on a5-js 0.x, so if you add a5-js 1.0 to your app you end up with two copies, and the layer keeps using the old one. Result: cells with v1 IDs are drawn in the wrong place, without any error. Until deck.gl depends on v1, the fix is to force a single version with your package manager’s overrides:

{
  "overrides": {
    "a5-js": "1.0.0"
  }
}

My takeaway

I like seeing how a project that, as Felix himself says, started as a visualisation experiment (and an obsession with pentagons) has reached a stable version with an ecosystem behind it. Freezing the IDs is what it takes for someone to dare store them in a production database.

And the equal-area idea is one of those that, once you see it, you can’t unsee. When making a density map with H3 it’s very easy to assume all cells are the same size, and A5 removes that mistake at the root. Combined with a curve that makes it possible to work with billions of cells, it’s a very good option for spatial analysis with DuckDB or PostgreSQL. A5 is open source, under the Apache 2.0 licence, and the code is on GitHub.

Source: A5 v1.0, Felix Palmer.