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

[Richard Fairhurst]

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