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

Recently at Mapbox we open sourced RoboSat our end-to-end pipeline for feature extraction from aerial and satellite imagery. In the following I will show you how to run the full RoboSat pipeline on your own imagery using drone imagery from the OpenAerialMap project in the area of Tanzania as an example.

Goal

For this step by step guide let’s extract buildings in the area around Dar es Salaam and Zanzibar. I encourage you to check out the amazing Zanzibar Mapping Initiative and OpenAerialMap for context around the drone imagery and where these projects are heading.

High-level steps

To extract buildings from drone imagery we need to run the RoboSat pipeline consisting of

• data preparation: creating a dataset for training feature extraction models
• training and modeling: segmentation models for feature extraction in images
• post-processing: turning segmentation results into cleaned and simple geometries

… See full entry

At Mapbox we are happy to open source RoboSat our production ready end-to-end pipeline for feature extraction from aerial and satellite imagery. In the following I describe technical details, how it will change the way we make use of aerial and satellite imagery, and how OpenStreetMap can benefit from this project.

Berlin aerial imagery, segmentation mask, building outlines, simplified GeoJSON polygons

… See full entry

Wir (Mapbox) haben soeben RoboSat unter einer MIT Lizenz auf Github veroeffentlicht. RoboSat ist ein generisches Ecosystem um aus Luft- und Satellitenbildern Daten zu extrahieren. Im Folgenden beschreibe ich die technische Umsetzung und wie es fuer OpenStreetMap eingesetzt werden kann.

Luftbilder von Berlin, Segmentierungsmasken, Gebaeudeumrisse, vereinfachte GeoJSON Polygone

… See full entry

In the following I describe how we implemented reasonable alternative routes in the Open Source Routing Machine’s Multi-Level Dijkstra mode.

Final result: generating reasonable alternative routes incredibly efficiently

Our main goals when designing and implementing reasonable alternative routes were two-fold:

• provide reasonable alternative routes for end-users and use-cases such as generating many alternative routes letting users or developers decide between them (e.g. runner’s app, start and end is the same but provide different route each day), and
• guarantee for fast query times in the tens to lower hundreds of milliseconds to fit the Open Source Routing Machine’s trade-off of doing heavy pre-processing and then get incredibly fast exact responses

But what exactly do we mean by “reasonable” alternative routes? When we find a fastest route and compute alternatives these are the criteria we try to optimize for:

… See full entry

Im Folgenden beschreibe ich wie wir Alternativrouten in den Multi-Level Dijkstra Algorithmus der Open Source Routing Machine implementiert haben.

Endprodukt: effiziente und plausible Alternativrouten

Unser Fokus beim Designen und Implementieren von Alternativerouten lag dabei auf:

• hoch-qualitative Alternativerouten zu generieren: fuer den Endanwender und fuer Anwendungsfaelle die von vielen Alternativerouten profitieren koennen (z.B. eine Jogging-App bei der Start und Ziel ueber die Woche hinweg gleich bleiben aber die Route sich aendern soll), und
• gleichzeitig fuer schnelle Antworten der Routingengine garantieren zu koennen, die im Bereich von 10-100 ms liegen und damit in das Konzept der Open Source Routing Machine passen wobei pre-processing benoetigt wird aber dafuer extrem effizient und schnelle exakte Routen berechnet werden koennen.

Hier sind die Kriterien nach denen wir die Qualitaet der Alternativerouten beurteilen:

… See full entry

We are releasing 10.4k turn restriction detections located across 5.2k intersections for the OpenStreetMap community.

Map

Raw GeoJSON data

---

These turn restriction detections were sourced by applying our machine learning computer vision models to Bing Streetside imagery. Mapbox has acquired the right to contribute these detections to OSM.

“Detections” are not really the same thing as turn restrictions. Rather, they are suspected, but unverified turn restrictions. We are planning to manually verify these turn restrictions, and our data team is working through the list, but the first pass produced thousands of candidates, so verification will take a while. We do think these can be useful to the OSM community, who may wish to move faster on improving OSM based on these detections.

… See full entry

It isn’t always obvious where to position a highway=motorway_junction node that connects a motorway way to a motorway_link way (also known as an off-ramp or slip road). Over the years, mappers have used three different approaches.

Inconsistent placement of junction nodes can affect turn-by-turn navigation software, particularly instruction timing and rerouting. I’d like to raise awareness about the preferred placement, which is at the beginning of the gore, and explain why the other two approaches are suboptimal.

Throughout this post, I will refer to the term gore. A gore is a wedge that separates a ramp from the main motorway. A physical gore may be a barrier or a grassy area, whereas a theoretical gore simulates this separation using pavement markings and empty space. By “gore”, I am referring to the beginning of the theoretical gore, if present, or alternatively the physical gore.

… See full entry

Es ist nicht immer offensichtlich wo eine highway=motorway_junction Node, an der ein motorway_link Way abgeht, gemappt werden soll. Im Folgenden betrachte ich die drei am häufigst genutzten Modellierungsmethoden mit ihren Vor- und Nachteilen insbesondere im Hinblick auf die Routenplanung und Navigationsansagen.

Dabei dient folgendes Schema als Grundlage in welchem der “physical gore” die physische Abgabelung der Strasse und der “theoretical gore” den Beginn der Fahrbahnflächenmarkierung darstellt.

Modellierung I: Node am Ausfahrtsschild

In manchen Fällen gibt es ein letztes Überhangs-Schild an dem das Abbiegemaneuver noch getätigt werden kann.

… See full entry

Here’s a map I got out of our Open Source Routing Machine when I built a validator for sharp turns onto ramps. The idea behind this validator is that turns onto highway ramps should never be sharp (i.e. < 90’ish degree). There is a high chance a turn restriction is missing at those locations.

With these checks enabled I found roughly 30k intersections on the planet. I visualized the results in the map below; the redder the circle, the sharper the turn angle onto the ramp.

Click for interactive map

In the results I found an issue that frequently re-occurred. Consider the situation below: heading east on Goff Mountain Road (the yellow line), there is a ramp on the right that you can legally take. Around the bend, there is another ramp onto the same road for drivers going west on Goff Mountain Road.

… See full entry

Hier ist eine Karte die ich mit unserer Open Source Routing Machine generiert habe als ich nach spitzen Winkeln beim Abbiegen auf Ausfahrten gesucht habe. Solche Abbiegevorgänge sollten niemals vorkommen und sind ein gutes Indiz für fehlende Abbiegeeinschränkungen.

Hier ist eine Visualisierung; je röter desto spitzer der Winkel.

Interaktive Karte

Ein Problem was immer wieder aufzutauchen scheint ist das Folgende (siehe Bilder unten): aus dem Westen kommend auf der Goff Mountain Road gibt es eine Ausfahrt auf der rechten Seite. Kurz nach dieser Ausfahrt ist eine zweite Ausfahrt für die Gegenrichtung.

Wenn man nun aus dem Osten kommend auf der Goff Mountain Road fährt und die Ausfahrt verpasst gibt einem die erneute Routensuche die Anweisung die nächste Ausfahrt der Gegenrichtung zu nehmen! Hier fehlt die Abbiegeeinschänkung in den OpenStreetMap Daten.

… See full entry

The Open Source Routing Machine supports bearing constraints for quite a while now. In the following I want to highlight their use-cases and effects on routing.

Suppose you are driving north and make a routing request. An instruction to take a U-turn — since the routing engine does not know your heading — would be undesirable. This is the primary use-case for setting bearing constraints.

Setting a constraint of bearings=0,90 tells the routing engine you are heading north and you want to allow for a variation of +-90 degree around true north. The format is value, range with

• value in 0, 360 degree for the direction; 0 degree represents true north, 90 represents east and so on
• range in 0, 180 degree for the allowed variation around the value; a variation of 90 degree allows for +- 90 degree

The bearings=0,90 constraint therefore allows the route to start off towards north +- 90 degree. But not in the opposite direction you are currently heading. Sweet!

Another interesting use-case I came across at FOSSGIS is fire truck routing where your vehicles have to arrive at the right side of the street. Using bearing constraints not only for the route’s start but its end location we can let the routing engine generate optimal routes which guide vehicles to the right side of the street.

Here are two routes from a fire department in Berlin to an arbitrarily chosen location:

• In orange with a bearing constraint of 0,90 guiding the fire trucks to the location from the northern direction (raw request)
• In green with a bearing constraint of 180,90 guiding the fire trucks to the location from the southern direction (raw request)

… See full entry

Die Open Source Routing Machine unterstützt seit längerem das Einschränken der Richtungen bei der Abfahrt und Ankunft. Im Folgenden zeige ich Anwendungen dafür auf und wie sich das Feature auf die Routenfindung auswirkt.

Angenommen wir fahren in Richtung Norden und machen eine Routing Anfrage. Was wir auf keinen Fall hören wollen ist die Aufforderung sofort eine Kehrtwende zu machen, nur weil die Routing Engine unsere Fahrtrichtung nicht kennt. Und genau das ist der perfekte Anwendungsfall für das Einschränken der Richtung bei der Routenplanung.

Wir können eine Einschränkung der Richtung erzwingen indem wir den Parameter bearings=0,90 setzen, was der Routing Engine mitteilt, dass wir in Richtung Norden fahren und +-90 Grad Variation zu Nord erlauben. Die Option bearings=value,range erklärt sich wie folgt:

• value in 0, 360 Grad für die Richtung; 0 Grad für Norden, 90 für Osten und so weiter
• range in 0, 180 Grad für die erlaubte Variation; eine Variation von 90 Grad erlaubt +-90 Grad

Die bearings=0,90 Einschränkung erlaubt es also dass die Route grob in Richtung Norden startet mit einer Variation von +- 90 Grad. Dadurch filtern wir also Routen die gegen unsere aktuelle Fahrtrichtung starten. Perfekt!

Ein weiterer Anwendungsfall den ich auf der FOSSGIS aufgeschnappt habe ist Feuerwehr Routing, wobei die Fahrzeuge auf den richtigen Strassenseiten ankommen sollten. Wenn wir die Richtung nicht (nur) für den Start einer Route einschränken, sondern für das Ende, können wir die Routing Engine benutzen um optimale Routen zu generieren die uns auf die korrekte Strassenseite führen.

Hier sind zwei Routen von einer Feuerwehr in Berlin (im Bild weiter im Süden) zu einer beliebig ausgewählten Position:

• In Orange mit einer Einschränkung von 0,90 welche die Feuerlöschfahrzeuge aus dem Norden kommen lässt (Anfrage Details)
• In Grün mit einer Einschränkung von 180,90 welche die Feuerlöschfahrzeuge aus dem Süden kommen lässt (Anfrage Details)

… See full entry

In which I explain the differences between the exit_to= tag on the highway=motorway_junction node and the more recent destination= tag on the way branching off of the motorway. In addition I will show the need for handling both tags and leave you with a tool for automatic rewriting.

To provide great guidance for our Open Source Routing Machine users we want to include ramp information for highway navigation.

There are two established tagging schemes for highway ramp signage:

• Using the exit_to= tag on the highway=motorway_junction node where the ramp branches off of the motorway. This tagging scheme was established mainly because the default Mapnik style displayed the tag quite nicely.
• The more recent destination= tag on the way branching off of the motorway.

Why do we have two completely different tagging schemes? Have a look at the following example where a ramp branches off the continuing motorway:

a . . . b . . d .
          ` . c .

In this case the exit_to tag is placed on the node b together with the highway=motorway_junction tag. So far so good. Now consider the common situation where multiple numbered exits diverge at a single point.

            . c
a . . . b `
          ` . d

Now there are destination signs for the ways bc and in addition for bd. There are workarounds like exit_to:left and exit_to:right tags but as you can imagine these do not suffice for more complex situations.

For these situations the destination tag is the better alternative.

Here in an example for where we need such a workaround.

… See full entry

Um den Nutzern unserer Open Source Routing Machine anständige Instruktionen liefern zu können, wollen wir Informationen zu Schildern an Autobahnausfahrten einbeziehen.

Es gibt zwei Tagging Varianten für Autobahnausfahrtsschilder:

• Den exit_to= Tag, gesetzt auf der highway=motorway_junction node an der der Ausfahrtsweg abgeht. Diese Art des Taggings wurde hauptsächlich verwendet da der standard Mapnik Stil es recht gut aussehen lies.
• Der neue destination= Tag auf dem Way der Ausfahrt.

Warum brauchen wir zwei grundweg unterschiedliche Tagging Varianten? Hier ist ein Beispiel für eine fortfahrende Autobahn und eine Ausfahrt:

a . . . b . . d .
          ` . c .

Hier kann der exit_to Tag auf der node b zusammen mit dem highway=motorway_junction Tag gesetzt werden. Soweit so gut. Was passiert nun aber bei mehreren Ausfahrten die sich alle an einer einzelnen node auftrennen?

            . c
a . . . b `
          ` . d

Hier wollen wir Ausfahrtsinformationen für bc als auch bd setzen. Dafür gibt es Workarounds wie exit_to:left und exit_to:right, die aber schon bei gering komplexeren Situationen versagen.

Für genau diese Fälle ist der destination Tag die bessere Alternative.

Hier ist ein Beispiel wo ein solcher Workaround verwendet wird.

… See full entry