GraphHopper.com | Forum | GitHub | Maps | Blog

Tutorial: how to associate path details with 'legs'


#1

If you have a route with multiple via points the route can be split into so called “legs”, e.g. start-via-end means two legs: start to via and via to end. Currently our API does not expose these legs explicitly but it is still not hard to do.

Work with legs

Assume the following route

To calculate the time for the first leg you add the two time values of the first two instructions before the waypoint 1 and do the same for the second leg with the instructions after waypoint 1. See this example snippet and the calculation for the first leg:

...
"instructions" : [ {
      "distance" : 60.182,
      "heading" : 84.14,
      "sign" : 0,
      "interval" : [ 0, 2 ],
      "text" : "Continue onto Bergmannstraße, K 8",
      "time" : 6018,
      "street_name" : "Bergmannstraße, K 8"
    }, {
      "exit_number" : 3,
      "distance" : 258.643,
      "sign" : 6,
      "exited" : true,
      "turn_angle" : -4.5,
      "interval" : [ 2, 14 ],
      "text" : "At roundabout, take exit 3 onto Ostpreußenstraße, K 9",
      "time" : 21962,
      "street_name" : "Ostpreußenstraße, K 9"
    }, {
      "distance" : 0.0,
      "sign" : 5,
      "last_heading" : 354.8098442127136,
      "interval" : [ 14, 14 ],
      "text" : "Waypoint 1",
      "time" : 0,
      "street_name" : ""
    }
...

The result is 6018+21962=27980 (~28sec), so you have to create a summation result when the sign of the instruction is 5. With our javascript client this would be something like:

if (path.instructions) {
   var sum = 0;
   for (var j = 0; j < path.instructions.length; j++) {
      var instr = path.instructions[j]; 
      sum += instr.time;
      if(instr.sign == 5) {
         instr.time_per_leg = sum;
         sum = 0;
      }
   }
}

Association of legs with path details

The new path details feature lets you handle even more fine grained results than just per leg. With the path details the information is returned per road segment. But how can you associate this information back to the legs? E.g. you want to know the geometry or all street names of one leg?

This can be done with the help of the indices into the points arrays. The points array is a list of coordinates making the shape of the route. So the points for the first legs goes from 0 to the first via point i.e. this would be 14 in the example above. In the JS client the geometry per leg is already calculated for you, see here.

Now how can you associate other path details like the street names to every leg? This is currently a bit tricky and we’ll make this easier at least in our JS client. First you collect the start indices of every leg via the interval array of the instructions entry. Then you create a hash that associates the start index of a leg to the array index of the leg array. And finally you store all street names of one leg into the leg array. In JavaScript this would be something like:

// store the start point index of every leg in an array
var start_points = [];
start_points.push(0);
if(path.instructions)
for (var j = 0; j < path.instructions.length; j++) {
  var instr = path.instructions[j]; 
  if(instr.sign == 5)
     start_points.push(instr.interval[0]);
}

var legs = [];
for(var j = 0; j < start_points.length; j++) {
  legs.push({streets:[]);
}

function findIndex(points_index, start_leg_index) {
   // TODO avoid start_leg_index parameter and use binary search to make it faster
   //
   // Here avoid start_leg_index+1 to return the old leg index until the next leg
   for(var j = start_leg_index; j < start_points.length; j++) {
     if(start_points[j] >= points_index)
        return j;
   }
   return -1;
}

leg_index = -1;
if(path.details && path.details.street_name) 
for(var j = 0; j < path.details.street_name.length; j++) {
   var detail = path.details.street_name[j];
   var leg_index = findIndex(detail[0], leg_index);
   if(leg_index >= 0)
      // finally collect all streets per leg
      legs[leg_index].streets.push(detail[2]);
}

Why is this path details thing so complex?

Actually it is not that complex but it is at least a bit unusual :). The only reason that we use point indices in the JSON response and not e.g. an array entry for every road segment is that there would be a huge duplication of data. For example if there is just one street name but multiple road segments every array entry would have to contain the same road name over and over again like [{"street": "Road XY", "geometry":...}, {"street": "Road XY", "geometry":...}]. Instead we just “mark” where the street starts and ends with the help of the point array (path geometry). We could even left out the end index, but have decided to keep this to make handling a little bit easier.