trace_route fails on some routes depending on specific pairs of coordinates.

[DigNZ]

A call to trace_route with the following payload succeeds:

{"costing":"auto", "encoded_polyline":"z{aymAshfjlI}c@oH"}

However with the following payload the request fails: {"costing":"auto", "encoded_polyline":"z{aymAshfjlIib@|@"}

With the following error: { "error_code": 299, "error": "Unknown:Could not build directions for TripLeg", "status_code": 400, "status": "Bad Request" }

Note that in the request that fails any request including those two points (even if those two points are not adjacent) will fail. In my real life example the two points were separated with ~360 other points and the second point was on the return journey however the include of both points in the same request is enough to trigger that error.

/trace_attributes with the same payloads will return 200 OK for both requests but will return an empty array for edges with the second payload.

This occurs both on my locally hosted valhalla with data built from OSM as well as on valhalla1.openstreetmap.de I've finding over 40% of real life traces that I'm using have this issue traced from telematics devices installed in cars - this is just one specific example that I narrowed down to the specific coordinates that caused the problem.

[kevinkreiser]

Thank you for narrowing this down, we should be able to debug this pretty quickly now!

[kevinkreiser]

so far i couldnt reproduce it with older data, im downloading the latest geofabrik new zealand extract and making data out of that to see if the latest data reproduces it

[kevinkreiser]

cool, that reproduced it. ill take a deeper look

[kevinkreiser]

ok yeah, so basically what is happening is that the algorithm, when the shape is closer will try to do a cheaper map matching algorithm we call "edge_walk". as a quick fix on your end you can disable this by setting shape_match to map_snap this will do a full map matching rather than the more efficient but less robust algorithm. in the mean time ill figure out why this algorithm isnt working properly in this case

[kevinkreiser]

ok so, before this change: https://github.com/valhalla/valhalla/pull/2712/files#diff-9f54e917f7664c4a402d31eaedf0bc814ec15dc67109945c2af6454a9e232db0L166-L167

we used to pass options.locations() to triplegbuilder::build because that thing expects loki edge candidates matching the edges in the path to be there. the thing is, up in loki where we fill those in, they are indeed on the locations field of options not the shape field. so the next question is, how does edge_walk ever work at all? looking th rough the code i cant find an instance where we actually put the edge candiates on the shape field except when it falls through and does map_snap instead... so i should debug a bit further but i guess what ill find is that the map_snap algorithm fails this case as well, perhaps for the reason @dnesbitt61 over in #3230. at any rate ill see if i can fix up the edge walk algorithm. and move on from there..

[DigNZ]

Interesting. Yes map_snap is slower but does work, so I"ll use that for now and await a fix. Thanks for looking into this.

[git-bone]

hi Kevin, is there any progress on this issue? I'm experiencing the same, especially when there are overlapping trackpoints. I'm working with latest master branch.

[nilsnolde]

Nope, you'd see a PR linked or further comments if there was any progress

[git-bone]

no worries, the workaround mentioned above works fine, it probably just takes a bit more time to calculate the route.