{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicpj6qol6iowu3ksbkc3sslsuoayh5zbigdohakjvlgzecf2jrcbe",
    "uri": "at://did:plc:4tuge3k3comfj4nfvqnwkemn/app.bsky.feed.post/3moa2yqnf25o2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiesiegcxiqvnsrin23lolavysyoxove6rerruiut4d4y43lkeh6sq"
    },
    "mimeType": "image/png",
    "size": 90395
  },
  "path": "/user/Paco%20Albacete%20Chicano/diary/408878",
  "publishedAt": "2026-06-13T17:08:09.000Z",
  "site": "https://www.openstreetmap.org",
  "tags": [
    "previous diary entry",
    "Josefsplatz in Vienna"
  ],
  "textContent": "Hi again!\n\nIn 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.\n\n### The problem with pedestrian areas\n\nWhen 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.\n\nLet’s see one example (using Valhalla) on Plaza Santo Domingo in Murcia (my hometown!):\n\nThe 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!\n\n### Why it happens\n\nIn 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.\n\nSome 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).\n\nWhat we want instead is to let the router generate those footways automatically from the area’s geometry. That is area routing.\n\n### The case study\n\nOf 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!)\n\nThere 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) :\n\n  * Visibility graph (VG): Connect every pair of polygon vertices that can “see” each other.\n  * 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.\n  * Medial axis: the “skeleton” of the shape, the set of points that are equally distant from the two nearest edges.\n  * Pruned medial axis: Is the medial axis with its small dangling branches removed, plus connect it to the entrances.\n\n\n\nVG:\n\nReduced VG:\n\nMedial axis:\n\nPruned medial axis:\n\nI tested this on several squares with different shapes, like Stephansplatz Vienna, Rockefeller Plaza NY, Puerta del sol Madrid Spain and a few more…\n\nI would show all of them but it will be a bit long and boring! But I can tell you about the results.\n\n### Results\n\nFirst 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.\n\nOn 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.\n\nSo 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).\n\nAnother 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.\n\nWe’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.\n\n### What’s next\n\nNow 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!\n\n> 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!\n\nAs 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.\n\nMore soon, bye!",
  "title": "Area routing in Valhalla: comparing algorithms to cross open spaces"
}