H3: Uber’s Hexagonal Hierarchical Spatial Index(eng.uber.com)
eng.uber.com
H3: Uber’s Hexagonal Hierarchical Spatial Index
https://eng.uber.com/h3/
14 comments
That's the jist of it.
h3 cells have the benefit of no boundary conditions as all neighbor edges are the same shape and you can only cross boundaries. With s2, the problem is that four edges are long and then there are four vertices you can cross to get into the adjacent diamonds at each corner. The tradeoff is what you described, s2 cells nest perfectly at different resolutions, but h3 cells are only approximate.
They are both great tools useful in different circumstances. It you have to move between resolutions and don't care about movement between cells, s2 is a better choice. If you care only about one resolution for your work or care about movement/flow between neighboring cells, h3 is a better choice.
s2 I believe also goes down to a smaller resolution (like 1 cm or so) and h3 goes down to like 1 meter. That said, there aren't many use cases that need greater than 1-meter resolution.
h3 cells have the benefit of no boundary conditions as all neighbor edges are the same shape and you can only cross boundaries. With s2, the problem is that four edges are long and then there are four vertices you can cross to get into the adjacent diamonds at each corner. The tradeoff is what you described, s2 cells nest perfectly at different resolutions, but h3 cells are only approximate.
They are both great tools useful in different circumstances. It you have to move between resolutions and don't care about movement between cells, s2 is a better choice. If you care only about one resolution for your work or care about movement/flow between neighboring cells, h3 is a better choice.
s2 I believe also goes down to a smaller resolution (like 1 cm or so) and h3 goes down to like 1 meter. That said, there aren't many use cases that need greater than 1-meter resolution.
Why hexagons?
* Neighbor traversal
simplicity of neighbors; triangles 3 classes of neighbors, squares 2 classes of neighbors, hexagons only one class of neighbor!
* Subdivisions
Squares obviously do this pretty well but by alternating cw, cww rotations and allowing not quite perfect coverage they get to shard with different resolutions/hex sizes.
* Distortion
"most important" Basically the use case here is visualizations that maintain basic unit appearance. They even pick the location of their vertices to be over water minimizing land distortions.
source: https://youtu.be/ay2uwtRO3QE?t=11m53s
p.s. as `contravariant` said you can't tessellate a sphere with hexagons so they project onto a icosohedron with pentagons at each of the twelve vertices (positioned over water) https://youtu.be/ay2uwtRO3QE?t=23m00s
* Neighbor traversal
simplicity of neighbors; triangles 3 classes of neighbors, squares 2 classes of neighbors, hexagons only one class of neighbor!
* Subdivisions
Squares obviously do this pretty well but by alternating cw, cww rotations and allowing not quite perfect coverage they get to shard with different resolutions/hex sizes.
* Distortion
"most important" Basically the use case here is visualizations that maintain basic unit appearance. They even pick the location of their vertices to be over water minimizing land distortions.
source: https://youtu.be/ay2uwtRO3QE?t=11m53s
p.s. as `contravariant` said you can't tessellate a sphere with hexagons so they project onto a icosohedron with pentagons at each of the twelve vertices (positioned over water) https://youtu.be/ay2uwtRO3QE?t=23m00s
Very interesting. At a glance, the binding libs seem to transform from lat/lon to a hex index. For storage then, conceivably you would just index by hex and transform lat / loc queries to hex on the fly.
Also, it seems there is no map data attribution for Australia. I doubt Uber built their own maps.
Also, it seems there is no map data attribution for Australia. I doubt Uber built their own maps.
It says at the bottom that for this blog post, they used MapBox. That said, yes, Uber is building their own maps.
This is very interesting. The video does a good job at motivating it. I'm puzzled though that they include some demos on the page (I presume emscripten could compile it) as this figuratively begs for interactive demos.
Is there an equivalent index where the icosahedron vertices are over land and not sea (at least for the most part)? I presume for marine requirements, such an index would reduce distortion over sea?
I wonder how does the math of this stack up against using space-filling curves in Google's S2?
[deleted]
Well other than the fact that it's impossible to tesselate a sphere with hexagons it really depends what you're interested in. Space filling curves would necessarily behave badly in some areas, but could be simpler.
Not sure why they didn't use squares.
Not sure why they didn't use squares.
They go into it a bit in the article.
A lot of the reasons seem reminiscent of why hexagons are awesome in video games: https://www.redblobgames.com/grids/hexagons/
A lot of the reasons seem reminiscent of why hexagons are awesome in video games: https://www.redblobgames.com/grids/hexagons/
I'm a bit curious about this, I am a video game developer (3d console games) and hexagon coordinate systems don't strike me as being awesome. Reading through the article you linked to confirmed my suspicion that there would be a great many possible parameterizations, and it seems like the kind of thing that wound cause a lot of confusion amongst developers, much like Euler angles do. I had hoped that the article would start with some kind of motivation section describing why one would be willing to suffer such horrible inconveniences, but the article got too far into the not gritty before explaining the benefits (I stopped reading half way through so maybe it was buried in there somewhere?)
I know that they are associated with rpg board games and therefore have found their way in to 2D RPG video games as well. I can see a slight advantage to using them on a board game situation where it would make it more accurate to estimate diagonal distances by counting tiles, but in a computational situation where your box can compute the Pythagorean theorem a few million times a second, the benefit of using hex systems in games eludes me.
I know that they are associated with rpg board games and therefore have found their way in to 2D RPG video games as well. I can see a slight advantage to using them on a board game situation where it would make it more accurate to estimate diagonal distances by counting tiles, but in a computational situation where your box can compute the Pythagorean theorem a few million times a second, the benefit of using hex systems in games eludes me.
Nice. Thanks.
I'm very curious about H3's lat/long => hex cell system. I'll be studying their geoToH3 function soonest. https://uber.github.io/h3/#/documentation/api-reference/inde...
I'm very curious about H3's lat/long => hex cell system. I'll be studying their geoToH3 function soonest. https://uber.github.io/h3/#/documentation/api-reference/inde...
Papa bless uber!
I'm not an expert on this, but off the top of my head I can see a couple obvious tradeoffs. I'd love to hear some feedback from someone who's worked with H3 and S2 about the differences.
- S2 cells end up being sort of diamond shaped and all oriented in the same direction after being projected onto a sphere, so their radius varies a lot more than an H3 cell. I wouldn't be surprised if H3 cells are on average more useful for doing local data analysis, since they're closer to a circle. For example, a collection of events are probably clustered together more in an H3 cell than an equivalently sized S2 cell.
- S2 cells tile perfectly - each one is comprised of 4 smaller S2 cells. An H3 cell is approximated by 7 smaller H3 cells.
- Related to above, S2 cell addresses are in some sense "strict" - you can cut off the lowest significant bit to get the address of the parent S2 cell, which will fully contain the child cell. An H3 cell is not necessarily fully contained by its parent cell - judging by the pictures, the center cell is, but the 6 edge cells will overlap a bit. Probably the H3 cells are more annoying to work with for certain cases requiring exact numbers.
- As mentioned in the writeup, H3 needs to include a few pentagons in their tiling. They mention that they're oriented the grid so that the pentagons are over water, so it's probably not a big deal in day to day work.