GSoC 2026 with OpenStreetMap
Routing through pedestrian areas in Valhalla
During this Google Summer of Code, I’ve solved a very common problem that pedestrian routers have by adding the feature to route through open pedestrian areas, such as squares, plazas, pedestrian zones… instead of routing around the perimeter.
It’s now merged and running on the full planet build. Where pedestrians used to be sent all the way around the perimeter, Valhalla now creates a path straight across it.
Before :
Now:
See the Square Plaza de Santo Domingo, Murcia
You can try a demo of the feature on openstreetmap.org:
Here
Table of contents
About the project
What is Valhalla
Valhalla is an open-source routing engine that calculates directions using OpenStreetMap data for driving, cycling, walking, and more.
It works by turning raw OSM data into routing graphs that generate routes for different means of transport.
The problem
In OpenStreetMap, open pedestrian areas are often mapped as polygons with the tags highway=pedestrian + area=yes. Valhalla treated these polygons as obstacles because these areas don’t have explicit sidewalks to route through, so it might have routed around the perimeter but never across them.
This led to some cases with extremely long and nonsensical routes. This is a long-standing pain point in pedestrian navigation, even for the big companies.
See one clear example of the problem: 
The goal
The goal of my project was to make Valhalla able to cross these open areas. The scope I agreed on with both my mentors was to cover the large majority of areas in the world, in a robust and mergeable way.
How it works
We had to choose an algorithm that could solve this problem as efficiently as possible, because there are some known algorithms that might seem like excellent options but are extremely inefficient. After doing extensive research (more detailed comparation in my past diary entry) we selected the medial axis approach.
This is how the skeleton of a medial axis looks on a complex square: 
The pipeline
1. Recovering the area geometry
The whole process is integrated into Valhalla mjolnir, the tile builder.
First of all, areas mapped as relations have member ways with no routable tags, so the normal parsing process discarded them. Moreover, areas mapped as ways were also discarded. So naturally the first step was to start parsing them.
This was resolved in two different ways, for the tags discarded at the beginning of the pipeline I had to make some changes to start keeping these areas in the files, see my Pull Request [GSoC] Pedestrian area routing: Detect areas during parsing.
For the member ways, it’s a more complicated case, because Valhalla’s pipeline order makes it impossible for us to collect these member ways before parsing the relations, so we came up with a new stage to recover these ways and preserve their geometry alive. This stage (ParseAreaWays) can be seen in my Pull Request [GSoC] Pedestrian area routing: Build area polygons and generate medial axis.
2. Building the traversal
Next, there is also a new stage (BuildAreas), where for each area, it assembles the polygon (including holes), densifies it, and computes a Voronoi diagram of the points to approximate the medial axis, prunes the branches reaching toward the corners, connects each entrance to the nearest skeleton vertex it can reach and materialises the result as synthetic footways.
These synthetic footways are built as normal footways so they can be processed through the rest of the pipeline just like any other footway. If you are interested in a long explanation of the algorithm you can look for my diary entry: [GSoC] Prototyping medial axis implementation for area routing
And for the explained code see: [GSoC] Pedestrian area routing: Build area polygons and generate medial axis.
3. Synthetic OSM IDS
The generated ways and nodes, as I mentioned before, are treated as “normal” ways and nodes, so they need synthetic OSM IDS. They get ids above the highest real OSM way and node ids, so they never collide with real data, and from there the rest of the pipeline treats them like any other footway.
And for the explained code see: [GSoC] Pedestrian area routing: Build area polygons and generate medial axis.
Design decisions
During the course of the project we had to do some serious thinking about some complex obstacles that I’ll explain further in this document. In addition, there are some other design decisions we made, to keep this feature robust:
- Areas below a size threshold keep their perimeter instead of having a generated traversal
- Areas that already have paths mapped inside are left untouched
- Nearby entrances that can “see” each other are merged
- The densification tolerance was tuned as a trade-off between speed and detail.
Results
Current state
We achieved having it merged and running on the full-planet build. It covers most of the pedestrian areas in the world and sits behind the mjolnir.pedestrian_areas config option, so it doesn’t affect anyone who doesn’t enable it.
Full-planet build statistics
These are real numbers from a full planet build, not estimates:
| Metric |
Value |
| Pedestrian areas processed |
127,612 |
| Virtual (synthetic) edges generated |
915,742 |
| Area parsing time |
~2 min |
| Area building time |
~9 min |
| Tile size impact |
negligible |
This is one of the things I’m most proud of, we achieved to have a first functional version with considerably good performance across the whole world, with a more than expected great result.
The first version took about 114 seconds to process Germany’s areas. Profiling with samply showed that the Voronoi computation was dominating everything else, so I focused on that part, preparing the polygon geometry once, collecting the lookup data in two passes, and feeding the Voronoi fewer points. That brought Germany’s processing time down to about 19 seconds, a ~83% reduction.
See it in action
The feature is now live on the public server, so you can try it yourself right now with no setup needed.
Valhalla powers one of the pedestrian routing engines available directly on openstreetmap.org, and it’s also on the Valhalla demo.
On either one, pick the pedestrian (foot) profile, drop a start and an end point on opposite sides of any square or plaza, and you’ll see the route go straight across the open area instead of tracing the edges of the area. It works anywhere in the world where the area is mapped in OpenStreetMap.
If you test it and find a bug, please take a minute to report it on Valhalla’s github: Valhalla Issues
The code
All the work is linked below.
Pull requests
- Main PR - pedestrian area traversal generation: #6195
the core of the project.
- Groundwork PR - optional area handling, and first parsing steps: #6127
- Documentation PR: #6266
- Future work / limitations documentation PR: #6279
Documentation
Commit history
- Last GSoC commit: 5b4d423 anything after this is post-GSoC work.
Challenges and what I learned
The hardest part of this project wasn’t writting the code, it was figuring out what to build. For weeks, before any real implementation, the work was research, prototyping and case studies, because the naive approaches don’t survive contact with real OpenStreetMap data.
-
Choosing an algorithm: My first thought was a Visibility Graph. A Visibility Graph connects each pair of vertex of the polygon that “see” each other in a straight line. But after a case study in QGIS over 10 different real squares comparing approaches, the result was pretty interesting, the Visibility Graph generated too many edges and the routes we believed weren’t very friendly. More of this discussion in the case study mentioned above.
-
Generating the skeleton: Generating the medial axis wasn’t calling a simple function. It was a whole pipeline, that led us to a lot of disorganized segments. Converting them into usable chains was a whole graph problem. Each step of the code was thought and designed.
-
Fitting it into the pipeline: Maybe the biggest design challenge. Areas are detected while parsing the ways, but to build their geometry you need the node coordinates, which are not parsed until later. And the generated crossings need to be turned into edges, which happens even later.
So an entirely new phase had to be designed and placed between ParseNodes and ConstructEdges
-
Memory, and making it scale: Throughout the whole process, one of the biggest challenges was constantly thinking about how to make the solution scalable. It was not just about making it work for a small number of areas, but making sure the design would still work efficiently when applied to the entire pedestrian network of a continent.
This meant being mindful of memory usage from the beginning, while also continuously looking for ways to improve performance as the implementation evolved
-
Getting into a large codebase: One of the first challenges was getting familiar with a codebase as large as Valhalla. Before implementing anything, I had to understand how the different components interacted and how data flowed through the pipeline.
A big part of the process was reading existing code and identifying patterns I could reuse, rather than introducing completely new approaches.
Limitations and future work
This is a first functional version. The known limitations are documented as TODOs in the code and in the docs, each with a plan for how it could be addressed.
Limitations
-
Perimeter footways aren’t detected as mapped paths. A pedestrian way that runs exactly along an area’s boundary, or crosses it in a straight line with only two nodes, isn’t recognised as one, since it has no node strictly inside the polygon, so a traversal may be generated over it.
-
Traversals generated from relations are unnamed. The name of an area mapped as a relation lives on the relation, not on its member ways. Since the name is currently taken from a member way, relation areas either inherit a member’s name or end up unnamed.
-
Generated edges use generic attributes. Both traversal ways and re-emitted entrance nodes get a fixed set of pedestrian attributes rather than inheriting the area’s own tags.
-
Only small areas get their perimeter back. When no traversal is generated, the perimeter is only restored for areas skipped for being too small. Areas skipped for other reasons, such as having no entrances, or having paths already mapped inside, are dropped entirely, even though some of them might still want a routable perimeter.
Future work
Each of the limitations above is a natural follow-up. This section outlines how each could be approached, as a starting point for future contributors.
-
Detecting perimeter footways. The current detection relies on finding a node strictly inside the polygon, which misses ways that only touch the boundary. Adding a geometric check on the segments between consecutive perimeter hits, testing whether they run along the boundary or cross the interior, would flag these ways without depending on an interior node.
-
Naming relation-based traversals. The relation name is available at parse time but isn’t carried forward. Storing it alongside the area relation data, and reading it when the traversal is generated, would let areas mapped as relations take the square’s name instead of a member way’s.
-
Inheriting the area’s attributes. Rather than building traversal ways and entrance nodes from scratch, the attributes could be looked up from the source area and the original nodes and merged. The attributes are already on the source ways at that point, so carrying them through is mostly a matter of routing them through to where the synthetic ways are created.
-
Restoring the perimeter more broadly. This one is more open and would need some investigation first: working out in which cases restoring the perimeter is actually desirable (small areas already do it, but areas skipped for other reasons, like having mapped paths inside, might benefit too), how to detect those cases, and then deciding per skipped area whether to give the perimeter back rather than only triggering on the size check.
-
Turn-by-turn instructions for crossings. Since crossings are ordinary footway edges, they produce a sequence of small maneuvers. Tagging the traversal edges with a dedicated flag, or grouping them in the maneuver generation step, would let the router emit a single “cross the square” instruction.
Beyond those, there are a few internal refinements marked in the source or raised during review:
-
Entrance distance tolerance. The tolerance for matching an entrance to its polygon is currently 0.1. This distance should ideally be zero, it would be worth investigating whether it can be tightened to an epsilon, or reworked so an exact value isn’t needed at all.
-
RAII for GEOS pointers. The GEOS geometries are currently created and destroyed by hand. Wrapping them in a RAII type, as done elsewhere in the codebase, would make the cleanup automatic and safer.
-
Unifying the chain-walking logic. The walk used for pruning the branches and the one used for stitching chains are nearly identical, and could be unified.
-
Separating area ways into their own file. Area member ways are currently emitted into the same file as completely processed ways but in an intentionally incomplete state. Keeping them in a separate file would make the two clearly distinct and the pipeline easier to follow.
Acknowledgements
I don’t have enough words to express my gratitude to my mentors, Kevin Kreiser and Christian Beiwinkel were the best mentors I could have ever asked for. I’m extremely thankful for their guidance, patience and for making me feel encouraged and proud of every little step I was making. It’s incredible how much you can learn from people like them, who have been working on Valhalla for such a long time.
A shout-out also goes to Nils Nolde, who wasn’t my mentor but was really kind during the application process and throughout our interactions during the summer.
Also, I have to thank all the Valhalla and OpenStreetMap community, which, through the forum, diary entries, and the Valhalla repository, helped us to find some things we had to rethink or try in a different way.
This has been a life-changing process, it was a pleasure to get to know my mentors and this community. It’s the end of the program, but I’m sure not the last you’ll see of me around Valhalla.
OpenStreetMap Blogs
►
►
►
►
For some, it may mean learning how to create and contribute to OpenStreetMap but it goes beyond putting roads, buildings and places on a map. It is about understanding the value of the data we create, building communities that can sustain themselves, and knowing the opportunities that come with being part of a global mapping network.
