Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

eng.uber.com

Post reply on HN
Print view View original

31–40 of 76 posts

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#31

Post by nwlieb »

jandrewrogers wrote: post #21
Mr_P wrote: post #3

I'd be curious to see a more thorough comparison to S2, which IMHO seems simpler (it's just quadtrees) and likely faster (it supports O(1) lookup vs. needing a hierarchical search).

It is complicated, and it depends on the use case. There are roughly three dimensions to what you are optimizing the representation for: presentation, computational geometry, and decomposition (sharding). S2 and H3 are both fundamentally cartography-driven representations, primarily optimizing for presentation. S2 focuses a bit more on sharding and H3 a bit more on computational geometry, there is quite a bit of lite…

What is an example of a 3-space embedding or interesting literature? I'm having difficulties googling the term.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#34

Post by jpab »

bayesian_horse wrote: post #33

I love the aesthetics of hexagons. It should be possible to turn this projection into quite a nice 3D printable model. Challenging, though. Probably one could try to split the sphere into equal hexagons for printing and then assemble.

You can't make a sphere entirely out of hexagons; the math doesn't work [1]. In the article they note that they include 12 pentagons too, to solve this problem. Neatly, they arrange to have all the pentagons in areas of water where they presumably won't have to analyse traffic patterns for a while.

(I mention it mostly because I think it's an interesting little mathematical factoid.)

[1] https://math.stackexchange.com/q/2121175

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#35

Post by jacobolus »

jpab wrote: post #34
bayesian_horse wrote: post #33

I love the aesthetics of hexagons. It should be possible to turn this projection into quite a nice 3D printable model. Challenging, though. Probably one could try to split the sphere into equal hexagons for printing and then assemble.

You can't make a sphere entirely out of hexagons; the math doesn't work [1]. In the article they note that they include 12 pentagons too, to solve this problem. Neatly, they arrange to have all the pentagons in areas of water where they presumably won't have to analyse traffic patterns for a while. (I mention it mostly because I think it's an interesting little mathematical factoid.) [1] https://math.stackexchange.co…

One thing you can do though is tile an octahedron by just hexagons. At each of the 6 corners you end up with 2 hexagons which border each-other along 2 edges (instead of the usual 1). If you blow this octahedron up into a sphere those hexagons appear to be pentagons, because two of their edges are colinear (i.e. the same great-circle arc).

This can be nicer in some cases: the edge case your hexagon-grid algorithms have to deal with is having a hexagon with one of the same neighbors twice, instead of needing to worry about pentagons per se.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#36

Post by jacobolus »

Animats wrote: post #32

There's a lot to be said for a hexagonal grid. I looked at this once for a collision detection system. It's convenient to get rid of the special cases needed where four cells meet. You have to invent some new bookkeeping, but it can be worth it.

The aliasing / moiré artifacts are also dramatically less objectionable with hexagonal grids.

Now that image sensors and e.g. smartphone displays are very high resolution, and most content ends up going through multiple resampling routines on its way from capture -> storage/processing -> display, I would love to see people start to experiment with hexagon-grid cameras and displays. The slightly more complicated resampling wouldn’t really be a big deal for modern DSP hardware, and the visual output could be significantly better for the same pixel count.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#37

Post by stefco_ »

kndjckt wrote: post #14
Mr_P wrote: post #3

I'd be curious to see a more thorough comparison to S2, which IMHO seems simpler (it's just quadtrees) and likely faster (it supports O(1) lookup vs. needing a hierarchical search).

The critical advantage of h3 vs. s2 is that all neighbors are equidistant from the central cell. Also, the implementation of the projection means there is less distortion than s2. I use this library every day and absolutely love it.

This is the same reason astronomers like HEALPix tiling for skymaps [0]. Equal areas-per-pixel (important for integrating over areas) with straightforward spherical harmonics calculations and hierarchical extensions that can store images at multiple resolutions by subdividing base cells (LIGO uses one such hierarchical strategy for our low-latency gravitational wave source direction estimates [1]).

[0] https://healpix.sourceforge.io

[1] https://arxiv.org/abs/1508.03634

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#38

Post by mtrovo »

jillesvangurp wrote: post #29

I did some indexing using elasticsearch and some home grown stuff based on geohashes about seven years ago. At the time Elasticsearch was just adding support for geoshape indexing as well. Initially this was also based on geohashes. Later they added proper quad tree support (instead of indexing the geohash as a term), and recently they revamped the implementation using BKD trees. The current implementation is way fas…

They go into some detail on this talk https://youtu.be/ay2uwtRO3QE?t=712.

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.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#39

Post by mtrovo »

thstart wrote: post #5

H3 is working for the specific Ubers’ needs. Not much useful as S2.

Could you give more details? After reading the article I think the main reason is the subdivision algorithm which for S2 is easier but for everything else hexagon seems like a better approach.

Re: H3: Uber’s Hexagonal Hierarchical Spatial Index (2018)

#40

Post by twic »

mtrovo wrote: post #38
jillesvangurp wrote: post #29

I did some indexing using elasticsearch and some home grown stuff based on geohashes about seven years ago. At the time Elasticsearch was just adding support for geoshape indexing as well. Initially this was also based on geohashes. Later they added proper quad tree support (instead of indexing the geohash as a term), and recently they revamped the implementation using BKD trees. The current implementation is way fas…

They go into some detail on this talk https://youtu.be/ay2uwtRO3QE?t=712 . 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 hexago…

> hexagon is a better shape for map grids because they are the most complex shape that can tesselate

[Penrose tiling intensifies]

Post reply on HN