Link promotion method and apparatus for improving route search performance for navigation system
First Claim
1. A method of searching a route between a start point to a destination for a navigation system, comprising the following steps of:
- executing a predetermined route search algorithm on map data having a layered structure for a predetermined direction between the start point and the destination for each predetermined search range;
retrieving candidate links from the map data for creating a route between the start point and the destination and temporarily storing the candidate links in a data storage;
applying climbing criteria and promotion criteria to the candidate links retrieved from the data storage to find whether there is a link in a lower layer of the map data to be promoted to a corresponding link in a higher layer of the map data;
storing data related to the links in the lower layer and the higher layer that have satisfied the climbing criteria and the promotion criteria; and
building a path between the destination and the start point by processing the data related to the links that have satisfied the criteria in a direction opposite to the predetermined direction executed for the route search algorithm.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for link promotion for a navigation system allows expansion of search in a lower layer to determine an optimum climbing point to an upper layer to search an optimum route. The link promotion procedure includes the steps of determining whether an upper link exists for a lower link, setting the upper link as a promoted link if such an upper link exists even if a climbing node point does not exist that connect the lower link and the upper link, and comparing a candidate normal route and a promoted route to find an optimum route.
-
Citations
20 Claims
-
1. A method of searching a route between a start point to a destination for a navigation system, comprising the following steps of:
-
executing a predetermined route search algorithm on map data having a layered structure for a predetermined direction between the start point and the destination for each predetermined search range; retrieving candidate links from the map data for creating a route between the start point and the destination and temporarily storing the candidate links in a data storage; applying climbing criteria and promotion criteria to the candidate links retrieved from the data storage to find whether there is a link in a lower layer of the map data to be promoted to a corresponding link in a higher layer of the map data; storing data related to the links in the lower layer and the higher layer that have satisfied the climbing criteria and the promotion criteria; and building a path between the destination and the start point by processing the data related to the links that have satisfied the criteria in a direction opposite to the predetermined direction executed for the route search algorithm. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. An apparatus for searching a route between a start point to a destination for a navigation system, comprising:
-
means for executing a predetermined route search algorithm on map data having a layered structure for a predetermined direction between the start point and the destination for each predetermined search range; means for retrieving candidate links from the map data for creating a route between the start point and the destination and temporarily storing the candidate links in a data storage; means for applying climbing criteria and promotion criteria to the candidate links retrieved from the data storage to find whether there is a link in a lower layer of the map data to be promoted to a corresponding link in a higher layer of the map data; means for storing data related to the links in the lower layer and the higher layer that have satisfied the climbing criteria and the promotion criteria; and means for building a path between the destination and the start point by processing the data related to the links that have satisfied the criteria in a direction opposite to the predetermined direction executed for the route search algorithm. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification