System and method for multi-resolution routing
A system, method and computer program product for efficiently generating on- and off-road travel routes using multi-resolution maps including a map generator ( 108 ), map database ( 106 ), route generator ( 100 ), heuristic generator ( 102 ), and search envelope factor generator ( 104 ). The map generator ( 108 ) converts input raster and vector map data into output multi-resolution raster map data suitable for routing and stores it in the map database ( 106 ). The route generator ( 100 ) uses the map database ( 106 ) to produce a route at a coarse zoom level and then regenerate the route at progressively higher zoom levels. The heuristic generator ( 102 ) penalizes high resolution routes that deviate too far from one or more low resolution routes. The search envelope factor generator ( 104 ) computes this penalty based on the distance from a given search graph node to the low resolution routes.
1. A system for generating a travel route comprising:
one or more computer processors configured to perform the functions of:
a map generator that generates maps at multiple detail levels; and
a route generator that generates a complete higher detail route based upon one or more complete lower detail routes,
wherein the route generator favors candidate complete higher detail routes that fall within a search envelope surrounding the complete lower detail routes, and
the one or more computer processors are configured to display the generated maps and generated routes to a user on a display device.
2. The system of claim 1 , wherein the route generator uses a graph search biased toward nodes that are closer to the complete lower detail routes.
3. The system of claim 1 , wherein the search envelope's dimensions depend on a current detail level.
4. The system in claim 1 , further comprising a heuristic generator that favors the candidate complete higher detail routes that are near the complete lower detail routes.
5. The system of claim 1 , wherein the map generator enlarges map features at lower detail levels to improve routing.
6. A method for generating a travel route, the method comprising:
one or more computer processors configured to perform the steps of:
generating by a map generator maps at multiple detail levels; and
generating by a route generator a complete higher detail route based upon one or more complete lower detail routes,
wherein the route generator favors candidate complete higher detail routes that fall within a search envelope surrounding the complete lower detail routes, and
the one or more computer processors are configured to display the generated maps and generated routes to a user on a display device.
7. The method of claim 6 , wherein the route generator uses a graph search biased toward nodes that are closer to the complete lower detail routes.
8. The method of claim 6 , wherein the search envelope's dimensions depend on a current detail level.
9. The method of claim 6 , wherein a heuristic generator favors the candidate complete higher detail routes that are near the complete lower detail routes.
10. The method of claim 6 , wherein the map generator enlarges map features at lower detail levels to improve routing.
11. A computer program product for generating a travel route and including one or more computer readable instructions embedded on a tangible computer readable medium and configured to cause one or more computer processors to perform the steps of:
generating by a map generator maps at multiple detail levels; and
generating by a route generator a complete higher detail route based upon one or more complete lower detail routes,
wherein the route generator favors candidate complete higher detail routes that fall within a search envelope surrounding the complete lower detail routes, and
the one or more computer processors are configured to display the generated maps and generated routes to a user on a display device.
12. The computer program product of claim 11 , wherein the route generator uses a graph search biased toward nodes that are closer to the complete lower detail routes.
13. The computer program product of claim 11 , wherein the search envelope's dimensions depend on a current detail level.
14. The computer program product of claim 11 , wherein a heuristic generator favors the candidate complete higher detail routes that are near the complete lower detail routes.
15. The computer program product of claim 11 , wherein the map generator enlarges map features at lower detail levels to improve routing.