The downsides are the characteristics that make h3 or s2 useful. For h3, the single neighbor type means it is well suited to flow analysis and S2 having exact cell subdivision means it is great for simplifying geometry.
However, there a number of use cases where choosing a spatial index is a more stylistic choice, like for visualization.
The aim of A5 is not to replace S2/H3 but rather to offer an alternative that has different strengths and weaknesses compared to existing solutions
Haha that colour scale on the area variance page makes it a bit hard to see whether nearby H3 hexagons are very different in size...? I've never really investigated, but my baseless assumption was that nearby hexagons (at a high zoom level) would be pretty similar size? But maybe that's completely wrong.
But yeah, will definitely reach for A5 at some point just for the aesthetics!
My favourite DGGS (this is a new term to me) is water basins as created by HydroSheds [1]. Different area, unpredictable shape, basically no usefull properties but they conform to topography! Can get a feel for them with this little thing I made several years ago [2] (your Cells example reminded me of this).
The description of the algorithm notes that each irregular pentagon is divided into four sub-pentagons. Eyeballing the maps, I don't see any group of 4 pentagons forming a similar larger pentagon.
I noticed that you had an analog to the H3 landing page on your landing page, allowing zooming in. If you could also steal the next-higher / next-smaller overlay like they did on the H3 landing page, it would make it clearer the relationship between the larger and smaller pentagons.
I've used H3 extensively, and one of the things that always bugged me about it was that each large hexagon was _mostly_ covered by a group of the next smaller ones, but because geometry, the edges have some overlap with the neighbor large hexagons. So I can't just truncate an integer mapping, for example, to get the ID of the next-largest.
The octahedron has a much higher angular defect (https://en.wikipedia.org/wiki/Angular_defect) than the dodecahedron, and thus when it is projected onto the sphere the cells are warped a lot. So while their areas may be the same, the shapes vary.
Not sure I understand—healpix starts from the rhombic dodecahedron and then bisects the generalizations of the 12 squares each time. Where do octahedra come into play?
A5 cell boundaries are geodesics. One more difference that I thought of is that HEALPix is generally not aligned with the continents (makes sense as it is mostly used for astrophysics), whereas the hilbert curve used to index A5 is aligned with the continental land masses: https://a5geo.org/examples/globe
As a result, when A5 is used as a spatial index, it will generally not have jumps in the cell index values when querying nearby locations on land
I once made a DGG without knowing that it was called a DGG so I could look up how to actually do it in the literature.
I ended up making it an icosahedron and recursively subdividing each face into four new ones by inscribing a new triangle. The project went nowhere for different reasons, so I never figured out if it would have worked, and given this isn’t one of the examples I suspect it wouldn’t have.
Google's S2 is all about performance and prefix-matching.
Uber's H3 makes the math a bit more complex to prioritize less variation in centerpoint-to-centerpoint distances (because they care most about driving times).
This makes the math even more complex to prioritize less variation in area covered by far away tiles (most applicable to e.g. analyzing density of something).
As a user, you generally don’t care about the math (and S2 is hardly simple either, as it warps the squares prior to projection). You just call the API and use the indices for spatial joins or computations.
The primary benefit is indeed the ability to treat cells as if they are equal areas. This is something people do currently with H3, but it introduces a bias. Contrary to popular belief, this is not only an issue near the poles or in the ocean.
The other difference is aesthetics, people generally find H3 more pleasing to look at than S2, which is why it gets used in visualization more. You can make the same argument for A5, although of course it is a matter of taste!
Finally, you are correct that H3 was originally developed at Uber for their specific use case, however it has since been used in many other contexts and I think it doesn’t hurt to have some alternatives as conceptually S2/H3/A5 are similar
Also check S2: http://s2geometry.io/, created at Google before H3, which uses squares and underpins the fast indexing in BigQuery amongst many other things
> The benefit of choosing a dodecahedron is that it is the platonic solid with the lowest vertex curvature, and by this measure it is the most spherical of all the platonic solids. This is key for minimizing cell distortion as the process of projecting a platonic solid onto a sphere involves warping the cell geometry to force the vertex curvature to approach zero. Thus, the lower the original vertex curvature, the less distortion will be introduced by the projection.
This feels like an uncommon need to optimize for. Can't think of a reason I would reach for this over S2 or H3
H3 and S2 are supported out of the box in ClickHouse and have reference libraries in C and C++. But it looks like A5 only has a reference implementation in TypeScript. Porting would not be a problem, though...
Bear in mind that this is a "Show HN", the library was released just a few weeks ago! Whereas the other libraries have been around for a decade+
The plan is certainly to release versions in other languages, if you would like to be involved, please get in touch. I agree the porting shouldn't be too difficult, as by design the library has just one simple dependency and the code should translate nicely to other C-style languages
Is it primarily useful just for data visualization? Would there be an potential performance benefits for something like searching a database for nearby data?
Thanks. I always enjoy when geospatial topics show up on here. My background it geo, but unfortunately I have slowly drifted away. Geohash is about where I left off in the same general realm of concepts, so S2 / H3 are essentially new to me as well.
Please please please include a description in your title. Just a couple of words will do.
It's obviously something about paper size A5.
On reading the comments it's about the healing powers of dodecahedrons.
github also mentions it has pentagonal shape..
+1...
Can you give some examples of when this might be better to use than H3?
The ones that seem obvious:
- You need very high resolution. H3 is also 64 bit I think, but it seems like A5 highest resolution is about 4 orders of magnitude higher.
- Equal cell size: are the cells exactly equal in size (in m2)? H3 they vary by up to ~2x.
What are the downsides? The shapes are irregular, distances between centroids are not uniform...
Yes, those are the obvious ones. This example: https://a5geo.org/examples/airbnb shows why the equal area is valuable in practice, while https://a5geo.org/examples/area shows the area variation vs h3.
The downsides are the characteristics that make h3 or s2 useful. For h3, the single neighbor type means it is well suited to flow analysis and S2 having exact cell subdivision means it is great for simplifying geometry.
However, there a number of use cases where choosing a spatial index is a more stylistic choice, like for visualization.
The aim of A5 is not to replace S2/H3 but rather to offer an alternative that has different strengths and weaknesses compared to existing solutions
Haha that colour scale on the area variance page makes it a bit hard to see whether nearby H3 hexagons are very different in size...? I've never really investigated, but my baseless assumption was that nearby hexagons (at a high zoom level) would be pretty similar size? But maybe that's completely wrong.
But yeah, will definitely reach for A5 at some point just for the aesthetics!
My favourite DGGS (this is a new term to me) is water basins as created by HydroSheds [1]. Different area, unpredictable shape, basically no usefull properties but they conform to topography! Can get a feel for them with this little thing I made several years ago [2] (your Cells example reminded me of this).
[1] https://www.hydrosheds.org/
[2] https://water.rdrn.me/
Very cool, thanks for the insight
The description of the algorithm notes that each irregular pentagon is divided into four sub-pentagons. Eyeballing the maps, I don't see any group of 4 pentagons forming a similar larger pentagon.
I noticed that you had an analog to the H3 landing page on your landing page, allowing zooming in. If you could also steal the next-higher / next-smaller overlay like they did on the H3 landing page, it would make it clearer the relationship between the larger and smaller pentagons.
I've used H3 extensively, and one of the things that always bugged me about it was that each large hexagon was _mostly_ covered by a group of the next smaller ones, but because geometry, the edges have some overlap with the neighbor large hexagons. So I can't just truncate an integer mapping, for example, to get the ID of the next-largest.
What's the advantage of this over HEALPix projection? https://en.wikipedia.org/wiki/HEALPix
The base platonic solid that Healpix is based on is the octahedron (https://en.wikipedia.org/wiki/Octahedron), which A5 uses the dodecahedron(https://en.wikipedia.org/wiki/Regular_dodecahedron).
The octahedron has a much higher angular defect (https://en.wikipedia.org/wiki/Angular_defect) than the dodecahedron, and thus when it is projected onto the sphere the cells are warped a lot. So while their areas may be the same, the shapes vary.
This article explains the geometric construction, and how it leads to the cells being a similar size and shape: https://a5geo.org/docs/technical/platonic-solids
Also from a data visualization point of view, the rectangular cells of Healpix (like S2) are arguably less pleasing to look at than hexagons/pentagons: https://h3geo.org/docs/comparisons/s2#visualization
Not sure I understand—healpix starts from the rhombic dodecahedron and then bisects the generalizations of the 12 squares each time. Where do octahedra come into play?
1 reply →
I'm not sure about A5, but I do know that HEALPix cell boundaries are not geodesics, whereas S2 cells are always bounded by four geodesics.
A5 cell boundaries are geodesics. One more difference that I thought of is that HEALPix is generally not aligned with the continents (makes sense as it is mostly used for astrophysics), whereas the hilbert curve used to index A5 is aligned with the continental land masses: https://a5geo.org/examples/globe
As a result, when A5 is used as a spatial index, it will generally not have jumps in the cell index values when querying nearby locations on land
I once made a DGG without knowing that it was called a DGG so I could look up how to actually do it in the literature.
I ended up making it an icosahedron and recursively subdividing each face into four new ones by inscribing a new triangle. The project went nowhere for different reasons, so I never figured out if it would have worked, and given this isn’t one of the examples I suspect it wouldn’t have.
So if I've understood correctly:
Google's S2 is all about performance and prefix-matching.
Uber's H3 makes the math a bit more complex to prioritize less variation in centerpoint-to-centerpoint distances (because they care most about driving times).
This makes the math even more complex to prioritize less variation in area covered by far away tiles (most applicable to e.g. analyzing density of something).
As a user, you generally don’t care about the math (and S2 is hardly simple either, as it warps the squares prior to projection). You just call the API and use the indices for spatial joins or computations.
The primary benefit is indeed the ability to treat cells as if they are equal areas. This is something people do currently with H3, but it introduces a bias. Contrary to popular belief, this is not only an issue near the poles or in the ocean.
The other difference is aesthetics, people generally find H3 more pleasing to look at than S2, which is why it gets used in visualization more. You can make the same argument for A5, although of course it is a matter of taste!
Finally, you are correct that H3 was originally developed at Uber for their specific use case, however it has since been used in many other contexts and I think it doesn’t hurt to have some alternatives as conceptually S2/H3/A5 are similar
For a visual explanation of how the system works, as well as interactive examples, check out the project website at https://a5geo.org/examples/
A5 uses pentagons, Uber's H3 uses hexagons:
H3: Uber’s Hexagonal Hierarchical Spatial Index https://www.uber.com/en-DE/blog/h3/
Also check S2: http://s2geometry.io/, created at Google before H3, which uses squares and underpins the fast indexing in BigQuery amongst many other things
> The benefit of choosing a dodecahedron is that it is the platonic solid with the lowest vertex curvature, and by this measure it is the most spherical of all the platonic solids. This is key for minimizing cell distortion as the process of projecting a platonic solid onto a sphere involves warping the cell geometry to force the vertex curvature to approach zero. Thus, the lower the original vertex curvature, the less distortion will be introduced by the projection.
This feels like an uncommon need to optimize for. Can't think of a reason I would reach for this over S2 or H3
If you're aggregating and comparing data across different locations for example: https://a5geo.org/examples/airbnb
H3 and S2 are supported out of the box in ClickHouse and have reference libraries in C and C++. But it looks like A5 only has a reference implementation in TypeScript. Porting would not be a problem, though...
Bear in mind that this is a "Show HN", the library was released just a few weeks ago! Whereas the other libraries have been around for a decade+
The plan is certainly to release versions in other languages, if you would like to be involved, please get in touch. I agree the porting shouldn't be too difficult, as by design the library has just one simple dependency and the code should translate nicely to other C-style languages
Is it primarily useful just for data visualization? Would there be an potential performance benefits for something like searching a database for nearby data?
Yes, such indices (S2 & H3) are widely used for providing a index in databases, so geospatial features that are close by in the world and stored in nearby databases rows. https://cloud.google.com/bigquery/docs/grid-systems-spatial-...
Thanks. I always enjoy when geospatial topics show up on here. My background it geo, but unfortunately I have slowly drifted away. Geohash is about where I left off in the same general realm of concepts, so S2 / H3 are essentially new to me as well.
[dead]