6 ms·
H3: For indexing geographies into a hexagonal grid, by Uber
- artemonster 2y ago[flagged]
- zimpenfish 2y agoWhat, 3 words?!
- mablopoule 2y agoWhile I also agree about the general stupidness of what3words and the clearly predatory move of trying to move GPS location behind a proprietary database, the article is not about what3words at all. The link is about a grid system with different mathematical properties which is used at Uber.
- Traubenfuchs 2y agoIs the big thing here that those hexagons have the advantages of a circles (almost even max distance in all directions from center) with the advantages of squares (no overlap)?
- Epa095 2y agoSqaures have overlap if you put them on a sphere, no? There are some nice things with this. It contains cells at different levels (sizes). So you can use very small cells if you care about small areas, or large cells if you care more about larger areas. Those are given here https://h3geo.org/docs/core-library/restable/#average-area-in-km2 https://h3geo.org/docs/core-library/restable/#average-area-i... From a coordinate it is fast to get the cell at any level, so it's fast to group coordinates at whatever level you want. If is less about comparing two coordinates, it is more about bering able to group large numbers of coordinates such that they go into non-overlapping groups, where everything in the same group is 'close' to each other.
- at0mic22 2y agoI would assume you wouldn't care a lot about overlapping squares as the representation on the screen is mostly square, you don't order uber from the globe. Thus most screen projections are derived from wgs84. The idea behind h3 (as I see it) that when moving the map to lets say top-right, you'd need to fetch 1 leaf comparing to 3 leafs with rtree
- jillesvangurp 2y agoMost grid systems don't have overlapping squares because they are quad trees. Each point identifies a single rectangle they are in, and all the parent rectangles that fully contain that rectangle. H3 doesn't have that property between levels. Cells at a level don't overlap. But the the seven children of a cell might overlap with neighboring parent cells. Of course rectangles aren't rectangular when projected on a sphere. Because there are no straight lines. Rectangles and hexagons are 2d shapes that are applied to the 2d projections of spheres. They only look like rectangles or hexagons in 2D.
- cpa 2y agoYes, but it's important to note that it's quite a specialized index. - It's an index that doesn't depend on the data, unlike traditional r-tree indices. This means non-uniform data won't be queried as efficiently as with rtree, but it may be faster to build. - This data independence property is VERY important for distributed or streaming queries. For example, if you want to join datasets using Spark or other big data tools, each team can add a column for h3 cells independently and join somewhat efficiently. For large volumes of data, constructing the rtree is just not feasible, or more precisely, very disconnected from the rest of the "data ecosystem". - It doesn't work with any coordinate reference system other than EPSG 4326 (which you may want if you only work on specific geographies to get more precision in your floats) - It's clearly built with points in mind. Polygons, curves, or lines are an afterthought. For example, the polygonToCells function returns a set of cells that are entirely within the polygon. If you want to join, you'd need to also have the set of all cells that entirely contain the polygon. I've never found a reliable way to get that. That being said, it's not bad at all, but if you don't have so much data that you can't compute rtree indices, just stick with PostGIS.
- riordan 2y ago> Polygons, curves, or lines are an afterthought. For example, the polygonToCells function returns a set of cells that are entirely within the polygon. If you want to join, you'd need to also have the set of all cells that entirely contain the polygon. I've never found a reliable way to get that. With v4 of h3 they (finally) have a clean syntax for this with polygonToCellsExperimental[0]. Now there’s options for - Cell center is contained in the shape (default) - Cell is fully contained in the shape - Overlapping (covering): Cell overlaps the shape at any point - BBOX: Cell bounding box overlaps shape Makes life a fair bit easier if you’ve gotta deal with H3 polys. And if you’re working locally, DuckDB Spatial’s r-tree indexing[1] can make for a nice stand-in for PostGIS as a quick point-in-polygon solution without the need to spin up a service. [0]: https://h3geo.org/docs/api/regions/#polygontocellsexperimental https://h3geo.org/docs/api/regions/#polygontocellsexperiment... [1]: https://duckdb.org/docs/stable/extensions/spatial/r-tree_indexes.html https://duckdb.org/docs/stable/extensions/spatial/r-tree_ind...
- 2y ago
- ethbr1 2y agoOh, mon frère... there are many reasons. Hexagons. Are the bestagons. https://m.youtube.com/watch?v=thOifuHs6eY https://m.youtube.com/watch?v=thOifuHs6eY
- ahoka 2y agoHow is this better than space filling curves? Or does this solve a different problem? It’s a bit hard to see what and how it solves. Why hexagons?
- meowtimemania 2y agoIf you used curves it'd get complicated deciding where one area starts and the other ends. With hexagons it's easier to divide the world such that (mostly) no hexagon overlaps. The purpose is to be able to predictably map any coordinate to its associated hexagon. In database applications this makes it easier to query all data associated with a hexagonal area.
- xhkkffbf 2y agoWhy not just squares or rectangles? Is there a simple explanation?
- jt_b 2y agoYou want a shape that can represent an approximately equal area, anywhere on a 3 dimensional surface.
- meowtimemania 2y agoBecause it’s hard to cover a sphere in rectangles and have no rectangle overlap. It’s the same reason soccer balls aren’t covered in squares/rectangles but rather hexagons.
- jandrewrogers 2y agoIt depends on what you are trying to do. Hexagonal tessellations are optimized for display and visualization because they approximate equal surface areas on a sphere. They have poor properties for scalable and efficient analytical data processing because they are not congruent. Indexing for scalable analytical processing on a sphere requires congruent equal volume decomposition, even if you only care about the surface. You can trivially project it to the surface later if needed. Binary space decomposition, of which space-filling curves are a subset, are strongly preferable for this type of indexing. In practice, a lot of data processing systems will render data as an H3 tiles only for visualization as a final step. That conversion is fast and trivial and it makes pretty pictures. It is not as commonly used to index the underlying data model because scalability and performance is prohibitive unless the data is small.
- dplarson 2y agoI found this presentation helpful for an intro to H3's design/motivation: "Engineering Sub-City Geos for a Hyper-Local Marketplace with Uber": https://youtu.be/wDuKeUkNLkQ?si=-9JmxZQJ2LZo6Kh4 https://youtu.be/wDuKeUkNLkQ?si=-9JmxZQJ2LZo6Kh4
- naiv 2y agoThis online tool gives you great idea about what this means on different levels: https://wolf-h3-viewer.glitch.me/ https://wolf-h3-viewer.glitch.me/
- kemotep 2y agoThis is like the advantage of using 6 mile hexes in a tabletop rpg map.[0] Each hex can be divided into smaller hexes until you get to the level of feet/meters as opposed to miles/kilometers. [0]: https://steamtunnel.blogspot.com/2009/12/in-praise-of-6-mile-hex.html?m=1 https://steamtunnel.blogspot.com/2009/12/in-praise-of-6-mile...
- crazygringo 2y agoI've read all the comments here and still don't understand the rationale for hexagons as opposed to squares. In every sense, squares seem to be much easier to reason about and easier to hierarchically partition than hexagons are. There are certain advantages to hexagons in certain contexts, like six degrees of movement instead of four in board games, but I don't see how any of those advantages translate here for geographical indexing. I'd love to understand why hexagons as opposed to squares in this context are a superior solution rather than unnecessary complexity?
- gleenn 2y agoIIRC it has to do with tiling the globe. You can't correctly tild a sphere with swuares. On a local level, it seems easier to reason about squares on a flat surface, but the Earth is round and Uber is international.
- crazygringo 2y agoThanks! I'm still a bit confused because you can't tile the globe with hexagons either, if I understand correctly -- everything I can find online says you need a mix of hexagons and pentagons, and you can think of a soccer ball as an example. Has Uber figured out a way to do it with just hexagons?
- noplacelikehome 2y agoSince cars don't need to cross water, maybe this isn't actually relevant. Uber aren't trying to model the planet, just the routes within the geographies they support.
- tiagod 2y agoh3 has the required pentagons in the ocean (dymaxion icosahedron vertices)
- Tistron 2y agoAt least one of the pentagons is on Norway. And another one contains Beijing.
- tomtomistaken 2y agoHexagons could be a new kind of political entity of the future, where, for example, rewards for climate progress (measured by satellites) could be put into practice.
- LegNeato 2y agoThere is a super high quality Rust lib that implements this: https://github.com/HydroniumLabs/h3o https://github.com/HydroniumLabs/h3o
- wbercx 2y agoI'm still surprised What3Words isn't more popular outside of the UK.