routing across areas

[andrewharvey]

In particular natural=beach for the trekking profile. Routing around the edge of the way is acceptable.

[Phyks]

Would be super useful for routing across squares as well, such as this one https://www.openstreetmap.org/#map=19/48.84147/2.32091 (BRouter takes a huge detour even though riding a bicycle at walking speed is permitted on the square http://brouter.de/brouter-web/#map=18/48.84199/2.32091/OpenStreetMap&lonlats=2.318695,48.841489|2.321465,48.84073).

I know https://makina-corpus.com/blog/metier/2013/moodwalkr-behind-the-scenes and https://makina-corpus.com/blog/metier/2018/calcul-ditineraires-pietons-avec-osrm (in French, "Traversée d'un espace ouvert") which precomputes a visibility graph for such areas and use it in OSRM.

Has anyone other ideas/doc on the way this should be implemented in BRouter?

[nrenner]

Some links I collected on the topic:

• How to Cross Open Spaces? (poster)
• Integrating Open Spaces into OSM Routing Graphs for Realistic Crossin… (slides)
• Integrating Open Spaces into OpenStreetMap Routing Graphs for Realistic Crossing Behaviour in Pedestrian Navigation
• User:Maxbe/Routen über Flächen – OpenStreetMap Wiki (de)

[poutnikl]

I guess a small area should be transformed internally to a node, a larger one possibly to a ring of short ways along its circumference.

[Phyks]

Thanks @nrenner for the docs! Looking at the links, it seems the approach from https://makina-corpus.com/blog/metier/2013/moodwalkr-behind-the-scenes should work quite well for a first version.

This basically boils down to computing the visibility graph as

and comes with the nice feature that the resulting ways can probably be added to the current BRouter routing without any extra work, therefore only requiring pre-processing / mapcreator changes

The downside is that the resulting routes are not very realistic, but this is probably not a big deal as

1. It will let BRouter at least cross squares and areas.
2. It is good enough for a first version.
3. Not even Google does it well https://www.google.fr/maps/dir/43.6020158,1.4469147/43.6019744,1.4482346/@43.6018933,1.4475484,19.56z/data=!4m2!4m1!3e2 :)

I'll have a look at the visibility graph computation, see if I can come up with a PoC.

[Phyks]

I've just realized the issue has quite deviated a lot from the initial issue.

In particular natural=beach for the trekking profile. Routing around the edge of the way is acceptable.

Routing around the edge of a surface (closed OSM way) is already implemented, this can be seen for squares in http://brouter.de/brouter-web/#map=19/48.81870/2.31914/standard&lonlats=2.319464,48.818572|2.319746,48.81886|2.319909,48.819143. I think the issue for not being able to route around a polygon with natural=beach (typically https://www.openstreetmap.org/way/169161621#map=17/46.69360/-1.94501) is that they are not included in the segments file (as they don't appear in https://github.com/abrensch/brouter/blob/master/misc/profiles2/lookups.dat).

So there are a few (quite related) issues:

• One should probably add natural=beach (and other such relevant tags) to allow routing around them (as long as this is a single polygon, made from a closed OSM way).
• There is the question of routing across areas (where an area is any polygon / closed OSM way), which can be achieved quite easily by computing the visibility graph of the polygon and adding new edges to the segment files. This would allow a route across the square in http://brouter.de/brouter-web/#map=19/48.81857/2.31943/standard&lonlats=2.319593,48.818601|2.319373,48.819214.
• Finally, one should also add support for the multipolygons (defined as OSM relations with outer and inner boundaries), which would allow routing across complex squares such as http://brouter.de/brouter-web/#map=18/48.84199/2.32091/standard&lonlats=2.318695,48.841489|2.321465,48.84073.

[zossebart]

* There is the question of routing **across** areas (where an area is any polygon / closed OSM way), which can be achieved quite easily by computing the visibility graph

slightly offtopic: if this happens to get implemented, maybe the visibility graph computation could be implemented in a reusable way.
With this, maybe something similar to this could be implemented later: http://k1z.blog.uni-heidelberg.de/2018/11/07/generating-customized-pleasant-pedestrian-routes-based-on-openstreetmap-data/
Especially the "greenness" sounds interesting and is also implemented using a visibility graph.

Maybe I should start a separate issue/thread regarding this, though...

[Phyks]

I could chat about the visibility graph approach with people working with it at the SOTM at Heidelberg (https://media.ccc.de/v/sotm2019-1359-pedestrian-routing-in-complex-areas-the-case-of-paris-railway-stations) and it seems quite tricky to have it working well actually. The main issue being that computing the visibility graph can be very power consuming, especially when you get a lot of nodes in your surface. With a naive algorithm (complexity O(n³)), it takes them about 20 minutes to ingest a small area around Gare de l'Est in Paris https://www.openstreetmap.org/#map=17/48.87781/2.35990 (with many surfaces with a few hundreds or thousands points).

There seems to be more refined algorithms with lower complexity (http://cs.smith.edu/~istreinu/Teaching/Courses/274/Spring98/Projects/Philip/fp/visibility.htm) but the complexity and implications of the area routing should probably be carefully investigated before starting to work on this.

[codemewell]

Maybe this will be helpful. Here's working example: https://turfjs.org/docs/#shortestPath

It uses A* algorithm. Has obstacles input. Matrix resolution.

No idea which approach from mentioned above is this based on. But if it works in popular library maybe is worth considering?

[nrenner]

There also was this talk at SotM:
Client-side route planning: preprocessing the OpenStreetMap road network for Routable Tiles.

They implement a visibility graph and then reduce the number of paths to those actually taken by the router (and use it as an example where it would make sense to share the results of such expensive preprocessings): video (5:17-), slides (10,11).