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

41–50 of 76 posts

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

#41

Post by na85 »

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…

That link is a great example of why I stopped using stack exchange. The OP asked a question about tiling spheres with pentagons and the third response is basically "you can tile a sphere if it's not a sphere."

I had analogous experiences every time I asked a question there. One would ask a very clear question like, say, "how do I print to stdout in C?" And the first or second answer you get is inevitably about taking input from stdin. Or polymorphism.

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

#42

Post by scottlocklin »

nwlieb wrote: post #31
jandrewrogers wrote: post #21

Earlier quoted context omitted.

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.

I'm guessing he means stuff like voronoi tesselation, which isn't limited to 3-space. Look at the books of Hanan Samet for more on this stuff: http://www.cs.umd.edu/~hjs/

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

#43

Post by HelloNurse »

mtrovo wrote: post #39
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.

Subdividing tiles can be more important than everything else: knowing in which tile a point lies is a fundamental operation for a spatial indexing system and it has to be very easy and efficient.

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

#44

Post by ant6n »

na85 wrote: post #41
jpab wrote: post #34

Earlier quoted context omitted.

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…

That link is a great example of why I stopped using stack exchange. The OP asked a question about tiling spheres with pentagons and the third response is basically "you can tile a sphere if it's not a sphere." I had analogous experiences every time I asked a question there. One would ask a very clear question like, say, "how do I print to stdout in C?" And the first or second answer you get is inevitably about taking…

Maybe people just like to hijack threads and change the topic to what they like to talk about.

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

#45

Post by lvh »

seanhandley wrote: post #22

I work for a delivery company. We currently use H3 to help calculate ETAs in realtime.

Does that work? I’d expect you want to do a fairly traditional road-based ETA? Otherwise you’ll be wildly off if you’re in a cul de sac next to a major highway or on said highway, or in massive traffic vs not at all.

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

#46

Post by twic »

HelloNurse wrote: post #43
mtrovo wrote: post #39

Earlier quoted context omitted.

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.

Subdividing tiles can be more important than everything else: knowing in which tile a point lies is a fundamental operation for a spatial indexing system and it has to be very easy and efficient.

It's also vital for correct aggregation: if you sum up some quantity over all the subdivisions of some area, you really want that sum to be equal to the quantity in that area. With this hexagonal pseudo-subdivision, it isn't.

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

#47

Post by phkahler »

seanhandley wrote: post #26
hamandcheese wrote: post #6

How does this compare to S2 from google? It is not mentioned in the post at all. http://s2geometry.io/

You get more aesthetic visuals from H3. S2 cells distort quite heavily depending on which part of the globe you're mapping.

I think this is the real answer. I've like hex tiles for a long time, but they don't nest properly like squares in a quadtree. I think someone at Uber decided to "make it work" because it looks cool. They traded one set of problems for another, and I think from a technical point of view they made a poor choice.

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

#48

Post by seanhandley »

lvh wrote: post #45
seanhandley wrote: post #22

I work for a delivery company. We currently use H3 to help calculate ETAs in realtime.

Does that work? I’d expect you want to do a fairly traditional road-based ETA? Otherwise you’ll be wildly off if you’re in a cul de sac next to a major highway or on said highway, or in massive traffic vs not at all.

It's more to figure out how many couriers are in a given cell at a given time, and track that data over time so it can be forecasted.

Then we can say if you need a package collecting at address X, there are usually Y available couriers within Z distance. Combine that with a road mapping/traffic API and you're done.

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

#49

Post by CositaS »

twic wrote: post #40
mtrovo wrote: post #38

Earlier quoted context omitted.

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]

I think it's clear what they meant was not actually 'the most complex shape' but the regular polygon with the most sides that can tessellate.
Post reply on HN