Bad route returned in polyline

[sweenzor]

If I route between the following two points in Los Angeles:

34.0317544005, -118.421863315
34.0321907422, -118.422235594

I get the following: curl "http://127.0.0.1:5020/viaroute?loc=34.0317544005,-118.421863315&loc=34.0321907422,-118.422235594&z=16" {"version": 0.3,"status":0,"status_message": "Found route between points","route_geometry": "myunErgxqUs@f@RIw@j@","route_instructions": [["10","Westwood Boulevard",83,0,3,"83m","NW",327],["15","",0,3,0,"","N",0.0]],"route_summary":{"total_distance":83,"total_time":8,"start_point":"Westwood Boulevard","end_point":"Westwood Boulevard"},"alternative_geometries": [],"alternative_instructions":[],"alternative_summaries":[],"route_name":["","Westwood Boulevard"],"alternative_names":[["",""]],"via_points":[[34.03175,-118.42186 ],[34.03219,-118.42223 ]],"hint_data": {"checksum":160465680, "locations": ["lFcoAEzmAAAfAAAAiAAAAOrmB1fzQsg_p-0zAHZNS_9", "QtYcAEzmAAAgAAAAlAAAAJz-SdrHIcc_0-0zAFFNS_9"]},"transactionId": "OSRM Routing Engine JSON Descriptor (v0.3)"}

Including this polyline:

myunErgxqUs@f@RIw@j@

But if I plot the polyline, I get this:

:cry:

tested at dc86007fa9cb0e9c4fa8004308ca55551a03b9e7 and d89be86e4f28f02264b8bc6a6564b9c69b84bc24

[DennisOSRM]

Not replicable. Seems to be broken input data. http://osrm.at/1FM

[sweenzor]

Interesting. I'll try some further debug.

@DennisOSRM, what ref is map.project-osrm.org running? and what ref was used to generate the hierarchy?

[sweenzor]

ah ha!

when I generate the hierarchy from 58dfd29a3a33170d1a533ed5efd8afb4f3155128 (an arbitrarily old commit message) I get the correct polyline: myunErgxqUwAhA

when I use the current ref, d89be86e4f28f02264b8bc6a6564b9c69b84bc24, I get the problematic polyline: myunErgxqUs@f@RIw@j@

I'll git-bisect and see if I can find the commit which changed the behavior

[sweenzor]

ok, finished the bisect:

b16db9fe68a8322f1d09be67b5a5eb1dcf991619 is the first bad commit
commit b16db9fe68a8322f1d09be67b5a5eb1dcf991619
Author: DennisOSRM <luxen@kit.edu>
Date:   Wed Sep 19 11:16:45 2012 +0200

    Replacing old style casts and unsafe float comparison

:040000 040000 76ee15376f1de70e67b5d63567ffb934d3556d94 6514ca667d4bca197f2167857d727593194117a3 M      Algorithms

if I build the hierarchy with anything before b16db9fe68a8322f1d09be67b5a5eb1dcf991619, I get:

myunErgxqUwAhA

With anything after b16db9fe68a8322f1d09be67b5a5eb1dcf991619, I get:

myunErgxqUs@f@RIw@j@

Here's the complete git-bisect log:

$ git bisect log
git bisect start
# bad: [d89be86e4f28f02264b8bc6a6564b9c69b84bc24] Fixing typo
git bisect bad d89be86e4f28f02264b8bc6a6564b9c69b84bc24
# good: [58dfd29a3a33170d1a533ed5efd8afb4f3155128] adapt speed profiles to extended access control
git bisect good 58dfd29a3a33170d1a533ed5efd8afb4f3155128
# bad: [2185bb3327462cd6f0b63bdddc37e243f7e9f6e0] Parsing duration of ferries before further computation
git bisect bad 2185bb3327462cd6f0b63bdddc37e243f7e9f6e0
# good: [9e6ac95e4f04ede7127efb56f87f369ab6334591] Output of used CRC32 method more verbose
git bisect good 9e6ac95e4f04ede7127efb56f87f369ab6334591
# bad: [352ee956cddaf1576bcf17e458003ddb8b6ed0fc] Merge pull request #427 from ibikecph/cuke_uturn
git bisect bad 352ee956cddaf1576bcf17e458003ddb8b6ed0fc
# bad: [1c415933dac772b9e20e5cf6c25b8cf115da5481] Fixing comparison of floats
git bisect bad 1c415933dac772b9e20e5cf6c25b8cf115da5481
# bad: [5423cff7a85e68025a9cd8484aa1814a714258af] Removing old style cast
git bisect bad 5423cff7a85e68025a9cd8484aa1814a714258af
# good: [a8a0d1b216bacaea80feb6b4a6de38ce05a99b38] Removing superflous line
git bisect good a8a0d1b216bacaea80feb6b4a6de38ce05a99b38
# bad: [b16db9fe68a8322f1d09be67b5a5eb1dcf991619] Replacing old style casts and unsafe float comparison
git bisect bad b16db9fe68a8322f1d09be67b5a5eb1dcf991619
# good: [2faf9ad1b641fd3d9157580afee4555a91f31cda] Proper initialization of shared_ptr by boost::make_shared
git bisect good 2faf9ad1b641fd3d9157580afee4555a91f31cda

[DennisOSRM]

On 08.11.2012 22:27, Matt Sweeney wrote:

ah ha!

when I generate the hierarchy from 58dfd29 https://github.com/DennisOSRM/Project-OSRM/commit/58dfd29a3a33170d1a533ed5efd8afb4f3155128 (an arbitrarily old commit message) I get the correct polyline: |myunErgxqUwAhA|

when I use the current ref, d89be86 https://github.com/DennisOSRM/Project-OSRM/commit/d89be86e4f28f02264b8bc6a6564b9c69b84bc24, I get the problematic polyline: |myunErgxqUs@f@RIw@j@|

— Reply to this email directly or view it on GitHub https://github.com/DennisOSRM/Project-OSRM/issues/498#issuecomment-10205611.

map.project-osrm is built with latest master branch.

[karme]

Matt Sweeney notifications@github.com writes:

ok, finished the bisect:

do you always use a complete rebuild and use the same version for preprocessing and testing?

[DennisOSRM]

On 09.11.2012 11:13, karme wrote:

Matt Sweeney notifications@github.com writes:

ok, finished the bisect:

do you always use a complete rebuild and use the same version for preprocessing and testing?

— Reply to this email directly or view it on GitHub https://github.com/DennisOSRM/Project-OSRM/issues/498#issuecomment-10221182.

The latest and greatest version from master branch is used as the develop branch may or may not be stable.

[sweenzor]

@karme, yes. At each point in the bisect, I recompiled (with scons) and rebuilt the hierarchy.

@DennisOSRM if I build the hierarchy with the latest commit on master, I see this error

[DennisOSRM]

On 09.11.2012 19:44, Matt Sweeney wrote:

@karme https://github.com/karme, yes. At each point in the bisect, I recompiled (with |scons|) and rebuilt the hierarchy.

@DennisOSRM https://github.com/DennisOSRM if I build the hierarchy with the latest commit on master, I see this error

— Reply to this email directly or view it on GitHub https://github.com/DennisOSRM/Project-OSRM/issues/498#issuecomment-10239947.

Just to be sure. Is your input data ok?

[sweenzor]

I'm using the metro extract for LA, in pbf form:

http://metro.teczno.com/#los-angeles http://osm-metro-extracts.s3.amazonaws.com/los-angeles.osm.pbf

If there's another source of input data I should try, I'd be happy to test that also!

[sweenzor]

Has anyone else be able to reproduce?

@DennisOSRM would you be willing to re-open this issue?

[emiltin]

i havent tried to reproduce it yet. it would be nice to add some tests for the polyline stuff. did you find other examples of weird polylines?

[emiltin]

i get the same (weird) polyline, running a pretty new version of the develop branch:

~/code/Project-OSRM/sandbox$ (develop) git log -n 1
commit 7493d8aa49b56c396f12704e737492c6b793aaa0
Author: Emil Tin <emil@tin.dk>
Date:   Sun Nov 4 14:00:21 2012 +0100

    test ferry duration on part of route

~/code/Project-OSRM/sandbox$ (develop) curl "http://localhost:5000/viaroute?loc=34.0317544,-118.421863&loc=34.0321907,-118.422235&z=16&alt=false&instructions=false"

{"version": 0.3,"status":0,"status_message": "Found route between points","route_geometry": "myunErgxqUs@f@RIw@j@","route_instructions": [],"route_summary":{"total_distance":83,"total_time":8,"start_point":"Westwood Boulevard","end_point":"Westwood Boulevard"},"alternative_geometries": [],"alternative_instructions":[],"alternative_summaries":[],"route_name":["",""],"alternative_names":[["",""]],"via_points":[[34.03175,-118.42186 ],[34.03219,-118.42223 ]],"hint_data": {"checksum":1317240711, "locations": ["lFcoAEzmAAAfAAAAiAAAAOrmB1fzQsg_p-0zAHZNS_9", "QtYcAEzmAAAgAAAAlAAAAJz-SdrHIcc_0-0zAFFNS_8"]},"transactionId": "OSRM Routing Engine JSON Descriptor (v0.3)"}

i also see the same visual zig-zag result. dragging the markers around shows the zip-zag most of the time, when passing the specific way section, but not always.

i don't see anything wrong with the data when looking with potlatch2 at osm.org.

[emiltin]

the above was using the same data file http://osm-metro-extracts.s3.amazonaws.com/los-angeles.osm.pbf

[DennisOSRM]

I looked at the raw data. It is broken.

[mck-]

Just to confirm that this was just an error on the open street map, and nothing to do with OSRM? Despite @sweenzor saying that it depends on what build he was using?

I just encountered a similar polyline recently...

[sweenzor]

Arg.. I don't remember what the resolution was, but I'm betting (judging by my lack of further comments) that Dennis was correct

[DennisOSRM]

It was indeed data.