Routing in polygon layers? Yes we can!
A few weeks ago, the city of Vienna released a great dataset: the so-called “Flächen-Mehrzweckkarte” (FMZK) is a polygon vector layer with an amazing level of detail which contains roads, buildings, sidewalk, parking lots and much more detail:
Now, of course we can use this dataset to create gorgeous maps but wouldn’t it be great to use it for analysis? One thing that has been bugging me for a while is routing for pedestrians and how it’s still pretty bad in many situations. For example, if I’d be looking for a route from the northern to the southern side of the square in the previous screenshot, the suggestions would look something like this:
… Great! Google wants me to walk around it …
… Openstreetmap too – but on the other side :P
Wouldn’t it be nice if we could just cross the square? There’s no reason not to. The routing graphs of OSM and Google just don’t contain a connection. Polygon datasets like the FMZK could be a solution to the issue of routing pedestrians over squares. Here’s my first attempt using GRASS r.walk:
… The route crosses the square – like any sane pedestrian would.
The key steps are:
- Assigning pedestrian costs to different polygon classes
- Rasterizing the polygons
- Computing a cost raster for moving using r.walk
- Computing the route using r.drain
I’ve been using GRASS 7 for this example. GRASS 7 is not yet compatible with QGIS but it would certainly be great to have access to this functionality from within QGIS. You can help make this happen by supporting the crowdfunding initiative for the GRASS plugin update.
I was using cost distance raster analysis to do accessibility modeling (generating walksheds using cost distance surfaces), but abandoned it due to the over generalization of connected routes when converting to raster and losing a lot of real connectivity.
I still see value in this, however, particularly for ‘routing’ people through open spaces, parks, fields, etc. when doing park accessibility mapping.
Is this still ‘routing’, though? Or simply cost path analysis?
I guess it’s “finding a route using cost path analysis”. In my experiments so far, the problem tends to be too much connectivity: some of the walls in the dataset are too thin to get included in the 40×40 cm raster. Do you have some of your work online?
Hey Anita sorry I couldn’t turn ‘notify when new comment appears’…
Anyway, we’re likely launching a new version of our accessibility app this summer… I will share when we’ve launched!
I’m no GIS expert and don’t know what other packages are there but it impresses me as inefficient that rasters are used to implement routing through polygons or through empty spaces. I wonder if there’s a better routing package, if not one should be implemented. All that is be needed is adding the convex vertices of polygons to the routing graph and adding edges between those that can “see” each other without an obstacle in the way. Calculating the costs will require splitting these edges as they cross edges of polygons of different surfaces (pavement vs. grass) but it can omitted at first for routing over one surface type only.
There will be some implementation details like creating nodes at where a linear path (e.g. footway) enters a polygonal one (a square). The start and the end node of the route will need to be added to the graph at runtime but the rest of the graph is still precalculated.
Currently, this functionality is not part of the default GIS routing toolboxes. On Twitter, @timetabling pointed me to https://github.com/graphhopper/graphhopper/issues/82 and @gicycle_ mentioned http://gispoint.de/gisopen-paper/1206-optimierte-wegefindung-fuer-fussgaenger-basierend-auf-vorhandenen-openstreetmap-daten.html (German).
Hello Anita, thanks for the interesting post on routing. I am currently also learning about GRASS and the module r.walk, trying to implement it for hiking people that need to avoid obstacles in the mountains like lakes, precipices, etc. Would you be able to send me your step to step workflow in GRASS for the above example, so I can have a better idea how you assigned different costs to the polygon classes.
Thank you very much!
Hi Henk, I used QGIS Field Calculator first to add a column with costs depending on the polygon type. Only then did I import the vector layer into GRASS and rasterized it based on the cost attribute.
Thank you for your kind reply!
I came here hoping for a step-by-step guide to processing an r.walk command (and stayed for the interesting post). I’m using QGIS 2.10, which does have the Grass plugin functionality you mention as a future prospect – but I’m having trouble setting an appropriate output raster, as the program keeps telling me that the output region does not match the input. I’m not sure if this step applies to the Grass system as well – do you have any insight on how to resolve this?
Hi, Please use http://gis.stackexchange.com for support questions and include information about the steps and settings you have used so far. Screenshots are helpful as well.