Hexagonal Grids (2013)

To condense it down to a few bullet points, we realized:

1. We needed to move from geofences to a grid for both data science reasons and scaling reasons to perform realtime aggregated and anonymized activity analysis for things like surge pricing.

2. With a grid along with quantized time ranges (eg 10 seconds or 1 minute intervals) we can reduce data collection to distributed increments across a small cluster of machines with O(1) compute time rather than a more complicated R-Tree (O(log(n)) + Point-in-Poly (O(m)) system for geofences (that also can't backfill prior results when new geofences are added)

3. With a grid, data science can be assured of approximately equal area and time across these space-time buckets so normalizing the data for analysis between them is not necessary, regardless of where on the planet it came from (cross-city analysis and forecasting). With a hexagon grid, data science can also be assured that all neighboring cells are the same distance from each other and that all neighboring cells share a measurable edge rather than an infinitesimal point (like squares) so flow analysis between the cells is similarly simplified and needs no normalizing.

4. With a hierarchical hexagon grid we can quantize the data at the finest granularity (which is higher resolution than commercial GPS, about the size of a coffee table in diameter) and it can be rapidly reaggregated upwards to other resolutions (with some small error introduced since hexagons do not properly tessellate) for data science to determine what the "right" resolution is for the analysis at hand, then the realtime aggregating system can be updated to index at that resolution natively, as well, to improve bucketing accuracy (H3 resolution 9 was one such blessed coarser resolution).

When we determined exactly what we needed, we didn't invent it to feel like we did something really cool, we reached out to Dr. Kevin Sahr in academia to help us make it, who used part of his DGGRID code to do so[1], and then spent nearly 2 years to make sure everything was legal for open sourcing.

What we did at Uber was focus on getting his core more easily consumable: Request that the core does not allocate memory on its own, but is passed in memory (so integration with memory-managed languages would be much simpler), implement many of the algorithms described by Red Blob Games to make manipulation of the data in the grid system more amenable, update the build and test system to a more modern standard (CMake, code coverage, and unit tests), and write C bindings in various languages.

[1](https://uber.github.io/h3/#/documentation/overview/use-cases) (references the paper that covers the work he did)

I do remember back in the late 70's and seeing D&D using hexagonal grids for outdoors, and the despair and pain of trying to find a damn pad of hexagonal paper (I think I had to mail order from The Armory or Chessex?!?). It was pretty funny that years later, one of the first PostScript programs I wrote generated hexagon sheets that could be printed on the college laser printers.

I'm an astrophysicist in high energy gamma ray astronomy.

Or telescope sensors have hexagonal pixels.

You website is awesome and helped a lot writing the coordinate trafos and other stuff. We always recommended it to everyone involved.

One switch I always wished it had was to switch to a cartesian coordinate system where x points right, y points up and negative coordinates are allowed.