How an algorithm from the 80s sets the new standard for modern spatial indices

Geospatial indices are all around us. They allow us to search through millions of points in an instant answering questions such as “find me the closest bike repair shop” efficiently.

And yet there are still forgotten gems in the archives of computational geometry: Space-filling curve based spatial indices. With an optimization going back to the year 1981 this spatial index delivers surprising efficiency; and yet it is rarely discussed in the geospatial community.

Let’s go back in time and rediscover how we can build a spatial index on top of a space-filling curve to accelerate geospatial queries and simplify geospatial indexing for location-based applications.

Note: If you know about Z-Order Curves or Hilbert Curves already I still recommend you reading this as the post below will show you how use Z-Order Curves efficiently as a spatial index and that is something you probably don’t know yet.

Note: Now available on NPM as zbush

npm install zbush

The Z-Order Curve

The Z-Order Curve is one of many space-filling curves transforming multi-dimensional data into a single dimension while preserving locality. In the geospatial domain it allows us for example to transform longitude and latitude into a single number while preserving geographic proximity.

For spatial queries such as “find me the closest bike repair shop” we want to find points within a rectangular area. To search a rectangular area on the Z-Order Curve (highlighted in gray below) we start at the top left Z value of the rectangular area and walk the curve until we’re at the bottom right.

… See full entry

With 2024 officially being the year of OpenStreetMap vector maps let’s do a deep-dive into vector maps: their history and how the underlying vector tiles work in detail.

Vector Maps History

To understand how revolutionary vector maps were we have to go back in time to the early 2010s. One Direction is raising to international fame and raster maps are at the height of their popularity. Folks creating raster web maps rendering OpenStreetMap data into beautiful 256x256 pixel images.

But raster maps come with limitations: when you rotate the map the labels stop facing you; you can’t customize pre-rendered maps to specific use-cases on the fly; there is no fractional scaling between zoom levels. All of these problems are unthinkable nowadays: here is one example where Jochen wrote about Wikipedia struggling with pre-rendering multilingual maps for over 200 languages because they can’t change their map’s language on the fly.

… See full entry

Maplibre and Protomaps are a match made in heaven! Together they are democratizing vector maps! There’s no better time to get involved than now; let me set the scene first.

Maplibre SDK with Protomaps vector tiles, map at an angle with a video source playing drone footage video overlayed; data attribution (c) OpenStreetMaps and contributors

Maplibre is the open source map SDK forked from mapbox-gl-js when Mapbox changed their license and moved away from open source in 2020. Maplibre packages up around seven years of state of the art map renderer development and is best in class in terms of map rendering and styling vector tiles.

Protomaps is a relatively new project and it’s fundamentally changing how vector maps are distributed. Protomaps can package up the whole world into a single .pmtiles files of around 100 GB. Static hosting this single file gets us global vector tiles! Magic!

… See full entry

Servus, Bayern! After releasing robosat v1.2 I trained it on 80cm aerial imagery to predict all buildings in Bavaria. tl;dr - here you can find the checkpoint ready to use.

Robosat is an open source end-to-end pipeline for feature extraction from aerial and satellite imagery seamlessly integrating with OpenStreetMap for automated dataset creation.

I downloaded the CC-BY-3.0 80cm aerial imagery from 2018 for Bavaria the Bayerische Vermessungsverwaltung provides. I then used the open source robosat v1.2 release to automatically create a training and validation dataset and trained it on my gpu rig. Within days we already get reasonable results without manual work involved.

For detailed instructions on how to create a dataset and run the robosat pipeline see my previous diary where I explain the process on drone imagery.

Here is a heatmap of all the z17 tiles in Bavaria where there are buildings

And here are two examples for the segmentation probabilities I get

… See full entry

I’m happy to release RoboSat v1.2.0 — RoboSat is an open source end-to-end pipeline for feature extraction from aerial and satellite imagery seamlessly integrating with OpenStreetMap for automated dataset creation.

This release is powered by major community contributions: state of the art Lovasz pixel-wise segmentation loss, better metrics, a road extraction dataset creation handler, and bug fixes! Thank you to our contributors!

v1.2.0 is also the first release shifting from a Mapbox sponsored development process to a community owned development process (after I quit Mapbox end of last year). New features, bug fixes, training and prediction all happens on my personal GPU rig now.

6 x GTX 1080 TI. Yes, the LEDs are necessary - they make it go fast

Here is an overview of what you will find in the v1.2.0 release

… See full entry

I’m happy to announce the RoboSat v1.1.0 release — our open source end-to-end pipeline for feature extraction from aerial and satellite imagery.

This release is powered by major community contributions from features like fine-tuning trained models, to training and prediction speedups, and bug fixes! Thank you to our contributors!

Here is an overview of what you will find in the v1.1.0 release

• rs train: new --checkpoint argument to re-start training (fine-tune) from a trained model checkpoint. Thanks https://github.com/ocourtin

• rs train: memory usage reduction during validation by disabling expensive gradient computation. Thanks https://github.com/Jesse-jApps

• rs train, rs predict: speedups using multiple workers and doing metric calculation on GPU. Thanks https://github.com/ocourtin

• rs merge: polygon orientation fixes to respect the GeoJSON specification (right-hand rule). Thanks https://github.com/marsbroshok

You can find automatically built Docker images at https://hub.docker.com/r/mapbox/robosat/

---

For our next release we already have a couple amazing community contributions

• rs extract: a new road extraction handler to automatically generate a training dataset for roads; Thanks https://github.com/DragonEmperorG

• New state of the art losses (like the Lovasz loss) and improved metrics among other improvements. Thanks https://github.com/ocourtin

Here’s why you should be excited for the Lovasz loss: the following shows a preview

… See full entry