A5 v1.0: una rejilla global de pentágonos con celdas de área idéntica

Cuando trabajas con datos geográficos a gran escala, tarde o temprano acabas usando una rejilla global: dividir el planeta en celdas, cada una con un identificador numérico, y asignar cada punto, línea o polígono a las celdas que le corresponden. A partir de ahí, cruzar dos conjuntos de datos distintos es tan sencillo como hacer un JOIN por el identificador de celda. Las más conocidas son H3, de Uber, con hexágonos, y S2, de Google, con cuadriláteros.

Felix Palmer, compañero en CARTO, lleva año y medio trabajando en una alternativa con pentágonos: A5. Esta semana ha publicado la versión 1.0, que congela la definición de la rejilla y trae bastantes novedades. Me ha parecido un buen momento para contar qué es y en qué se diferencia de las demás.

Qué es A5

A5 es lo que se conoce como un DGGS (Discrete Global Grid System). Divide el mundo en celdas pentagonales con 31 niveles de resolución, desde unas pocas celdas que cubren todo el planeta hasta celdas de menos de 30 mm². Cada celda se identifica con un entero de 64 bits.

La base geométrica es curiosa: un mosaico de pentágonos irregulares que juntos forman un pentágono regular. Doce copias de ese mosaico forman un dodecaedro, que luego se proyecta sobre la esfera. Al poliedro resultante lo llaman Teohedron.

Su punto fuerte es que todas las celdas de una misma resolución tienen exactamente la misma área. Parece un detalle, pero no lo es.

Por qué importa que las celdas tengan la misma área

En H3, las celdas de una misma resolución no miden lo mismo. La documentación de A5 incluye una comparación muy ilustrativa: calcular la densidad de alojamientos turísticos en varias ciudades del mundo y ordenarlas.

Con A5, contar alojamientos por celda equivale a contar alojamientos por km², porque todas las celdas miden lo mismo. Con H3 no: si no se normaliza por el área de cada celda, el ranking sale mal. En el ejemplo, Buenos Aires desaparece de la clasificación porque allí las celdas son más pequeñas (unos 0,07 km²), y Hawái y Roma se intercambian el puesto. Y aclaran que la variación de tamaño en H3 no depende sólo de la latitud, sino que aparece en todas partes.

La solución con H3 es dividir siempre por el área de cada celda, pero es un paso que se olvida con facilidad. Con una rejilla de área igual, ese error no se puede cometer.

Además, en la v1.0 todas las celdas tienen la misma topología: pentágonos con cinco vecinos. Las rejillas hexagonales necesitan siempre 12 pentágonos repartidos por el globo, porque una esfera no se puede cubrir sólo con hexágonos, y esas celdas especiales complican los algoritmos.

Lo nuevo en la v1.0

Identificadores estables

Es el cambio más importante para usarlo en producción: la rejilla y los identificadores de celda quedan congelados. Un identificador A5 guardado hoy en una base de datos se referirá al mismo sitio en el futuro.

El precio es que los identificadores han cambiado respecto a las versiones 0.x. La forma y la posición de las celdas son las mismas, pero su numeración no. Hay una función migrate para convertir los identificadores antiguos, aunque lo más sencillo es volver a procesar los datos originales si se tienen.

Una curva que no se cruza

La mayoría de las mejoras vienen de una nueva curva de relleno del espacio, la curva teoédrica, que define el orden en que se numeran las celdas. Recorre el planeta entero sin cruzarse nunca consigo misma y agrupa las celdas de forma que forman una jerarquía espacial aproximada.

Que no se cruce permite trucos muy eficientes. Para rellenar un polígono con celdas, el borde del polígono corta la curva en una serie de puntos, y todo lo que queda entre esos cortes está dentro. No hace falta ir explorando celda a celda: un polígono se convierte en unos pocos rangos de identificadores.

Las pruebas de rendimiento del anuncio, rellenando los contornos de varios países, son claras. Antes de la v1.0, A5 se volvía impracticable por encima del millón de celdas, igual que H3 hoy. La v1.0 llega a mil millones de celdas, igual que S2, que tampoco es casualidad: S2 usa una curva de Hilbert, que tampoco se cruza.

Coberturas con operaciones de conjuntos

Una cobertura es un conjunto de celdas que representa una región, como un país, una parcela o un radio alrededor de un punto. La v1.0 añade:

• Operaciones de conjuntos: unión, intersección y diferencia.
• Predicados: contains y overlaps.
• Medidas: número de celdas y área.

Todo funciona sobre datos compactados, es decir, usando celdas grandes donde se puede en lugar de muchas pequeñas, sin tener que descompactarlos antes. Así se pueden procesar miles de millones de celdas de forma eficiente. Un flujo típico sería unir varias coberturas que salen de consultas a la base de datos, intersecarlas con un polígono y filtrar una colección de puntos contra el resultado.

Jerarquía

Un pentágono no se puede dividir exactamente en pentágonos más pequeños (un hexágono tampoco en hexágonos), así que la jerarquía de A5 es lógica y sólo aproximadamente espacial: los “hijos” de una celda no la cubren de forma exacta. Para los casos en que hace falta precisión, como remuestrear datos, la v1.0 añade cellToSubcells, que devuelve una cobertura correcta de la celda, y su inversa cellToSupercell.

Probarlo con DuckDB

Hay bibliotecas oficiales para TypeScript, Python y Rust, e integraciones con DuckDB, PostgreSQL, R, QGIS y deck.gl. Con la extensión comunitaria de DuckDB se puede probar en un minuto:

INSTALL a5 FROM community;
LOAD a5;

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

A resolución 10, Madrid cae en una celda de unos 32,4 km², y todas las celdas de esa resolución miden exactamente lo mismo, estén donde estén. Agregar puntos por celda es un GROUP BY de toda la vida:

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

Ojo con los ejemplos que circulan por ahí: los identificadores calculados con versiones anteriores a la 1.0 no coinciden con los nuevos.

Un ejemplo real de lo que se puede construir es el FIRMS Explorer, que agrega con A5 los 631 millones de incendios detectados por satélite en todo el mundo desde el año 2000.

Un aviso si usas deck.gl

La guía de migración avisa de un detalle que puede dar un buen susto. La capa A5Layer de deck.gl 9 depende de a5-js 0.x, así que si añades a5-js 1.0 a tu aplicación acabas con dos copias, y la capa sigue usando la antigua. Resultado: las celdas con identificadores v1 se dibujan en el sitio equivocado, sin ningún error. Hasta que deck.gl dependa de la v1, la solución es forzar una sola versión con los overrides del gestor de paquetes:

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

Lo que me llevo

Me gusta ver cómo un proyecto que, según cuenta el propio Felix, empezó como un experimento de visualización (y una obsesión por los pentágonos) ha llegado a una versión estable con un ecosistema detrás. Congelar los identificadores es lo que hace falta para que alguien se atreva a guardarlos en una base de datos de producción.

Y la idea del área igual me parece de las que, una vez la ves, no puedes dejar de verla. Al hacer un mapa de densidad con H3 es muy fácil dar por hecho que todas las celdas miden lo mismo, y A5 elimina ese error de raíz. Sumado a una curva que permite operar con miles de millones de celdas, es una opción muy a tener en cuenta para análisis espacial con DuckDB o PostgreSQL. A5 es open source, con licencia Apache 2.0, y el código está en GitHub.

Fuente: A5 v1.0, Felix Palmer.