Hi again! 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(
[(0,0),(5,0),(5,10),(30,10),(30,30),(0,30)], # outer ring
[
[(5,15),(10,11),(18,15),(18,20),(5,20)], # inner rings
[(2,5),(3,3),(4,5),(3,8)],
])
