Просмотр новости
Найдите то, что Вас интересует
Спутники
РН
SpaceX
Роскосмос
NASA
СпутникиРНSpaceXРоскосмосNASAHi 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)],
])
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.
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.
(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.
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.
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!
| # | Наименование новости | Тональность | Информативность | Дата публикации |
|---|---|---|---|---|
| 1 | About OSM for Cities | 0 | 7 | 29-06-2026 |
| 2 | Tile server for toll roads, cycling restrictions and cobblestone overlays | 0 | 5 | 29-06-2026 |
| 3 | Sobre OSM for Cities | 0 | 5 | 29-06-2026 |
| 4 | Sobre o OSM for Cities | 0 | 7 | 29-06-2026 |
| 5 | Supermarchés à Genève de A à Z (ou plutôt de A à M) | 0 | 3 | 27-06-2026 |
| 6 | Adding cuisine and shop-tag context for 8 trade-business nodes in NC | 0 | 5 | 27-06-2026 |
| 7 | Documenting POI cluster — 8 offices in 100-mile NC corridor | 0 | 5 | 27-06-2026 |
| 8 | Globe Meet-up last time. Albert pub tonight | 0 | 5 | 30-06-2026 |
| 9 | Cross-checking phone formatting on 8 LCC nodes — E.164 vs US-local | 0 | 5 | 27-06-2026 |
| 10 | Proposing description tag conventions for small-business offices in NC | 0 | 5 | 27-06-2026 |