Handling islands

[skinkie]

Some features in OpenStreetMap are not drawn with journey planners in mind. Such as area's where roads stop in the middle of the area, or public transport platforms where steps towards them center in them, but are never connected. Similar platforms of a tram that is located in the middle of the road, but doesn't have any zebra to reach it. In OpenStreetMap in best case there are tagged with highway=crossing, crossing=unmarked.

The first question: should they appear in the graph? The question is how to determine the size of a valid island? If the answer is: we should prune the islands, how would one do so? If we would like to keep islands, can we do anything 'best-effort' to connect them to the rest of the infrastructure? For example infrastructure that is routable within the same context?

[ben-strasser]

Hi,

whether eliminating islands is a good thing depends on the application. I can imagine application where you want to keep them all, such as an OSM data editor. I think the best solution is to not eliminate them in the OSM importer but offer functionality to postprocess the routing graph before feeding it into the routing engine. The postprocessing step can have parameters that control what islands get removed and what not.

I think the postprocessing step should start by computing the strongly connected components and then filter nodes upon some criterion. For example (a) remove all components except the largest (this is what I usually do in my academia code), (b) remove all components who have fewer than X nodes/arcs, or (c) remove all components whose bounding box has an area size below X square meters.

Implementing (a) and (b) is not difficult once you have the strongly connected components. (c) could be very tricky if you want to get the Earth-being-a-sphere stuff right. It starts with the basic question of how to even define a bounding box on a sphere's surface...

In issue #28 I posted some code that computes strongly connected components but currently does not interoperate well with RoutingKit. That code could be a good basis to start.

Best Regards
Ben Strasser