Paco Albacete Chicano's Diary | [GSoC] Prototyping medial axis implementation for area routing | OpenStreetMap

Select Language

Loading...

Close

Paco Albacete Chicano's Diary

[GSoC] Prototyping medial axis implementation for area routing

Posted by Paco Albacete Chicano on 1 July 2026 in English.

Hi again!<br>During the last weeks I’ve been working on a Python prototype of the medial axis that will later be implemented in Valhalla

The goal of this prototype is to validate the algorithm, experiment with different choices and make it work for some synthetic and real OSM areas.

I’ve done it using Shapely, which is a python package built on top of GEOS (the library used by Valhalla). So thanks to Shapely I can implement the algorithm using functions that I’ll use in Valhalla, but in a much easier way without having to care about Valhalla’s complexity.

However GEOS doesn’t provide a medial axis implementation. So to achieve the medial axis we have to build it from the Voronoi Diagram. The thing with the Voronoi is that it doesn’t care about topology it just works with point clouds. So in order to get a medial axis of it we have to:

Collect all vertices from the polygon’s outer boundary and its holes

Generate the Voronoi diagram

Iterate over every Voronoi Edge

Discard every edge that is not completely contained within the polygon

And then we have our medial axis! This is a raw version, later we have to prune it as explained in the previous diary entry.

Algorithm overview

1. Building the polygon

The first step is whether to reconstruct the polygon from OpenStreetMap or create my own polygon to test the exact case I want to.

For example:

square = Polygon(<br>[(0,0),(5,0),(5,10),(30,10),(30,30),(0,30)], # outer ring<br>[(5,15),(10,11),(18,15),(18,20),(5,20)], # inner rings<br>[(2,5),(3,3),(4,5),(3,8)],<br>])

Because the Voronoi only considers the input vertices, the resulting skeleton becomes inaccurate, to mitigate this problem I densify every boundary segment using:

polygon.segmentize(1.0)

Which inserts one vertex every meter, this produces a much smoother approximation of the medial axis.

2. Voronoi generation

Once all vertices have been collected, we generate the diagram. However, this diagram extends outside the polygon. So every Voronoi edge is tested and only thoise completely contained inside the polygon are kept. Duplicate edges are also removed.<br>And now we have:

Plaza de Santo Domingo Murcia:

It starts looking good, but now we have to get the skeleton of it

3. Pruning dead branches

To better understand the implementation it is important to know what degree of a vertex is. And we can simply define it as the number of edges incident to that vertex.<br>(Don’t judge my drawing skills :))

So in order to obtain the skeleton, I compute the degree of every vertex, and iteratively walk from each leaf until reaching a junction (degree >= 3). And after removing these branches now we have it!

4. Extra implementations

There are a few more things I’ve implemented, like test entrances joining the skeleton to the closest point of the skeleton without crossing over a boundary.<br>Moreover, because of the densification we made before, what looks like an edge, they really are segments of ~1 meter, then I had to simplify these, joining everything between degree 1-3 or 3-3. So the numbers of edges remains low as we discussed, in my last diary entry, was a big pro of the medial axis.<br>Here is an example testing entrances:

Conclusion

This prototype has been extremely useful to validate the approach and understand the practical challenges. Thanks to doing it here first, we can experiment and refine the approach in a much easier way. Next step is bringing this into Valhalla.

Finally, thanks to Chris, Kevin and Nils who are always helping me a lot and they have been a great support! I want to also thank the people that commented on my last entry, all the messages have helped us to look for edge cases and refine our implementation, Thanks a lot!

I’ve kept this entry without much code so it can be understandable for everyone, but if someone is interested in the code implementation feel free to ask!

Location:

La Fama, Murcia, Puente Tocinos, Murcia, Área Metropolitana de Murcia, Region of Murcia, Spain

Discussion

Comment from SK53 on 2 July 2026 at 08:04

Might be just me, but the first image (a gif?) appears as “content not visible in your region”.

(I have an interest in skeletonisation and medial axes, see an old blogpost of mine.)

Leave a comment

Log in to leave a comment