Uber Engineering
1 HN recommender · recommended in 3 months, 2018–2025
25:39 · 53K views · Jan 22, 2018
Uber Engineering's Joseph Gilley explains why Uber uses hexagons for geospatial indexing and introduces H3, its open source hierarchical grid system. He covers use cases and how distortion is handled.
HN points to it as the detailed explanation of why hexagons suit map grids, in threads about H3.
3 comments from Hacker News
They go into some detail on this talk this video . What I get from their explanation is that hexagon is a better shape for map grids because they are the most complex shape that can tesselate (the other two are triangles and squares). As they are more close to a circle, distances within a cell are more stable, also computing the distance from a cell center to its neighbours is stable in hexagons as well. I think the reason hex is not more common is that subdivisions are hard to create compared to triangles or squares. Uber solved this by subdividing in 7 smaller hex and tilting it so they cover the bigger shape with some small overlap. Also a big problem is distortion, I never thought this would be that huge of a problem but it makes sense. They go into a lot of the details later on the same video.
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: this video 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) this video
Key reasons for the choice of hexagons in h3 - hexagons have have low distortion as compared to squares when you attempt tessellation of a spherical shape. You just require 12 pentagons to complete this tessellation. - all six neighboring cells are equidistant from the center of a cell. One of the use case Uber was trying to solve here, was to show which regions had surge pricing - on the uber app for the drivers. With h3 and hexagons you can argue it looks a teensy bit better with smoother gradients [LINK] . I am not sure whether Uber uses h3 for other use cases like - finding the closest drivers next to a location. See this presentation from Uber on this: this video