[HN Gopher] H3: Hexagonal hierarchical geospatial indexing system
___________________________________________________________________
H3: Hexagonal hierarchical geospatial indexing system
Author : jonbaer
Score : 92 points
Date : 2021-09-15 15:31 UTC (7 hours ago)
(HTM) web link (h3geo.org)
(TXT) w3m dump (h3geo.org)
| throwoutway wrote:
| Is there a UI or image of what the hexagons look like on the
| planet?
| mxfh wrote:
| https://observablehq.com/@fil/h3-oddities
|
| also check out the "gnomonic icosahedral" at H0 from the
| dropdowns, that's the projection the base hexagonal grid is
| from, it's a perfectly planar hexgrid on an unfolded
| icosahedron net.
| david_draco wrote:
| Yes, in the sections under Intro > Comparisons
| prpl wrote:
| There's gifs of hexagons on a planet you can search but you
| can't cover a sphere with just hexagons. Even so, I imagine the
| poles are irrelevant to Uber
| xvedejas wrote:
| The image shows a number of pentagons, so it's not just
| hexagons unless you consider a pentagon some kind of
| degenerate hexagon. That said, you can indeed cover a sphere
| with only hexagons, if you relax the requirement that they
| all be regular hexagons.
| jayd16 wrote:
| Looks like H3 uses regular hexagons and instead drops the
| requirement that they can't overlap.
| jacobolus wrote:
| At each tiling level, they have a proper tiling of
| hexagons with 12 pentagons. The system is based on an
| icosahedron.
|
| But the way the hierarchical division system works, the
| tile boundaries from one scale don't precisely match the
| tile boundaries from another scale.
| ClumsyPilot wrote:
| That can be a deal breaker for some uses
| jacobolus wrote:
| > _you can indeed cover a sphere with only hexagons, if you
| relax the requirement that they all be regular hexagons_
|
| More precisely, what you need to relax is the requirement
| that 3 hexagons always meet at every vertex. See https://en
| .wikipedia.org/wiki/Euler_characteristic#Polyhedra
|
| If you have only hexagons, you end up with 6 vertices on
| the sphere where only 2 hexagons meet (whether you still
| consider these to be "hexagons" when they have two adjacent
| sides is a matter of definitions).
|
| But what many spacial indices do instead is include 12
| pentagons among the hexagons.
| fredley wrote:
| This has a nice visualiser:
| https://observablehq.com/@four43/h3-index-visualizer
| saalweachter wrote:
| The blog post has a picture showing several layers of hexagons
| overlapping.
| adolgert wrote:
| Dumb question: I've put points on a sphere using a Fibonacci
| series, then relaxed them and triangulated them, and there are
| some 5's and 7's, not all hexagons. I thought an all-hexagon
| tiling wasn't possible. How do they do it?
| bloopernova wrote:
| They distort the hexagons as you go further north.
|
| https://observablehq.com/@four43/h3-index-visualizer
|
| https://imgur.com/a/SgDfJkG is an example
| ritwikgupta wrote:
| The warping you're observing is a result of the projection
| used to display the map on a 2D screen. They actually do use
| pentagons to solve the tessellation issue.
| robinhouston wrote:
| There's a 2018 blog post from Uber Engineering[0] which has
| more technical details about the system, and explains:
|
| > Since it is not possible to tile the icosahedron with only
| hexagons, we chose to introduce twelve pentagons, one at each
| of the icosahedron vertices.
|
| 0. https://eng.uber.com/h3/
| ravar wrote:
| There are 12 pentagons conveniently placed over water. The docs
| are a pretty interesting read. https://eng.uber.com/h3/
| progbits wrote:
| That is a clever solution! For a transportation company at
| least.
|
| I wonder what happens if an artificial island and a major
| city pops up in one of those pentagons - presumably a fun
| tech debt to tackle :)
| ku-man wrote:
| "H3 is a geospatial indexing system that partitions the world
| into hexagonal cells."
|
| So, which world? or more specifically which ellipsoid? or is that
| the hexagons map over the geoid? (in turn, which geoid?)
| X6S1x6Okd1st wrote:
| Blog post here: https://eng.uber.com/h3/
| captare wrote:
| I've used the excellent DGGRID for building geo-hex grids:
| https://github.com/sahrk/DGGRID
| JakeStone wrote:
| DGGRID was very useful for me when I first started
| experimenting with hexagon partitioning.
|
| One of my projects is using the Dymaxion projection, which H3
| uses, and I've found H3 to be a lot faster for my uses. YMMV.
| kevmoo1 wrote:
| Worth reminding folks:
| https://www.youtube.com/watch?v=thOifuHs6eY
| samirahmed wrote:
| 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.
| danbruc wrote:
| 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/...
| ajfriend wrote:
| 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.
| Tarrosion wrote:
| I wrote a blog post exploring the tradeoffs different geo grid
| systems make, including H3. The post describes a proof of concept
| exploring a different part of design-tradeoff space.
|
| https://evanfields.github.io/No-Perfect-Geo-Grid/
| [deleted]
| eerikkivistik wrote:
| Does anyone happen to know of any geospatial indexing solutions
| that can also index simultaneously by other dimensions. Temporal
| indexing for example (not only where, but when)?
| jandrewrogers wrote:
| Yes, with caveats and reasons you don't often see it.
|
| As a practical matter, you want to fit the indexing structure
| to the properties of your data model as closely as possible.
| Increasing the generality of high-dimensionality spatial
| indexes comes at a high _cognitive_ cost, so most complex high-
| dimensionality indexes are bespoke designs to limit generality.
| Things become pretty messy when you mix dimension types that
| are interval-like (e.g. polygons) and monotonic-like (e.g.
| temporal) so almost no one does it.
|
| You can build, say, a general 8-dimensional index that can
| handle (some) distributions of interval _and_ monotonic types
| simultaneously, in addition to the usual boring data types,
| that has excellent performance and scalability characteristics.
| It would probably only require something like 1000 lines of
| C++, so not too onerous. However, the code logic would be
| nearly impenetrable to read, never mind write, which matters
| for practical engineering.
| eerikkivistik wrote:
| Thank you for the thorough answer.
| geophile wrote:
| Z-order does this easily, just index on (x, y, t). I wouldn't
| recommend it for more than maybe 4-6 dimensions though.
| rurabe wrote:
| H3 cell indexes are just integers so you can easily make a
| compound index of (cell_index,timestamp). This would be easy in
| SQL and I'd have to imagine just about anything else that
| supports a compound index.
| endisneigh wrote:
| Somewhat related - how would you setup geospatial indexing using
| a traditional index? For example IndexedDB?
|
| I've been wanting to implement something similar to this (albeit
| much lighter) for the use with indexeddb - it's challenging since
| many of the capabilities here just aren't available to JavaScript
| on the browser.
| nrabinowitz wrote:
| Everything in H3 is available in the browser:
| https://github.com/uber/h3-js
| endisneigh wrote:
| Thanks for the link - I'll have to check that out. I wonder
| if the limitations in IndexedDB will make certain queries
| impossible
| fredley wrote:
| Fun fact: Uber surge pricing is calculated per-hexagon (h9, I
| think). If you're near a hexagon boundary experiencing surge, hop
| across to another one and check again.
| RicoElectrico wrote:
| This sounds similar to the S2 cell shenanigans people do in
| Pokemon GO and Ingress. ;)
| krebby wrote:
| Unfortunately this isn't strictly true anymore (and hasn't been
| for a few years). All areas of surge have a quadratic fall-off
| zone around the high point to solve just this. You'd have to
| walk some distance for this to be helpful.
|
| It may work near a major avenue or political boundary or an
| event like a parade where there are "dispatch walls" set up or
| where there are two city areas that meet - think Reno / Tahoe.
| fredley wrote:
| Yes, while you don't get such extreme drops, surge can drop
| from 1.6x to 1.4x by crossing the street if you're in the
| right place, which can save quite a bit on a longer journey.
| codezero wrote:
| All the shapes!
|
| When I was working in space science we experimented with using
| Hierarchical Triangular Meshes but we ended up not really needing
| the faster indexing it offered since most of our processing was
| done in small portions of the sky at a time anyways.
|
| [0] https://arxiv.org/pdf/cs/0701164.pdf
| junon wrote:
| First thought: "this looks like what we used at Uber."
|
| Sure enough, it is. It works well IIRC and there's a lot of
| interesting math surrounding it. Some of our internal tools we
| had access to at the time (now, presumably, under lock and key)
| had maps laid out in hexagons.
|
| E: Some of the visualizers linked here seem a bit weird. I could
| be mis-remembering things, but the hexagons were WAY smaller than
| some of the visualizers here. I remember looking at the SF map
| and there was a lot of granularity even in the city center. Like
| I said though, could be mis-remembering.
| setr wrote:
| https://h3geo.org/docs/core-library/restable
|
| The smallest granularity is . 0000009 km^2, so I guess 1/3 of
| an inch. Which seems to me a ridiculously and unnecessarily
| precise, but who knows
| junon wrote:
| It wasn't that granular. Maybe a few blocks of the city in
| size, give or take. The visualizers I'm seeing have a single
| hexagon span the entirety of Austin, TX for reference. At
| least in Uber's usecase, that was less than useful.
| setr wrote:
| It's a hierarchy... so you can take your pick of
| granularity? Only thing that matters is min, max and step-
| size.
|
| Unless we're talking about different things, I'm not clear
| why we're not assuming the tool you remember chose h10 or
| whatever level was actually useful to it, where the
| visualizations chose h5
| junon wrote:
| I don't remember ours being a hierarchy but perhaps it
| was just the visualization.
| tln wrote:
| That table shows H15 cells are on average 0.9 m^2, or a
| hexagon with edges 0.59m long.
|
| (The average edge length is 0.5m, but that's not the same as
| the edge length of the average area hexagon)
| jti107 wrote:
| so its true....hexagons are the bestagons
|
| https://youtu.be/thOifuHs6eY
| serjester wrote:
| Uber's open source geospatial suite is simply amazing. A while
| back I used H3 to visualize snowfall in Colorado (powdamap.com)
| and the result came out way better than a grid based approach
| with the added of benefit of doing a better job representing a
| continuous variable.
| oofbey wrote:
| How was it better? I'm having trouble understanding why this is
| better than a simple grid. Grids on the surface of a sphere
| certainly have problems at high latitudes if naively applied.
| But they are incredibly simple to use, and don't have H3's
| problems of edges that don't quite overlap.
| rodonn wrote:
| Depends on your use case. Hex's have a lot of advantages when
| you are a transportation oriented company. All hexes are the
| same size and the distance between the center of any two
| adjacent hexes is always the same distance.
| https://h3geo.org/docs/highlights/aggregation
|
| As an example of where this is useful, it makes it very easy
| to get a list of all hexes with distance less than X from a
| current location.
|
| Here's a comparison they give to some of the other common
| geographical partitions https://h3geo.org/docs/comparisons/s2
| Pamar wrote:
| Yes. This is why, btw, wargames have more or less
| standardized in hex grids: no sudden 20% increase of speed
| for units moving diagonally.
| Sanguinaire wrote:
| Hexagons are the bestagons; better than all the
| restagons.
| peterb wrote:
| You forgot the reference video!! :-)
| https://www.youtube.com/watch?v=thOifuHs6eY&t=5s
| thehappypm wrote:
| Solve the problem "find me the all restaurants within 1 mile
| of of my location" efficiently in a database with restaurants
| and their lat-long coordinates.
|
| Brute force solution: iterate over all possible restaurants,
| compute their distance to your location, then return the list
| that meet the criteria.
|
| Better solution: cut the world into 1-mile square grids, and
| assign each restaurant a grid square index. Search for all
| restaurants in your grid square, plus all adjacent grid
| squares to that (because you might be on the edge of your
| square), and filter out the ones that are more than 1 mile
| away. This is a pretty good solution, but you're searching a
| square area for a circle of restaurants. Any restaurants in
| the corners of the square are wasting your time -- you're
| never within 1 mile of the corner.
|
| So, if you could search a circular area, you'd have no
| corners. Using tessellated hexagons means your search space
| is more circular, so it's more efficient.
| [deleted]
| jowday wrote:
| Sounds similar to Google's S2 library.
|
| s2geometry.io
|
| In S2, the binary representations of a cell's parents (larger
| cells that contain the cell) are always a prefix of the cell
| itself'a binary representation. This lets you perform constant
| time containment checks.
| rodonn wrote:
| They give a nice comparison of S2 vs H3 here
| https://h3geo.org/docs/comparisons/s2
|
| Which is better definitely will depend on your use case.
___________________________________________________________________
(page generated 2021-09-15 23:00 UTC)