Route through squares (area=yes)

[emiltin]

handling square might not be trivial, and are probably mostly important for pedestrian routing. so this might be for a future version.

the thing with a square is that you can cross it in any way. unfortunately squares can have odd shapes, so it's not always possible go in a straight line from where you enter to where you leave. for example a building might be in the way if the square has a hour-glass shape.

a simple example is "Prins Jørgens Gård" is a square, tagged with highway=pedestrian, area=yes: http://www.openstreetmap.org/?lat=55.676763&lon=12.579427&zoom=18&layers=M

if i set up a pedestrain speedprofile, which includes 'pedestrian=5', osrm will route at the edge of the square. this is will get me across the square, but in a somewhat odd fashion.

one option would be to add routes connecting all entries to the square to all others. another would be to connect all entries to a central point. perhaps these to options could be improved by checking that routes are only added if they don't cross the square boundary.

a third option would be be still route along the edge of the square, but insert the route some reasonably distance from the edge, since in reality you cant walk right at the edge of the building.

[emiltin]

another idea for handling areas: find all nodes along the edge that is also part of a way with a highway=* tag, or another area. then divide this polygon using standard subdidivision algorithms. this might provide a good balance between not adding too many lines, while still providing significant a pretty good route across any type of square.

[emiltin]

how OTP solved it: http://blog.openplans.org/2012/06/b-roll-david-solves-the-plaza-problem-with-help-from-de-berg-and-matt-conway/

[DennisOSRM]

Yes, very standard modelling.

[TheMarex]

Brain dump on how to do this:

• This requires that we have all node locations available when processing a way
• Add area flag to ExtractionWay
• In ExtractorCallbacks::ProcessWay compute the visibility graph of the polygon (naive algorithm):
  • For each pair of boundary vertices check if they can be connected without intersecting the boundary
  • Add edge for pair if intersection free

AFAIK there is an algorithm in deBerg that routes through cell centers, but I would need to look this up.

[lbud]

this would also be awesome for, say, indoor routing :)

[danpat]

Example indoor routing use-case: http://en.wikipedia.org/wiki/Edmonton_Pedway

Some of the walkways are in OSM, but it doesn't look complete: https://www.openstreetmap.org/#map=17/53.54259/-113.49257

[homersimpsons]

Is it possible, in preprocessing operation, to create ways in those area?

[daniel-j-h]

Yes, you could do the pre-processing already on the OSM extract adding artificial ways and saving out the extract again. OSRM will then happily route you over those ways when appropriate.

Have a look at https://github.com/osmcode/libosmium if you want to give it a try.

[daniel-j-h]

Let's be more concrete here. What needs to be done is the following.

• Filter area=yes + highway=pedestrian ways. In addition access tags need to be respected as well. Open question: are there other tags / combinations we have to take care of? Sample OSM!
• Handle simple areas (no multipolygones) at first / at all. Osmium's Area type - the area() handler callback is getting called with - has a is_multipolygon() check.
• Compute visibility graph. Simple solution as outlined above is good enough for a first pass. We can make it fancy afterwards. Care needs to be taken not to blow up the already huge walk graph. Gather some statistics for the planet how many areas there are and how many support nodes they have min. / max. / avg. to get a feeling for the data out there.

We could do it either as a pre-processing step as noted above. Implementing it internally has the benefit of us being able to tell artificial ways we introduce apart from original OSM data.

Additional work could then propagate a flag through the pipeline allowing us to "fix" guidance by introducing "cross the area" instructions.

Internally we would need to classify areas based on the raw OSM objects here and create a new ExtractorCallbacks::ProcessArea callback taking a area and inserting artificial ways (marked as such).

Ref. refactoring the extraction callbacks for proper libosmium usage: https://github.com/Project-OSRM/osrm-backend/issues/3447

cc @PedaB @joto

[joto]

@daniel-j-h Why no multipolygons? Are they more difficult to handle?

[daniel-j-h]

Yes, at least the simple approach won't do for multipolygons. Have a look at these examples in the context of area routing via creating artificial ways.

[joto]

@daniel-j-h Note that the osmium::Area::is_multipolygon() call will only check whether the area has more than one outer ring. What you seem to be interested in is that it doesn't have any inner rings. You'd have to call num_rings() for that.

[emiltin]

regarding tag combinations, we should reuse as much of the usual way processing as possible, to handle tags like access, foot, bicycle, car, surface, smoothness, construction, impassable, status, amenity, platform, railway, service, steps, etc.

tags related to direction will not apply to squares, like oneway, :forward and :backward and should be ignored (and would be invalid tagging anyways). same with tags related to lanes and width.

turn restrictions to/from a square probably doesn't apply either.

[sfkeller]

What is the reason that this issue about pedestrian routing through areas has such low priority?

I'm asking because mappers obviously continue to add "virtual" ways over areas in OSM. This is unncessary and like "tagging for the router". In addition it looks weird in renderers, because such pedestrian ways can't be distinguished from "real" ones without guessing...

[daniel-j-h]

Mainly two reasons

1. in the last two years the core dev team heavily focused on car navigation; and @emiltin is working on all things bike routing for his own use-case
2. no one stepped up and wanted to implement it; if you have a use-case for this and see a need here we're more than happy to guide you along.

[emiltin]

This is highly relevant for bicycle routing as well (which is why I opened the issue originally), since:

1) you're allowed to bicycle on some areas 2) you can push your bike on most areas where you're allowed to walk

But unfortunately I don't have time to implement it.

[systemed]

FWIW, it's not "tagging for the renderer/router". That means putting incorrect information in to achieve the desired effect: for example, tagging a golf course bunker as a beach so it shows up as sand, even though it's not a beach. Adding centrelines or virtual ways is perhaps duplicate information, but it's been done since the very earliest days of OSM (on rivers).

[andrewharvey]

Open question: are there other tags / combinations we have to take care of? Sample OSM!

natural=beach for the walking profile. Beaches don't normally have a path going through them but you can walk along them.

[sfkeller]

@systemed: I'm talking about not-existing and misleading (sic!) footways which have been added only to enhance a router, like on this place "Helvetiaplatz, Zurich" (http://www.openstreetmap.org/way/4533221 ). There you also see that these unnecessary footways are only partially working since the route from east to west side is missing...

[saerdnaer]

if you have a use-case for this and see a need here we're more than happy to guide you along.

@daniel-j-h Can you give some pointers how to start implementing this issue? Which classes have to be modified? (besides https://github.com/Project-OSRM/osrm-backend/issues/64#issuecomment-289463048 )

[daniel-j-h]

If you give the ExtractionWay here a new property maybe is_area and expose it to the profiles through the scripting environment here you can parse a way's area tag in the Lua profiles and set the attribute accordingly.

You probably also want to expose is_closed on the osmium::Way in the scripting environment here because you only care for closed ways (=> areas).

Once you have the attribute on the ExtractionWay and inside C++-land you can modify the ExtractorCallbacks here to compute e.g. the visibility graph and add edges.

Hope that helps