From Navit's Wiki
Revision as of 15:59, 25 August 2009 by Cp15 (talk | contribs)
Jump to: navigation, search

How Routing in navit 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

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.