Routing

From Navit's Wiki
Revision as of 13:10, 28 August 2012 by Mvglasow (talk | contribs) (Added tweaks introduced in r5216, explained order)
Jump to: navigation, search

How it works

First, a few rectangles are calculated (route_calc_selection):

  • One that does include the position and destination point with an additional 25% at the ends with an order of 4
  • One square-shaped of about 80 km edge length around the position with an order of 8
  • One square-shaped of about 20 km edge length around the position with an order of 18
  • Like the last two, but for the destination

The "order" of a road depends on which tile level it is placed in. Refer to Navit's binary map driver, specifically the How An object Is placed in a tile section, for details.

Then the map is queried with this rectangles and from the result a graph is built, consisting of points and segments. Then the graph gets flooded, beginning with the destination. This makes the graph re-useable when the position changes. The used algorithm is Dijkstra together with Fibonacci-Heaps to quickly get the lowest value point. When no points are left (this could be optimized, because once the position is reached flooding the graph could stop) the graph is followed from the position back to the destination and a route path is build. This route path will be displayed just like a map.


Diagnosing Routing Problems

Turn on the route graph map in the Settings/Maps menu (Or from the Map menu in GTK). You will see lots of arrows and numbers. The numbers indicate the estimate of time in 10ths of seconds to reach your destination. The arrows will show the direction to the destination. If two very different numbers are close together but there should be a connection, there is most likely none.

Tweaks

As of r5216, the vehicle profile in navit.xml can take a route_depth attribute. This attribute sets the size and order of the rectangles.