MAP-DATA-GENERATION DEVICE AND MAP-GENERATION METHOD USED THEREFOR, AND NAVIGATION DEVICE AND ROUTE-SEARCH METHOD USED THEREFOR

• US 20070250264A1
• Filed: 04/25/2007
• Published: 10/25/2007
• Est. Priority Date: 04/25/2006
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.), Mobilemedia Brain Association,Inc.
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.), Mobilemedia Brain Association,Inc.
• Inventors: Sekine, Minoru, Ohira, Masaaki
• Granted Patent: US 7,890,252 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures

Abstract

A map-data-generation device and a map-generation method used therefor, and a navigation device and a route-search method used therefor are provided. The map-data-generation device generates hierarchical guide-route-search-map data by using information about a road link of level 2 (reference level), the road link generating a guide-object road. A first upper-level-link-determination unit determines a level-3 link by performing level-raising processing by using level-2-link information. A second-upper-level-link-determination unit acquires a plurality of links of levels (levels 4 to 8) higher than level 3 by performing the level-raising processing by using information about the level-3 link, and specifies an upper level map to which the link belongs on the basis of the range of a distance between a departure-point link and a destination-point link.

Claims

1. A map-data-generation method capable of generating hierarchical map data by using road link information associated with a reference level map, the method comprising:

determining at least one first upper level link of a first upper level map by using the road link information associated with the reference level map, the first upper level map being at a higher map level than the reference level map, and specifying at least one link to function as a route-search-start link of the first upper level map; and

determining upper level links of a plurality of upper level maps higher than the first upper level map by using information associated with the first upper level link, and specifying at least one upper level link to function as a route-search-start link for each of the plurality of upper level maps,

wherein the plurality of upper level maps are defined according to a distance range between a departure point and a destination point.

2. The map-data-generation method according to claim 1, wherein determining at least one first upper level link includes:

dividing at least one mesh of the reference level map into divided areas, ensuring that the number of links within the divided areas is approximately equivalent to or lower than a predetermined number, and generating a list of leaving links, each of the leaving links exiting a divided area;

generating a search-start link set from all of the links leaving at least one predetermined divided area, and performing route-search processing in a forward traveling direction to search for routes extending from the search-start link set; and

acquiring route links associated with routes obtained through the search, where the number of the acquired route links is approximately equivalent to or smaller than a predetermined link number, the predetermined link number denoting the number of links from a route-start link to a predetermined link, and where the number of search branches required to complete the route search is approximately equivalent to or larger than a predetermined branch number, and specifying an adjacent link which is the closest to the route-start link of all of the acquired route links as a route-search-start link of the first upper level map.

3. The map-data-generation method according to claim 2, wherein the route-search processing is performed until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, a search for routes extending from the search-start link set is performed on the basis of a result of the route-search processing.

4. The map-data-generation method according to claim 2, wherein determining at least one first upper level link further includes:

generating a list of entering links, each of the entering links going into a divided area;

generating a second search-start link set from all of the links entering the predetermined divided area, and performing the route-search processing in a backward traveling direction to search for routes extending from the second search-start link set;

acquiring route links associated with routes obtained through the backward search, where the number of the acquired route links is approximately equivalent to or smaller than a predetermined link number, the predetermined link number denoting the number of links from a route-start link to a predetermined link, and where the number of search branches required to make the route search is approximately equivalent to or larger than a predetermined branch number, and specifying an adjacent link which is the closest to the route-start link of all of the acquired route links as a route-search-start link of the first upper level map; and

performing the above processing for each of the divided areas.

5. The map-data-generation method according to claim 4, wherein the route-search processing is performed until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, a search for each of the routes extending from the second search-start link set is performed on the basis of a result of the route-search processing.

6. The map-data-generation method according to claim 4, wherein determining the upper level links includes:

generating a first upper level search-start link set for the first level map from all first-upper-level-route-search-start links associated with the predetermined divided area, performing the route-search processing in the backward traveling direction to search for routes extending from the first upper level search-start link set; and

determining to which of the upper level maps the links obtained from route-search processing belong to on the basis of a distance between a route-start-point link and a route-terminal-point link.

7. The map-data-generation method according to claim 6, wherein the route-search processing is performed until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, a search for each route extending from the first upper level search-start-link set is performed on the basis of a result of the route-search processing.

8. The map-data-generation method according to claim 2, wherein determining the upper level links includes:

creating a first upper level search-start link set associated with the first upper level map, and performing the route-search processing in the forward traveling direction to search for routes extending from the first upper level search-start link set; and

determining to which of the upper level maps the links obtained from the route-search processing belong to on the basis of a distance between the route-start-point link and a route-terminal-point link.

9. The map-data-generation method according to claim 8, wherein the route-search processing is performed until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, a search for routes extending from the search-start link set is performed on the basis of a result of the route-search processing.

10. A map-data-generation device configured to generate hierarchical map data by using road link information associated with a reference level map, the device comprising:

a first link-determination unit configured to determine at least one first upper level link of a first upper level map higher than the reference level map by using the road link information associated with the reference level map, and specify at least one link to function as a route-search-start link of the first upper level map; and

a second link-determination unit configured to determine upper level links associated with a plurality of upper level maps by using information associated with the first upper level link, each of the plurality of the upper level maps being at a higher level than the first upper level map, and specify at least one link to function as a route-search-start link of each of the plurality of upper level maps; and

an upper-level-setting unit configured to set a distance range of each of the plurality of upper level maps so that an upper level map to which a predetermined link used to perform the route search belongs can be determined on the basis of a distance between a departure-point link and a destination-point link.

11. The map-data-generation device according to claim 10, wherein the first-step-determination unit includes:

a list-generation unit configured to divide at least one mesh of the reference level map into divided areas, ensure that the number of links within the divided areas is approximately equivalent to or lower than a predetermined number, and generate a list of leaving links, each of the leaving links exiting a divided area;

a route-search unit configured to form a search-start link set from all of the links leaving at least one predetermined divided area and perform route-search processing in a forward traveling direction to search for routes extending from the search-start link set; and

a link-acquisition unit that is configured to acquire route links associated with the routes obtained through the search, where the number of the acquired route links is approximately equivalent to or smaller than a predetermined link number, the predetermined link number denoting the number of links from a route-start link to a predetermined link, and where the number of search branches required to complete the route search is approximately equivalent to or larger than a predetermined branch number, and that is configured to specify an adjacent link which is the closest to the route-start link of all of the acquired route links as a route-search-start link of the first upper level map.

12. The map-data-generation device according to claim 11, wherein the route-search unit performs the route-search processing until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, a search for routes extending from the search-start-link set is performed on the basis of a result of the route-search processing.

13. The map-data-generation device according to claim 11, wherein, in the first link-determination unit, the list-generation unit generates a list of entering links, each of the entering links going into one of the divided areas, the route-search unit generates a second search-start-link set from all of the links entering the predetermined divided area and performs the route-search processing in a backward traveling direction to search for routes extending from the second search-start-link set, and the link-acquisition unit acquires route links associated with the routes obtained through the backward search, where the number of the acquired route links is approximately equivalent to or smaller than a predetermined link number, the predetermined link number denoting the number of links from a route-start link to a predetermined link, and where the number of search branches required to complete the backward route search is approximately equivalent to or larger than a predetermined branch number, and specifies an adjacent link which is the closest to the route-start link of all of the acquired route links as a second route-search-start link of the first upper level map.

14. The map-data-generation device according to claim 13, wherein the route-search unit performs the route-search processing until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, a search for routes extending from the second search-start-link set is performed on the basis of a result of the route-search processing.

15. The map-data-generation device according to claim 11, wherein the second link-determination unit includes:

a route-search unit configured to form the search-start link set from all first-upper-level-route-search-start links associated with the predetermined divided area, and perform the route-search processing to search for routes extending from the search-start link set to all of the first-upper-level-search-start links;

a link-acquisition unit configured to acquire route links associated with the routes obtained through the search, where the number of the acquired route links is approximately equivalent to or smaller than a predetermined link number, the predetermined link number denoting the number of links from a route-start link to a predetermined link, and where the number of search branches required to complete the route search is approximately equivalent to or larger than a predetermined branch number, and that is configured to specify an adjacent link which is the closest to the route-start link of all of the acquired route links as a route-search-start link of a next map level; and

a link-level-determination unit configured to determine to which of the upper level maps the links obtained from route-search processing belong to on the basis of a distance between the route-start link and a route-terminal-point link.

16. The map-data-generation device according to claim 15, wherein the route-search unit performs the route-search processing until the search branch can be extended only with more difficulty than a previous search branch extension, and after the difficulty in extending the search branch increases, the route-search unit searches for routes extending from the search-start link set on the basis of a result of the route-search processing.

17. A route-search method used for a navigation device configured to search for a route to a destination point, the route-search method comprising:

storing hierarchical map data in a storage unit, where the hierarchical map data includes road link information associated with a reference level map, first upper level link information associated with a first upper level map, the first upper level link information being obtained by using the road link information associated with the reference level map, and higher level link information associated with a plurality of links, each of the plurality of links associated with a higher level map, the higher level link information being obtained by using the first upper level link information;

calculating a slant distance between a departure point and the destination point when the destination point is set;

determining a higher level map other than the first upper level map on the basis of the slant distance, where a link used to perform route-search processing belongs to the higher level map;

searching for a route on the reference level map that can be shifted to the first upper level map;

searching for a route on the first upper level map that can be shifted to the higher level map; and

performing the route-search processing by using the higher level link information associated with the higher level map.

18. A navigation device configured to search for a route to a destination point, the navigation device comprising:

a storage unit configured to store hierarchical map data including road link information associated with a reference level map, first upper level link information associated with a first upper level map, the first upper level link information being obtained by using the road link information associated with the reference level map, and higher level link information associated with a plurality of links each corresponding to a higher level map being at a higher level than the first upper level map, the higher level link information being obtained by using the first upper level link information;

a destination-setting unit configured to set the destination point; and

a route-search unit configured to (1) select one higher level map higher than the first upper level map on the basis of a slant distance between a departure point to the destination point, where a link used for performing route-search processing belongs to the higher level map, (2) search for a route on the reference level map that can be shifted to the first upper level map, (3) search for a route on the first upper level map that can be shifted to the higher level map, and (4) perform the route-search processing by using the higher level link information associated with the higher level map.