[OSRM-talk] Eliminating, or reconstructing, via points
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...
More information about the OSRM-talk