Hacker News Reader

Comment by samirahmed | Hacker News Reader

S2 is used pretty heavily across the industry. Comparison - (https://h3geo.org/docs/comparisons/s2/)

H3 doesn't guarantee a child hexagon at level N+1 strictly belongs to 1 parent at level N. S2 is built on this exactly this primitive, but then struggles with cell-size variability across latitude.

This lack of strict hierarchy seeming negates alot of practical benefits (e.g tree data-structure that maps well to sharding and aggregation). Whilst I haven't dug into H3 that much from a practical sense - but I have build several Geospatial systems with S2 that exploit this strict hierarchy - I can't imagine this isn't a huge pain-point with H3.

Would be interested to hear of how these approximate cases are handled at Uber or in any practical setting.

View on HN

I typically only rely on the logical parent/child relationship between cells, and containment there is strict even if geometric containment is only approximate. The logical relationship is useful, for example, in providing a compact representation when you have a large collection of cells: https://h3geo.org/docs/highlights/indexing

I'll use the approximate geometric containment mostly just to get a rough idea of where cells are. For example, in the plots of cells covering California in the link above, plotting the "compacted" cells is still visually useful, even if you aren't seeing the exact boundaries of the uncompacted set it represents.

How do you typically leverage exact geometric containment with S2 in your applications? I'm curious because I work on H3 and h3-py (https://uber.github.io/h3-py), and maybe there's something we can build (or it already exists) that would fit your use case.

One example I am trying to wrap my head around is if you have two adjacent polygons (say California and Oregon) and perform an interior cover of both with variable hex sizes.

It seems possible that a child hex might actually slip outside the boundary - since the 7 children don't fit squarely inside the parent (no pun intended).

In S2 it guaranteed that any child cell of the S2CellUnion representing that cover is strictly inside the polygon bounds.

This doesn't seem to be guaranteed in H3. I could have a location that is in Oregon, that depending on the child resolution could slip into to Oregon instead of California - or vice versa?

Now imagine an business application where a user must be mapped to one of 2 physically exclusive regions, (for say pricing, legal, compliance reasons) it seems like exact containment is preferred.

Perhaps there is another way to employ H3 that would mitigate this?

There is also Hierarchical Triangular Mesh [1] which also forms a proper quad tree but I am not sure how the cell variability compares to S2.

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...

I tried to use this a few years ago but found the tooling inadequate for my use case. It wasn’t supported well enough across the various libraries involved in ingestion, storage and web client rendering. I’d love to hear from anyone using Hierarchical Triangular Mesh in the wild to learn more about how they made it work.

Thank you for linking the comparison to S2!

The big difference to me seems to be the shape of the cells: hexagonal for H3, square for S2.

H3 hexagonal is better for seeing more neighbouring cells.

S2 is better for being referenced with a numeric coordinate system, and uses a fractal space-filling curve to generate subdivisions.

https://s2geometry.io/devguide/s2cell_hierarchy

Fractals are super efficient (a binary tree is a fractal used for search) so I feel like I prefer S2 in this case. How are fractals being used in H3, and could other cell geometry be more efficient than the space-filling curve fractal used in S2?

I remember searching for S2 (+”geofencing”, “map”) and not being able to find it. What search terms would have helped?

Reply on news.ycombinator.com