0

Working for a client on a tracking package for delivery vehicles, I've been given an interesting requirement. Over the past several months, we've been collecting telemetry from the vehicles, including lat/lon, speed, heading, and so forth. The client has asked if we can take an arbitrary track (defined here as an ordered set of lat/lon coordinates) and convert it to a series of turn-by-turn instructions that would result in the same route.

I've been fiddling with OSRM and Graphhopper and both are able to pretty easily turn the points into a polyline and return a set of instructions, but the instructions need a serious amount of reduction in order to be useful to a driver -- for example, traveling down a street for half a mile may result in a dozen instructions that just say "continue on _______ street for 200ft" or whatever the interval between the data points happens to be.

Before I just "brute force" the answer by removing all intermediate points where the street name is the same, I am trying to find an existing SDK or library that can do this for me. My concern is that blindly removing points may result in generated directions that take a different path, and in this situation even a slightly different path is unacceptable. At present I'm not even sure what I would call a feature like this, and all I've been able to find when searching are websites that can do this for you, manually, for cyclists and the like.

Edit: Example lat/lon pairs

43.059595, -70.753773
43.060723, -70.753812
43.061808, -70.754822
43.062661, -70.755752
43.063645, -70.756604
43.064411, -70.756960
43.065192, -70.757475
43.065901, -70.757851
43.065858, -70.758326
43.065597, -70.758999
43.065250, -70.759751
43.064888, -70.760860
43.064700, -70.761494
43.065337, -70.761810
43.065988, -70.762088
43.066581, -70.762345
43.067072, -70.762563
43.067376, -70.762701
43.067463, -70.762642
43.067521, -70.762206
43.067651, -70.761632
43.067752, -70.761276
43.067868, -70.760781
43.068027, -70.760444
43.068186, -70.760009
43.068403, -70.759593

Given to /route results in this polyline:

mayeGpaznLaFVwEjEiDzDgE`DqCxAaDxAmCfABfBv@`C|@zCfAzEl@xB}B`AaCv@wBn@aBh@{@XUGOsAYqBOiAWaB[eAc@qAg@uA

From this json result: https://pastebin.com/qLHrxVPu

Which results in many repeated instructions to continue forward on the same road, for example. What I'm looking to create, from existing sets of lat/lon points like that, is a simple set of driving instructions saying "go straight on this road xxx meters, turn left here, turn right there..."

I know I can brute force this, but I'm hoping there's something built in somewhere.

  • This might have been improved in the latest version. Can you give an example where this is the case with GraphHopper? This should be reproducable with graphhopper.com/maps – Karussell Dec 28 '17 at 11:39
  • @Karussell I couldn't format all the information correctly in a comment, so I edited the question to add example coordinates and the output from graphhopper's /route API. I really don't know how I can use that maps link to demonstrate the issue. – alzee Dec 28 '17 at 14:16
  • You can simulate the snapped route with input points (coordinates) and send the resulting link from GraphHopper Maps – Karussell Dec 28 '17 at 16:06
  • Like graphhopper.com/maps/… which produces only a few instructions – Karussell Dec 28 '17 at 16:08
  • Ah, are you using the /route end point or the map matching end point /match? See github.com/graphhopper/map-matching or graphhopper.com/api/1/docs/map-matching – Karussell Dec 28 '17 at 16:09
1

I don't know of a ready-made library to do this with OSRM, but one of the developers outlined an approach in this mailing list posting: https://lists.openstreetmap.org/pipermail/osrm-talk/2016-June/001225.html

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].

I've implemented this successfully and it works well.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.