Area routing in Valhalla: comparing algorithms to cross open spaces

Hi again!

In my previous diary entry I introduced myself and my GSoC project with Valhalla, and I mentioned we were still putting the finishing touches on the exact main goal. Now we have it! We’re focusing on area routing. This is basically means making the router cross open pedestrian areas (like squares) instead of walking around them and generating weird and inefficient routes. This diary entry is a deep dive into the research I’ve done while exploring the different options.

The problem with pedestrian areas

When you ask a router to go across a square, you would expect it to cross it like any person would. But a lot of routers don’t do that, they may send you around the perimeter or go along the streets surrounding the square. The problem here is that the open area has no “ways” inside of it to travel on.

Let’s see one example (using Valhalla) on Plaza Santo Domingo in Murcia (my hometown!):

The path we’re seeing is clearly not the one we’d take if we were walking down the square. The difference between going straight and going around is ~100 meters vs ~370 meters. There is quite a big gap between them, and this isn’t even the worst square!

Why it happens

In OSM, a pedestrian square is typically mapped as highway=pedestrian and area=yes. But this just defines the shape of the surface, there’s nothing inside it for the router to walk along.

Some mappers solve this manually by drawing “virtual footways” across the area, along paths that the people actually walk. An example can be Josefsplatz in Vienna which has some of these crossings ways drawn. It works, but it doesn’t scale (someone has to draw and maintain them everywhere).

What we want instead is to let the router generate those footways automatically from the area’s geometry. That is area routing.

The case study

Of course, before start to write any code, my mentors and I agreed the best way was to understand the geometry visually. So I started taking real squares from OSM and comparing several approaches for generating crossing edges. To do this I started using QGIS (I’m very thankful that Nils taught me how to use it!)

There are a lot of different approaches for this like straight skeleton or grid sampling, but I focused mainly on the two that seemed more interesting for our case. The visibility graph and medial axis (each one with a couple of variations) :

• Visibility graph (VG): Connect every pair of polygon vertices that can “see” each other.
• Reduced VG: Visibility graph generates too many edges, one solution to this is to keep only the edges that lie on the shortest paths between entrances of the square.
• Medial axis: the “skeleton” of the shape, the set of points that are equally distant from the two nearest edges.
• Pruned medial axis: Is the medial axis with its small dangling branches removed, plus connect it to the entrances.

VG:

Reduced VG:

Medial axis:

Pruned medial axis:

I tested this on several squares with different shapes, like Stephansplatz Vienna, Rockefeller Plaza NY, Puerta del sol Madrid Spain and a few more…

I would show all of them but it will be a bit long and boring! But I can tell you about the results.

Results

First of all, talking about the number of edges each one generates, we can see the VG generates more than 5k edges in some cases, way too many to insert them into a routing graph. But with the reduced VG we manage to stay at ~50 edges even in big squares since it depends more on the number of entrances than on the size.

On the other hand, medial axis each version also stays at a very low number of edges. The medial axis may not be the most direct, but it produces very natural and human routes.

So between reduced VG and pruned medial axis, we can say that medial axis is simpler and has the same efficiency in most of squares except the bigger ones but even in these ones, the result of the medial axis is extremely good. And after all this thinking we decided to go with the medial axis (with pruning).

Another thing I’ve discovered while testing all of this, is that we have to be a bit selective and “play safe” with the squares we are dealing with, because OSM data is huge and we can not make sure every square is perfectly tagged/mapped.

We’ve also discussed a few design rules as, entrance detection, size threshold of very small areas and how to deal with a few more cases.

What’s next

Now that we have a better view we can start with the implementation in Valhalla! I’ve enjoyed a lot learning QGIS and watching how these algorithms would work for each square, it’s been actually fun!

If you know any especially weird or interesting squares (whether is good or badly mapped) I’d love to hear about them, more test cases are always welcome. Or maybe some ideas that pop into your mind while reading this, everything helps!

As always, huge thanks to Kevin, Chris and Nils for all the guidance and of course for being so understanding and friendly. You can follow the progress in my PRs to Valhalla and here in my diary.

More soon, bye!