[OSRM-talk] Eliminating, or reconstructing, via points

Richard Fairhurst richard at systemeD.net
Sat Jun 4 20:20:27 UTC 2016


Two similar via-points-related questions I'd like to hear people's 
opinions on. I realise that out-of-the-box OSRM might not be able to 
solve these efficiently, but I'd be interested to hear ideas how one 
might build a plugin (or other code) to solve these.


1. Sometimes users of cycle.travel plan routes with a _lot_ of via 
points, e.g. http://cycle.travel/map/journey/19429 . Often, many of 
these via points are unnecessary: for example, the route from 'via 13' 
to 'via 15' would pass through 'via 14' anyway.

I'd like to add an option to eliminate these unnecessary points. I could 
do a fairly naive implementation, repeatedly routing between each pair 
and eliminating those which aren't necessary, but wonder if there's a 
smarter way of doing it.


2. Often people ask for a way to upload routes (e.g. in GPX or KML 
format, perhaps created with another routing website). This would be 
cool if the resulting routes were editable.

In other words, for a given polyline, reconstruct the via points 
necessary for (an approximation of) that polyline.

Strava built something like this the other year: 
https://twitter.com/paulmach/status/668921393656954880 . I can't get it 
to work, but the "divide and conquer" principle I guess is basically 
analogous to Douglas-Peucker: find a route from (start) to (end), find 
the polyline point furthest from the generated route, add a via there, 
and repeat until no points are more than n metres from the route.

Again, I could probably hack a naive implementation together, but wonder 
if there's a smarter way to do it!


Any ideas welcome. These could be fun challenges but I'd just like to 
get some second opinions before embarking on them...

cheers
Richard



More information about the OSRM-talk mailing list