4 ms·

I used to work at Uber and worked on H3. They're working on a blog post to explain some more, but if you clone the repo and build the doxygen docs, you'll get m

I used to work at Uber and worked on H3. They're working on a blog post to explain some more, but if you clone the repo and build the doxygen docs, you'll get more explanation. The big difference between this and S2 is that hexagons have only one kind of neighbor, neighbors that border on an edge, instead of the two kinds of "checkerboard" neighbors that squares have. This lets you do some interesting analysis on data gathered with hexagons. Movement between neighbors could be modelled as a current flow, with the edge being a cross-sectional area between them, and since the edges are all equal (unlike squares) you can consider it a constant factor on that analysis, and then drop it and simply use the directional flow counts (the H3 UniEdge index) directly. H3 takes better care than S2 to keep both hexagon area and shape distortion to a minimum together (area distortion is about the same as S2, but shape distortion is much better than S2), so the hexagons look almost the same almost anywhere on the planet, and so data gathered in one city on the planet is directly comparable to data gathered in another city, which can let you do interesting things like classify "types" of hexagons (urban, suburban, etc) and then make predictions about cities you haven't even set up shop in, yet, based on similar cities. Hexagons are also the most efficient way to pack spheres, and can best approximate a circular radius with a discrete grid, so they're also useful for doing fast approximations of field-effect calculations (like electromagnetic fields from discrete particles). You could count drivers as a negative charge and riders as a positive charge, for instance, and use EM equations to determine the biggest imbalances in supply and demand distribution, and this will let you do it very quickly with little error. The hexagons themselves can get down to a granularity below GPS resolution error, so you could, without any effective losses, pack 3 doubles (lat, lng, error) into a single 64-bit integer (H3 index of an appropriate size based on the error) and reduce bandwidth usage on location data. The H3 index for any particular resolution is ordered in something similar to a Gosper curve[1] so if you really need just a rough approximation of data to query from an area, you actually only need to store the two indexes at the beginning and end of the gosper-like curve you're interested in. This C library wasn't meant to be used directly by most developers and that's why it has a few rough edges (like not centering the output around the meridian (-180, 180) instead of the current (0, 360) output). I can't wait until the bindings come out, too, probably with the blog post. :) [1]: https://en.wikipedia.org/wiki/Gosper_curve https://en.wikipedia.org/wiki/Gosper_curve

jacobolus 9y ago
If you want to do “field-effect calculations” or care about preservation of shapes you probably want a conformal grid. If you want to trade off area vs. shape distortion, it’s probably better to pick a projection which tries to optimize distance errors. Using a gnomonic projection for each icosahedron triangle is probably not the best choice for pretty much any application, though it has the advantage of being less work to implement. There are lots of reasonable choices for high-level grid shapes, e.g. http://www.lib.ncep.noaa.gov/ncepofficenotes/files/on467.pdf http://www.lib.ncep.noaa.gov/ncepofficenotes/files/on467.pdf For human comprehensibility of coordinates I would recommend instead starting with an octahedron as the basic geometric skeleton.
amckenna 9y ago
This was a very helpful explanation, thank you! Does using hexagons represent the start of a paradigm shift for mapping applications or is it something that has been used for a while? This is the first I have heard of it, but based on your explanation it makes a lot of sense.
- jacobolus 9y ago
  Hexagonal pixel grids have been used for decades by many different people for various GIS/mapping applications. If you do a google scholar search you will find hundreds of relevant papers. They’re still uncommon compared to square grids, because they are less convenient in several ways, and less familiar – every part of our culture (textiles, architecture and construction, mechanical engineering, urban planning, writing and books, furniture, visual art, toys, cartography, circuit boards, computer displays, abstract mathematics, ...) is deeply rooted in rectangular grids. Like most tools/conventions, there are trade-offs involved.
- ISV_Damocles 9y ago
  There have been many uses of hex grids and maps for a while, such as Civilization V, and this awesome hex grid resource from a gaming company: https://www.redblobgames.com/grids/hexagons/ https://www.redblobgames.com/grids/hexagons/ Others have pointed out various indexing systems that NASA uses that support hexagons, as well. H3's advantages over the others is, in my opinion, that we tried to marry as much of the awesome S2 library into a hexagonal grid (short 64-bit addresses for all hexagons at all resolutions, a parent-child tree with no shared parents, minimized area distortion, and a pretty simple API with some built-in utilities, like geofence polyfill, hexagon compaction, GeoJSON output, etc), where the hexagonal properties give you the other advantages I outlined over S2. To be perfectly fair, there are some things that S2 will still do better than H3, most notably that the area coverage of a parent perfectly matches all of its children, where that's not the case with H3, though we minimized it as well as I think is possible. Kevin Sahr (whom others have cited in here) worked with us on this library and came up with the parent-child orientation and scaling, and implemented the original version of the code.

jacobolus 9y ago

If you want to do “field-effect calculations” or care about preservation of shapes you probably want a conformal grid. If you want to trade off area vs. shape distortion, it’s probably better to pick a projection which tries to optimize distance errors. Using a gnomonic projection for each icosahedron triangle is probably not the best choice for pretty much any application, though it has the advantage of being less work to implement. There are lots of reasonable choices for high-level grid shapes, e.g. http://www.lib.ncep.noaa.gov/ncepofficenotes/files/on467.pdf http://www.lib.ncep.noaa.gov/ncepofficenotes/files/on467.pdf For human comprehensibility of coordinates I would recommend instead starting with an octahedron as the basic geometric skeleton.

amckenna 9y ago

This was a very helpful explanation, thank you! Does using hexagons represent the start of a paradigm shift for mapping applications or is it something that has been used for a while? This is the first I have heard of it, but based on your explanation it makes a lot of sense.

jacobolus 9y ago
Hexagonal pixel grids have been used for decades by many different people for various GIS/mapping applications. If you do a google scholar search you will find hundreds of relevant papers. They’re still uncommon compared to square grids, because they are less convenient in several ways, and less familiar – every part of our culture (textiles, architecture and construction, mechanical engineering, urban planning, writing and books, furniture, visual art, toys, cartography, circuit boards, computer displays, abstract mathematics, ...) is deeply rooted in rectangular grids. Like most tools/conventions, there are trade-offs involved.
ISV_Damocles 9y ago
There have been many uses of hex grids and maps for a while, such as Civilization V, and this awesome hex grid resource from a gaming company: https://www.redblobgames.com/grids/hexagons/ https://www.redblobgames.com/grids/hexagons/ Others have pointed out various indexing systems that NASA uses that support hexagons, as well. H3's advantages over the others is, in my opinion, that we tried to marry as much of the awesome S2 library into a hexagonal grid (short 64-bit addresses for all hexagons at all resolutions, a parent-child tree with no shared parents, minimized area distortion, and a pretty simple API with some built-in utilities, like geofence polyfill, hexagon compaction, GeoJSON output, etc), where the hexagonal properties give you the other advantages I outlined over S2. To be perfectly fair, there are some things that S2 will still do better than H3, most notably that the area coverage of a parent perfectly matches all of its children, where that's not the case with H3, though we minimized it as well as I think is possible. Kevin Sahr (whom others have cited in here) worked with us on this library and came up with the parent-child orientation and scaling, and implemented the original version of the code.