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

Patrick Niklaus patrick.niklaus at student.kit.edu
Sat Jun 4 23:27:12 UTC 2016

I'm assuming your goal for 1. is not to actually speed up the route
query by reducing the number of via points, but rather just to reduce
them for storage/usability?

My solution for that would remove vias if the way through them is a
shortest (duration) path. Technically shortest paths are not unique
(think of grid cities). So this might lead to some route modifications
that don't change the duration of the route but maybe the actual path.

The way to implement this would be by doing a table query with the
vias and removing via j from (i, j, k) if result.durations[i][j] +
result.durations[j][k] == result.durations[i][k].

For 2. the implementation would be pretty straight forward. Using the
match plugin first obtain snapped via coordinates of the trace. Then
apply 1. to minimize the via points.
Another option would be to simply run Douglas Peucker on the trace
first before feeding it into match. We have used this successfully on
trace data (then again this depends on the traces being rather dense).


On Sat, Jun 4, 2016 at 10:20 PM, Richard Fairhurst <richard at systemed.net> wrote:
> 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
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

More information about the OSRM-talk mailing list