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). Cheers, Patrick On Sat, Jun 4, 2016 at 10:20 PM, Richard Fairhurst <[email protected]> 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 > [email protected] > https://lists.openstreetmap.org/listinfo/osrm-talk _______________________________________________ OSRM-talk mailing list [email protected] https://lists.openstreetmap.org/listinfo/osrm-talk
