Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors
podcast
Filter by Categories
ArcGIS Pro
GDAL
GeoJson
Map
Map Tools
Maps
postgis
Python
QGIS
Uncategorized

H3 geospatial indexing system

Isaac Brodsky is the co-founder of Unfolded. With a background in computer science and software engineering, he previously worked at Uber’s Marketplace, which is the heart of their operations; matching riders and drivers, dynamic and surge pricing, guidance to driver-partners, and so on. All the things that affect what people call marketplace dynamics or supply and demand.

Isaac ran some large Elasticsearch clusters and provided geospatial data to understand those markets. Dynamic pricing needs spatial information, and that’s how he came into contact with the H3 projectInitially, he led the project from the data side, and then from the publishing and open source side.

IS H3 A SPATIAL INDEX? IS IT A COORDINATE SYSTEM? WHAT KIND OF GRID SYSTEM IS IT?

The academic term for H3 is a discrete global grid system.

It’s a discrete system, breaking up the world into discrete cells. Every position in the world has a cell identifier associated with it. It’s global. It doesn’t matter if you’re at the North Pole, the South Pole, the antimeridian, in the middle of the Pacific Ocean, or somewhere in Texas, it will cover you.

H3 is also a system of grids. It’s not only a single resolution grid at a certain resolution (cell or size), but it’s a system of all of them. All 16 resolutions of the grid relate to each other; the resolution 10 grid, for example, is created by subdividing the resolution 9 grid in the H3 system and so forth.

WHY DID YOU CHOOSE HEXAGONS?

Hexagons throw people off when we say that H3 is a hierarchical grid, plus it’s hexagons.

In H3, we subdivide each cell into seven smaller cells. If you try to draw that out, you’ll realize it doesn’t fit right. We had to make some compromises to get that to work. Why? Because it causes us to make these trade-offs, and there’s some kind of odd edge cases with it.

Why hexagons?

We needed a shape that we can tile over the entire Earth. There are some pentagons in the H3 system, but we put them in out-of-the-way places where we hopefully won’t have to deal with them. We also need to model things moving around in the actual world. That’s the key use case Uber had for it. Hexagons have this neat property; all the neighbors are the same distance apart.

For squares, four neighbors share an edge. But then four neighbors are sharing all their points with that square, and those neighbors have a different distance, center to center, from the original square. With hexagons, all the neighbors are the same distance apart. This makes it much more convenient to run a variety of different algorithms on top of the grid.

IS THIS WHAT’S CALLED UNIFORM ADJACENCY?

I believe that that’s the case. It’s certainly the case that you’re able to model these neighbors as being roughly the same. There is a bit of variation in terms of the size from neighbor to neighbor. Still, in my experience, this rarely varies significantly enough that you’d be concerned about it. It is a very uniform grid.

WHAT ABOUT THE KNOWN ISSUES WITH HEXAGONS?

We can’t solve those entirely.

But we can make it a lot harder for you to run into cases you want to avoid. The first thing when you’re converting to the H3 grid—a point, a polygon, or any kind of shape—is you’re giving H3 both those coordinates for that point, plus a resolution, and what we call an indexing operation.  This is so you can work with it inside of the grid system. The indexing operation is exactly at that resolution.

If I tell the system, “I want to index this point at resolution 8,” it’s going to give me the cell that contains precisely the resolution 8 inside of H3, without being affected by any distortion. The difficulty happens when you want to move between different resolutions of the H3 grid.

When H3 subdivides cells, it slightly offsets them from one resolution to another. This causes a zigzag or jagged pattern around the edge of cells. When moving between one resolution to another, for instance when you truncate the precision of the resolution itself that we got to resolution 7, there will be a bit of the cell area, which is an error if you try to render that cell out. According to my calculations, 7% – 8% of the area that is an error.

Your analysis may be okay with this, perhaps you got your data from GPS, and you’re not that certain of where exactly this point was, in which case you just continue from there.

For some use cases where you do want to preserve those exact boundaries in cells, you have to be more careful to ensure that you don’t render the data at a different resolution than what you originally indexed it at. For example, you could truncate the position of the index to save space when you’re storing data in a database. When you’re rendering it out, use that original resolution that you used.

IS THIS DESIGNED FOR SPECIFIC USE CASES?

The use cases of receiving GPS locations influenced us in a big way. For those, a smoothing operation is usually beneficial because you have uncertainty as to where the data point occurred. When you have a great deal of certainty, you need to be preserving boundaries. If you’re trying to use it as a spatial index, you might want to choose a discrete global grid system that has an exact containment property that H3 doesn’t have.

IMPORTING DATA TO THE H3 GRID SYSTEM

I have a polygon building layer for all of the buildings in Denmark. I want to use the H3 system. Can I? What does the process look like? Does it make sense to use H3?

You can, and it certainly makes sense.

Let’s expand on the example and say you want to calculate the density of buildings or the number of buildings in an area or different areas.

Using H3, we start by inputting the data, which is the polygons and any information associated with those buildings. H3 has functions that we use to convert from this data, a point or polygon form, into the H3 grid.

These functions have bindings to several programming languages and different databases. It’s a bit of a do it yourself endeavor at the moment. Maybe you know Python, R or Java, or one of the other programming languages. If you’re using Postgres, Elasticsearch, or similar databases, you’ll be able to do it within those environments.

From there, select a function in H3 called polyfill. It takes an input polygon and finds the H3 indexes which cover it. Polyfill has an odd history in terms of how it was built. It makes some assumptions that you’d want to have exclusive coverage. In our case, it doesn’t sound like we want to have that, so we might index that at a little higher resolution than we normally would.

The result is a list of indexes for every single building. You can now use your usual off the shelf data processing tools.

This is one of the great things about H3. It takes these data processing tools that we would use for other kinds of data and applies them to geospatial data. It scales really well. If you wanted to use Pandas, Spark, or Python for this, you could do that. If you want to use an off-the-shelf database, you can use that because they’re able to treat these H3 identifiers as strings or integers and work with them efficiently.

When you have that, you have your data source that is built using the H3 system, and you can use it for analytics. You have mapped them from the H3 identifier to a metric value for that cell. You can do database lookups, and you can say, “I’m in this area, I want to know how many buildings there are around me.” It’s just a matter of checking where I am, finding the H3 identifier, and then looking that up in a database that is set up to map from the H3 identifier to that metric value.

Next, you can also do visualization and send your list to a visualization tool, such as Kepler.gl, or Dec.gl, that can understand H3 identifiers. You can create a heat map of where these buildings are in Denmark.

Note that this is happening without converting the data between different formats. You’re able to do all these different things, analytics and modeling, lookup, search, spatial indexing functions, and visualization, all with the data being kept in the same format.

CAN I ATTACH MULTIPLE VALUES TO THE IDENTIFIER?

In terms of attaching multiple values to it, that’s something that H3 doesn’t have an opinion on.

It doesn’t really know what you put next to it inside of your database. You could create a database in a Big Data system where one of those columns is an H3 identifier. The other columns can be whatever you want them to be, within the constraints of that database. You can attach categorical or numerical metrics to it, or if you wish, attach original geometries (which might be a little bit expensive, but it’s certainly possible, especially for points).

H3 doesn’t have a constraint on it. What it’s handling is that single column that’s the spatial identifier and what you’re probably using is a primary key for that table. What you do with the rest of that table is up to you. You choose what you want to associate with that identifier.

HOW DOES THIS COMPARE TO THE SPEED OF AN AVERAGE RADIUS LOOKUP, A POINT IN A POLYGON, OR WHAT IS NEAR ME?

The answer to this really cuts into the use of H3 as a spatial index.

If you’re only concerned about the very immediate surrounding, i.e., what is the cell you’re in, it compares favorably.

Let’s say you use a database that maps from keys to values ̶ it maps from a hexagon key to a value. For that lookup operation, it is also generally going to be roughly constant time. If you wanted to do a neighborhood lookup, you might have to scan many different points and compute their distances from where you are now to where those points are.

Maybe you want to find things that are within a certain radius of you. H3 is very interested in the radius question. This, as we mentioned before, is about the equidistant neighbors and is a very important property of the H3 grid that finds these rings around an origin. These rings, approximate a circle as best as they can.

You can generate, let’s say all the cells that are within two grid distance from you, and then do the lookups on those. This increases the complexity slightly because you need to look up these different cells that are near you. But you’re able to take advantage of the spatial index and property, finding nearby cells and the hexagon property ensures that nearby cells approximate a circle.

IS TRANSFORMING IMAGE DATA WITH RASTER DATA INTO THE GRID POSSIBLE, LIKE WITH DISCRETE DATA?

It is possible.

I just saw an example where someone placed elevation data into the H3 grid. As you can imagine, like when we talked about polygons earlier, similar processes can be used for an extensive range of data.

There are different ways to get a raster into the H3 grid. One is by sampling from the raster. We take an H3 grid, and we find a bunch of points we want to sample from the raster. Then we use that to move that raster data into the grid.

Another way is by taking all the pixels in that raster and finding the associated H3 cell and moving the data in that way.

CAN YOU THINK OF EXAMPLES WHEN H3 IS NOT THE RIGHT CHOICE?

All grid systems have some trade-offs. We make decisions when we implement a grid system in terms of the projection that we use, the cell shape, and the cell subdivision.

The one that jumps to my mind is the hexagon hierarchy issue that we touched on earlier. If we do have a use case that requires very exact containment, perhaps it has parcel data or political data where we cannot have an approximate containment, but we still need to do this truncation, in that case, you might not want to use H3, or it might be more complicated to use it.

H3 tries to be roughly equal-ish area, but it’s not an equal area system. If you have use cases that require this kind of property, it might be something where H3 is not a good fit for you.

WHAT IS THE ADVANTAGE OF USING H3 TECHNOLOGY WITH SPATIAL ANALYTICS AND VISUALIZATION?

There are a few advantages that H3 gives us.

There’s a tremendous advantage of having a geospatial analytics system that’s grid integrated throughout the entire system. We talked earlier about the example of how you may need to index, process, and visualize the data. A lot of the power and benefit of having data in a discrete global grid system like this comes from an integrated experience.

We’re hoping to build an experience at Unfolded, where data on the back end, on the front end, and in between, is all in a consistent geospatial format. This lets us work with all the different Big Data tools, and even small data tools, on the data.

Maybe you have some code data if you’re in the US, another grid system, and even a raster. You still want to be able to work with these different formats. Getting data in and out of H3 is flexible, as we have seen. One of the key things that we’re able to do at Unfolded because we have this H3 grid system is to unify data spatially in a way that’s very difficult with other technologies. We’re able to project data between geometries.

As a good example, in the US, we have customer data in zip code format, and we have demographics data in a format we’d get from the US Census Bureau. They use different geometries which the H3 grid joins together. We can also bring in raster,  GPS tracks  and all these different data and unify them into a simple analysis that the user is doing. It makes it a lot easier to access geospatial data.

ARE YOU CONVERTING EVERYTHING INTO HEXAGONS, AND THEN TREATING THEM AS INDEPENDENT GEOSPATIAL LAYERS?

Yes, and the ability to convert data back out of hexagons is just as critical. This allows you to transform between that sample of the US Census of geographies to zip codes. We’re able to use a hexagon grid to transform remarkably efficiently from one polygon geometry to another. Users can do their analysis in a geometry that they’re comfortable with and that they feel useful.

WHAT IS YOUR FAVORITE ADOPTION OF THE H3, EXCLUDING UBER?

That’s a hard question.  There are so many ways to use it that I’ve seen- like wildfire analysis or urban planning uses. It’s an open-source project, and we don’t necessarily always get feedback on how people are using it. If you have an interesting use case, if you’re using H3 in different fields, I’d love to know what you’re using it for, and how you’re using it. It’s beneficial to understand what people are doing with it when we’re thinking about maintaining the project.

The use case that appealed to me the most is in the gaming and gamification space. I’ve heard of a couple of ideas around this. One of them is a data provider that’s gamifying data collection for some of their users. There’s just something timeless about game development. What appeals to me is anything that’s building games on top of H3. Think of the successes of Pokémon Go and other augmented reality games. It’s just a fun use case, if nothing else, to see H3 pop up as part of a game system.

Geospatial integrated into games, and in the hands of everyday people? I think it’s fantastic. What would you use H3 for?  

About the Author
I'm Daniel O'Donohue, the voice and creator behind The MapScaping Podcast ( A podcast for the geospatial community ). With a professional background as a geospatial specialist, I've spent years harnessing the power of spatial to unravel the complexities of our world, one layer at a time.