Difference between revisions of "Routing"

From Navit's Wiki
Jump to: navigation, search
(New page: 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 wi...)
(No difference)

Revision as of 18:22, 8 May 2008

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.