osrm-backend: map matching returns name for the wrong direction

Using the v5.5.4 release, I notice that map matching can map a trace to the wrong direction. Here is a small example that reproduces the problem.

Given the following trace/query, which goes from west to east:

/match/v1/car/-120.147778,34.392861;-120.147695,34.392889?annotations=true&overview=false

and the following OSM:

<osm generator="test" version="0.6">
<node id="1" lon="-120.1467783" lat="34.3932086" version="1" changeset="1" timestamp="2017-01-19T18:37:02Z" />
<node id="2" lon="-120.147782" lat="34.39286" version="1" changeset="1" timestamp="2017-01-19T18:37:02Z" />
<way id="1" version="1" changeset="1" timestamp="2017-01-19T18:37:29Z">
<nd ref="1" />
<nd ref="2" />
<tag k="highway" v="secondary" />
<tag k="oneway" v="yes" />
<tag k="name" v="westbound" />
</way>
<way id="2" version="1" changeset="1" timestamp="2017-01-19T18:37:29Z">
<nd ref="2" />
<nd ref="1" />
<tag k="highway" v="secondary" />
<tag k="oneway" v="yes" />
<tag k="name" v="eastbound" />
</way>
</osm>

the resulting matched name is the wrong direction (westbound)

{"tracepoints":[{"location":[-120.147778,34.392861],"hint":"AAAAAAEAAIAEAAAAUQAAAAEAAAAAAAAAAAAAAAAAAAABAACAvrDW-B3LDAK-sNb4HcsMAgAAAQF_0OeL","matchings_index":0,"waypoint_index":0,"name":"westbound"},{"location":[-120.147695,34.392889],"hint":"AAAAAAEAAIAEAAAASgAAAAgAAAAAAAAAAAAAAAAAAAABAACAEbHW-DnLDAIRsdb4OcsMAgAAAQF_0OeL","matchings_index":0,"waypoint_index":1,"name":"westbound"}],"matchings":[{"distance":8.2,"duration":0.7,"legs":[{"distance":8.2,"steps":[],"duration":0.7,"annotation":{"nodes":[2,1],"datasources":[0],"duration":[7.4],"distance":[8.22993]},"summary":""}],"confidence":0.980289}],"code":"Ok"}

Note that my OSM is such that both ways share the same nodes. I remember seeing this same problem in v4.x and it was fixed in v4.x. But this does not seem to work in v5.x.

I’d like to be upgrade from v4 to v5 and any help would be appreciate. Thanks

About this issue

Original URL
State: closed
Created 7 years ago
Comments: 20 (15 by maintainers)

Most upvoted comments

@sjones94549 The sorting step that it’s holding up on does perform a lexicographical comparison of the names (to determine the sort order). If the strings are long and similar looking, this could be a big source of the slowdown. There are lots of these comparisons done.

The comparison done to sort edges is done here, it looks like you’re triggering the final std::lexicographical_compare test, which is quite expensive (and is avoided when the names the same, which they often are for normal OSM maps):

https://github.com/Project-OSRM/osrm-backend/blob/6e1c4bfecd6d3b993208c13e8b2afe9a1388121e/src/extractor/extraction_containers.cpp#L66

danpat on Feb 9, 2017

As an aside, I ran into two string length thresholds when trying this. First, osmium raises an exception at 1024 characters, and will simply reject any OSM or PBF with longer values when parsing. Second, OSRM silently truncates to ~254 characters (RangeTable limit, I believe). I see #3585 from 2 days ago might bump this up, but ideally it’d also warn when truncating. In any case, I’ll try the new names table and see what happens.

Strings in OSM can only have a maximum length of 256 unicode characters. See https://github.com/Project-OSRM/osrm-backend/issues/2844. The changes to the range table only up the limit from 256 bytes to 256 unicode codepoints.

daniel-j-h on Feb 9, 2017

@sjones94549 hmm, good point. It’ll work for traces that cross the beginning of ways, but yeah, it won’t work for traces that are only on a sub-section of a longer un-broken way.

To do this inside OSRM, I really see two options:

forward-porting https://github.com/Project-OSRM/osrm-backend/pull/2298
or exposing a forward/reverse flag as an annotation, and encoding both the forward/reverse name in your way.

Both of these will require some C++ work to implement.

danpat on Jan 30, 2017