search

abrensch / brouter

configurable OSM offline router with elevation awareness, Java + Android
MIT License
473 stars 113 forks source link

routing across areas #108

Open andrewharvey opened 5 years ago

andrewharvey commented 5 years ago

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

Phyks commented 5 years ago

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 commented 5 years ago

Some links I collected on the topic:

poutnikl commented 5 years ago

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 commented 5 years ago

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

Visibility graph

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

Resulting route

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 commented 5 years ago

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:

zossebart commented 5 years ago 
* 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 commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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).