H3: Hexagonal hierarchical geospatial indexing system
h3geo.org
h3geo.org
H3 doesn't guarantee a child hexagon at level N+1 strictly belongs to 1 parent at level N. S2 is built on this exactly this primitive, but then struggles with cell-size variability across latitude.
This lack of strict hierarchy seeming negates alot of practical benefits (e.g tree data-structure that maps well to sharding and aggregation). Whilst I haven't dug into H3 that much from a practical sense - but I have build several Geospatial systems with S2 that exploit this strict hierarchy - I can't imagine this isn't a huge pain-point with H3.
Would be interested to hear of how these approximate cases are handled at Uber or in any practical setting.
[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...
I'll use the approximate geometric containment mostly just to get a rough idea of where cells are. For example, in the plots of cells covering California in the link above, plotting the "compacted" cells is still visually useful, even if you aren't seeing the exact boundaries of the uncompacted set it represents.
How do you typically leverage exact geometric containment with S2 in your applications? I'm curious because I work on H3 and h3-py (https://uber.github.io/h3-py), and maybe there's something we can build (or it already exists) that would fit your use case.
It seems possible that a child hex might actually slip outside the boundary - since the 7 children don't fit squarely inside the parent (no pun intended).
In S2 it guaranteed that any child cell of the S2CellUnion representing that cover is strictly inside the polygon bounds.
This doesn't seem to be guaranteed in H3. I could have a location that is in Oregon, that depending on the child resolution could slip into to Oregon instead of California - or vice versa?
Now imagine an business application where a user must be mapped to one of 2 physically exclusive regions, (for say pricing, legal, compliance reasons) it seems like exact containment is preferred.
Perhaps there is another way to employ H3 that would mitigate this?
The big difference to me seems to be the shape of the cells: hexagonal for H3, square for S2.
H3 hexagonal is better for seeing more neighbouring cells.
S2 is better for being referenced with a numeric coordinate system, and uses a fractal space-filling curve to generate subdivisions.
https://s2geometry.io/devguide/s2cell_hierarchy
Fractals are super efficient (a binary tree is a fractal used for search) so I feel like I prefer S2 in this case. How are fractals being used in H3, and could other cell geometry be more efficient than the space-filling curve fractal used in S2?
As an example of where this is useful, it makes it very easy to get a list of all hexes with distance less than X from a current location.
Here's a comparison they give to some of the other common geographical partitions https://h3geo.org/docs/comparisons/s2
Brute force solution: iterate over all possible restaurants, compute their distance to your location, then return the list that meet the criteria.
Better solution: cut the world into 1-mile square grids, and assign each restaurant a grid square index. Search for all restaurants in your grid square, plus all adjacent grid squares to that (because you might be on the edge of your square), and filter out the ones that are more than 1 mile away. This is a pretty good solution, but you're searching a square area for a circle of restaurants. Any restaurants in the corners of the square are wasting your time -- you're never within 1 mile of the corner.
So, if you could search a circular area, you'd have no corners. Using tessellated hexagons means your search space is more circular, so it's more efficient.
It may work near a major avenue or political boundary or an event like a parade where there are "dispatch walls" set up or where there are two city areas that meet - think Reno / Tahoe.
s2geometry.io
In S2, the binary representations of a cell’s parents (larger cells that contain the cell) are always a prefix of the cell itself’a binary representation. This lets you perform constant time containment checks.
Which is better definitely will depend on your use case.
https://observablehq.com/@four43/h3-index-visualizer
https://imgur.com/a/SgDfJkG is an example
> Since it is not possible to tile the icosahedron with only hexagons, we chose to introduce twelve pentagons, one at each of the icosahedron vertices.
I wonder what happens if an artificial island and a major city pops up in one of those pentagons - presumably a fun tech debt to tackle :)
Sure enough, it is. It works well IIRC and there's a lot of interesting math surrounding it. Some of our internal tools we had access to at the time (now, presumably, under lock and key) had maps laid out in hexagons.
E: Some of the visualizers linked here seem a bit weird. I could be mis-remembering things, but the hexagons were WAY smaller than some of the visualizers here. I remember looking at the SF map and there was a lot of granularity even in the city center. Like I said though, could be mis-remembering.
The smallest granularity is . 0000009 km^2, so I guess 1/3 of an inch. Which seems to me a ridiculously and unnecessarily precise, but who knows
Unless we’re talking about different things, I’m not clear why we’re not assuming the tool you remember chose h10 or whatever level was actually useful to it, where the visualizations chose h5
(The average edge length is 0.5m, but that's not the same as the edge length of the average area hexagon)
But the way the hierarchical division system works, the tile boundaries from one scale don’t precisely match the tile boundaries from another scale.
More precisely, what you need to relax is the requirement that 3 hexagons always meet at every vertex. See https://en.wikipedia.org/wiki/Euler_characteristic#Polyhedra
If you have only hexagons, you end up with 6 vertices on the sphere where only 2 hexagons meet (whether you still consider these to be "hexagons" when they have two adjacent sides is a matter of definitions).
But what many spacial indices do instead is include 12 pentagons among the hexagons.
also check out the "gnomonic icosahedral" at H0 from the dropdowns, that's the projection the base hexagonal grid is from, it's a perfectly planar hexgrid on an unfolded icosahedron net.
When I was working in space science we experimented with using Hierarchical Triangular Meshes but we ended up not really needing the faster indexing it offered since most of our processing was done in small portions of the sky at a time anyways.
I’ve been wanting to implement something similar to this (albeit much lighter) for the use with indexeddb - it’s challenging since many of the capabilities here just aren’t available to JavaScript on the browser.
One of my projects is using the Dymaxion projection, which H3 uses, and I've found H3 to be a lot faster for my uses. YMMV.
As a practical matter, you want to fit the indexing structure to the properties of your data model as closely as possible. Increasing the generality of high-dimensionality spatial indexes comes at a high cognitive cost, so most complex high-dimensionality indexes are bespoke designs to limit generality. Things become pretty messy when you mix dimension types that are interval-like (e.g. polygons) and monotonic-like (e.g. temporal) so almost no one does it.
You can build, say, a general 8-dimensional index that can handle (some) distributions of interval and monotonic types simultaneously, in addition to the usual boring data types, that has excellent performance and scalability characteristics. It would probably only require something like 1000 lines of C++, so not too onerous. However, the code logic would be nearly impenetrable to read, never mind write, which matters for practical engineering.
Hexagons tile the plane very nicely, and are used for choosing where to place phone transmitters!
But they can't be easily divided into sub-hexagons.
Could we instead model them as the combination of Sierpinski triangles?
https://larryriddle.agnesscott.org/ifs/siertri/symmetricZ3he...