funny u-turn

[emiltin]

    Scenario: Chain of Ways
        Given the nodes
         | a | b | c | d | e |

        And the ways
         | nodes |
         | ab    |
         | bc    |
         | cd    |
         | de    |

        When I route I should get
         | from | to | route       |
         | a    | e  | ab,bc,cd,de |

but actually i get: bc,cd,de,de

{"version": 0.3,"status":0,"status_message": "Found route between points","route_summary": {"total_distance":440,"total_time":85,"start_point":"","end_point":"de"},"route_geometry": "_ibE_ibE?gE?gE?gE?gE??","route_instructions": [["Head","",111,0,210,"0","NE",22.5],["Continue","bc",111,1,210,"1","NE",22.5],["Continue","cd",111,2,210,"2","NE",22.5],["Continue","de",111,3,210,"3","NE",22.5],["U-Turn","de",0,4,210,"4","NE",22.5]],"via_points":[],"transactionId": "OSRM Routing Engine JSON Descriptor (v0.3)"}

notice the last instruction: ["U-Turn","de",0,4,210,"4","NE",22.5]

(also, the first way is empty, but this is noted in a separate issue)

[emiltin]

btw, does coordinate origin matter?
at the moment i'm using 1,1 as the origin (avoiding 0,0). the distance between nodes is 0.001, or about 110m.

[emiltin]

    Given the nodes           # features/step_definitions/test_data.rb:143
      | a |   | c |   | e |
      |   | b |   | d |   |
    And the ways              # features/step_definitions/test_data.rb:158
      | nodes |
      | ab    |
      | bc    |
      | cd    |
      | de    |

going from a to e on this map returns bc,cd,de, curiously with a u-turn as 2. instruction:

{"version": 0.3,"status":0,"status_message": "Found route between points","route_summary": {"total_distance":630,"total_time":120,"start_point":"","end_point":"de"},"route_geometry": "_ibE_ibE??fEgEgEgEfEgEgEgE","route_instructions": [["Head","",0,0,298,"0","NE",22.5],["U-Turn","",157,1,298,"1","NE",22.5],["Turn left","bc",157,2,298,"2","NE",22.5],["Turn right","cd",157,3,298,"3","NE",22.5],["Turn left","de",157,4,298,"4","NE",22.5]],"via_points":[],"transactionId": "OSRM Routing Engine JSON Descriptor (v0.3)"}

[DennisOSRM]

A U-turn occurs when a via point is on a dead-end street. OSRM ossumes that the driver will only turn at the end of the street. This is not always true in reality but a simple way to handle dead-end streets.

[emiltin]

but there's no via points?

[emiltin]

here's an example from running the latest code:

    Scenario: Don't use empty steps or u-turns at start/end of route
        Given the nodes
         | a |   |   |
         | b |   |   |
         | c | d | e |

        And the ways
         | nodes |
         | abc   |
         | cde   |

        When I route I should get
         | from | to | route   |
         | b    | d  | abc,cde |
         | a    | e  | abc,cde |

the first case is ok.
but going from a to e, osrm suggest:

1. start on abc, for 0m
2. do a u-turn for 222m
3. turn left for 222m
4. do a u-turn for 0m

when in fact all that's need would be:

1. head on abc, for 222m
2. turn left for 222m

it seems it's related to start or ending at the end of a dead-end street.

details:

Failed Scenario: Don't use empty steps or u-turns at start/end of route
Time: 2012-02-08T20:02:36Z

<?xml version="1.0" encoding="UTF-8"?>
<osm generator="osrm-test" version="0.6">
  <node id="1" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z" lon="1.0" lat="1.0">
    <tag k="name" v="a"/>
  </node>
  <node id="2" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z" lon="1.0" lat="0.999">
    <tag k="name" v="b"/>
  </node>
  <node id="3" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z" lon="1.0" lat="0.998">
    <tag k="name" v="c"/>
  </node>
  <node id="4" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z" lon="1.001" lat="0.998">
    <tag k="name" v="d"/>
  </node>
  <node id="5" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z" lon="1.002" lat="0.998">
    <tag k="name" v="e"/>
  </node>
  <way id="6" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z">
    <nd ref="1"/>
    <nd ref="2"/>
    <nd ref="3"/>
    <tag k="highway" v="primary"/>
    <tag k="name" v="abc"/>
  </way>
  <way id="7" version="1" uid="1" user="osrm" timestamp="2000-00-00T00:00:00Z">
    <nd ref="3"/>
    <nd ref="4"/>
    <nd ref="5"/>
    <tag k="highway" v="primary"/>
    <tag k="name" v="cde"/>
  </way>
</osm>

[test]
cycleway = 19
trunk = 19
trunk_link = 19
primary = 19
primary_link = 19
secondary = 17
secondary_link = 17
tertiary = 15
residential = 15
unclassified = 15
living_street = 13
service = 12
track = 12
path = 12
footway = 10
pedestrian = 5
pier = 5
steps = 3
ferry = 5
obeyOneways = yes
useRestrictions = yes
accessTag = bicycle
excludeFromGrid = ferry
defaultSpeed = 17
obeyBollards = no

Expected: {"from"=>"a", "to"=>"e", "route"=>"abc,cde"}
Got: {"from"=>"a", "to"=>"e", "route"=>"abc,abc,cde,cde"}
Query: http://localhost:5000/viaroute&start=1.0,1.0&dest=0.998,1.002&output=json&geomformat=cmp
Response: {"version": 0.3,"status":0,"status_message": "Found route between points","route_summary": {"total_distance":440,"total_time":85,"start_point":"abc","end_point":"cde"},"route_geometry": "_ibE_ibE??nK??oK??","route_instructions": [["Start","abc",0,0,210,"0","S",0],["U-Turn","abc",222,1,420,"1","S",180],["Turn left","cde",222,2,420,"2","W",270.02],["U-Turn","cde",0,3,210,"3","S",0]],"via_points":[],"transactionId": "OSRM Routing Engine JSON Descriptor (v0.3)"}
Parsed:
["version", 0.3]
["status", 0]
["status_message", "Found route between points"]
["route_summary", {"total_distance"=>440, "total_time"=>85, "start_point"=>"abc", "end_point"=>"cde"}]
["route_geometry", "_ibE_ibE??nK??oK??"]
["route_instructions", [["Start", "abc", 0, 0, 210, "0", "S", 0], ["U-Turn", "abc", 222, 1, 420, "1", "S", 180], ["Turn left", "cde", 222, 2, 420, "2", "W", 270.02], ["U-Turn", "cde", 0, 3, 210, "3", "S", 0]]]
["via_points", []]
["transactionId", "OSRM Routing Engine JSON Descriptor (v0.3)"]

[DennisOSRM]

This one looks much better, too with the upcoming changeset:

{
    "version": 0.3,
    "status": 0,
    "status_message": "Found route between points",
    "route_summary": {
        "total_distance": 440,
        "total_time": 23,
        "start_point": "abc",
        "end_point": "cde"
    },
    "route_geometry": "wbbE_ibEfE??oK",
    "route_instructions": [
        [
            "Head",
            "abc",
            111,
            0,
            57,
            "111m",
            "S",
            180
        ],
        [
            "Turn left",
            "cde",
            222,
            1,
            113,
            "222m",
            "W",
            270.02
        ]
    ],
    "via_points": [],
    "transactionId": "OSRM Routing Engine JSON Descriptor (v0.3)"
}

[DennisOSRM]

See commit 8cddaf3.