Route search method and apparatus for navigation system utilizing map data of XML format
First Claim
1. A method of searching a route between a start point to a destination point for a navigation system utilizing XML map data, comprising the following steps of:
- evaluating the XML map data stored in a data storage device and establishing boundary nodes on boundaries of administrative regions represented by the XML map data, said administrative regions are arranged by a layered structure in the XML map data;
creating cost information on virtual links that connect the boundary nodes on the administrative regions on layers higher than a base layer in the layered structure of the XML map data and storing the cost information on the virtual links in the data storage device;
creating cost information on physical links on the base layer of the layered structure of the XML map data and storing the cost information on the physical links in the data storage device;
searching routes, under control of a processor of the navigation system, by evaluating the XML map data with the cost information, between a start point and boundary nodes of an administrative region to which the start point belongs and searching routes between a destination point set to the navigation system via an input device and boundary nodes of an administrative region to which the destination point belongs;
selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the XML map data by evaluating the cost information on the virtual links under the control of the processor of the navigation system;
detecting candidate total routes between the start point and the destination point, under the control of the processor of the navigation system, by connecting the candidate virtual links and the routes between the start point and the destination point to the boundary nodes of the corresponding administrative regions; and
applying physical links in the base layer of the map data to the candidate total routes, under the control of the processor of the navigation system, for further evaluating costs of the total routes to select the most cost effective total route;
wherein the cost information is established on each of said administrative region layer of the XML map data, and the cost information on the virtual links on a particular administrative region layer is included in an administrative region layer of the XML map data that is immediately higher than the particular administrative region layer in a form of cost tables.
1 Assignment
0 Petitions
Accused Products
Abstract
A route search method for a navigation system using the XML map data that is layered based on administrative regions improves efficiency and accuracy of finding an optimum route. The method includes the steps of establishing boundary nodes on boundaries of administrative regions, creating cost information on virtual links that connect the boundary nodes on the administrative regions and physical links on a base layer, selecting candidate virtual links regions by evaluating the cost information, detecting candidate total routes between the start point and destination by connecting the candidate virtual links and other routes, and applying physical links in the base layer to the candidate total routes for further evaluating the costs of the total routes to select the most cost effective total route.
-
Citations
20 Claims
-
1. A method of searching a route between a start point to a destination point for a navigation system utilizing XML map data, comprising the following steps of:
-
evaluating the XML map data stored in a data storage device and establishing boundary nodes on boundaries of administrative regions represented by the XML map data, said administrative regions are arranged by a layered structure in the XML map data; creating cost information on virtual links that connect the boundary nodes on the administrative regions on layers higher than a base layer in the layered structure of the XML map data and storing the cost information on the virtual links in the data storage device; creating cost information on physical links on the base layer of the layered structure of the XML map data and storing the cost information on the physical links in the data storage device; searching routes, under control of a processor of the navigation system, by evaluating the XML map data with the cost information, between a start point and boundary nodes of an administrative region to which the start point belongs and searching routes between a destination point set to the navigation system via an input device and boundary nodes of an administrative region to which the destination point belongs; selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the XML map data by evaluating the cost information on the virtual links under the control of the processor of the navigation system; detecting candidate total routes between the start point and the destination point, under the control of the processor of the navigation system, by connecting the candidate virtual links and the routes between the start point and the destination point to the boundary nodes of the corresponding administrative regions; and applying physical links in the base layer of the map data to the candidate total routes, under the control of the processor of the navigation system, for further evaluating costs of the total routes to select the most cost effective total route; wherein the cost information is established on each of said administrative region layer of the XML map data, and the cost information on the virtual links on a particular administrative region layer is included in an administrative region layer of the XML map data that is immediately higher than the particular administrative region layer in a form of cost tables. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A navigation system for searching a route between a start point to a destination point utilizing XML map data and guiding a user to the destination point via the searched route, comprising:
-
a data storage device which stores the XML map data related to determining a preferable route between a start point and a destination point; an input device for selecting operational menus of the navigation system and specifying a destination point for a route guidance operation to the destination point; a processor for controlling overall operations of the navigation system in a route search process and a route guidance process; wherein the processor controls the following operations of the navigation system; evaluating the XML map data stored in the data storage device and establishing boundary nodes on boundaries of administrative regions represented by the XML map data, said administrative regions are arranged by a layered structure in the XML map data; creating cost information on physical links on the base layer of the layered structure of the XML map data and storing the cost information on the physical links in the data storage device; creating cost information on physical links on the base layer of the layered structure of the XML map data and storing the cost information on the physical links in the data storage device; searching routes by evaluating the XML map data with the cost information, between a start point and boundary nodes of an administrative region to which the start point belongs and searching routes between a destination point set to the navigation system via the input device and boundary nodes of an administrative region to which the destination point belongs; selecting candidate virtual links that connect the boundary nodes of different administrative regions on a particular layer of the XML map data by evaluating the cost information on the virtual links under the control of the processor of the navigation system; detecting candidate total routes between the start point and the destination point, under the control of the processor of the navigation system, by connecting the candidate virtual links and the routes between the start point and the destination point to the boundary nodes of the corresponding administrative regions; and applying physical links in the base layer of the map data to the candidate total routes for further evaluating costs of the total routes to select the most cost effective total route; wherein the cost information is established on each of said administrative region layer of the XML map data, and the cost information on the virtual links on a particular administrative region layer is included in an administrative region layer of the XML map data that is immediately higher than the particular administrative region layer in a form of cost tables. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification