Method And Apparatus For Creating Map Data And Method And Apparatus For Route Search

• US 20070179708A1
• Filed: 01/29/2007
• Published: 08/02/2007
• Est. Priority Date: 01/30/2006
• Status: Abandoned Application

• 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
• Application Number:
  US11/668,289
• Publication Number:
  US 20070179708A1
• 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/3815 Road data
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G09B 29/102 using electrical means

Abstract

A method for creating map data for navigation includes setting a plurality of levels corresponding to levels of detail, stratifying meshes at the individual levels, and creating map data that includes road information of the individual meshes at the individual levels. The map data includes, for individual combinations of two meshes at a predetermined level, data for identifying meshes at the predetermined level that are used to search for routes from one mesh in each of the combinations of two meshes to the other mesh in each of the combinations of two meshes as search range data.

Claims

1. A method for creating map data for navigation comprising:

setting a plurality of levels corresponding to levels of detail,

stratifying meshes at the individual levels, and

creating map data that includes road information of the individual meshes at the individual levels, wherein the map data includes, for individual combinations of two meshes at a predetermined level, data for identifying meshes at the predetermined level that are used to search for routes from one mesh in each of the combinations of two meshes to the other mesh in each of the combinations of two meshes as search range data.

2. The method according to claim 1, comprising:

creating a list of boundary-exit links that exit from a mesh and a list of boundary-entrance links that enter a mesh for each of the meshes with reference to the road information of each of the meshes;

for individual combinations of two meshes, searching for all routes from boundary-exit links in one mesh in each of the combinations of two meshes to boundary-entrance links in the other mesh in each of the combinations of two meshes; and

creating the search range data from data for identifying meshes to which links that constitute each of the searched routes belong.

3. The method according to claim 1, comprising:

creating a list of boundary-exit links that exit from a mesh and a list of boundary-entrance links that enter a mesh for each of the meshes with reference to the road information of each of the meshes;

performing a search from boundary-exit links in a first mesh until the search cannot be performed and, after performing the search, obtaining all routes from the boundary-exit links in the first mesh to boundary-entrance links in a second mesh with reference to the search result; and

creating search range data corresponding to a combination of the first and second meshes by determining meshes to which links that constitute each of the searched routes belong.

4. The method according to claim 1, wherein the level of the meshes is a level immediately below a top level, a link that constitutes road information at the top level does not cross over meshes at the level immediately below the top level, and a link record of the link includes identification data of a mesh at the level immediately below the top level where the link exists.

5. A route search method for a navigation apparatus that searches for a route to a destination location, the method comprising:

setting a plurality of levels corresponding to levels of detail, stratifying meshes at the individual levels, storing, for individual combinations of two meshes at a level immediately below a top level, data for identifying meshes that are used to search for routes from one mesh in each of the combinations of two meshes to the other mesh in each of the combinations of two meshes as search range data, together with road information of the individual meshes at the individual levels, in map data, performing control so that a link that constitutes road information at the top level does not cross over meshes at the level immediately below the top level, and storing, in a link record of the link, identification data of a mesh at the level immediately below the top level where the link exists; and

searching for a route between nodes at the top level, using top-level links having mesh identification data of meshes that are defined to be used for route search in the search range data.

6. An apparatus for creating map data for navigation for setting a plurality of levels corresponding to levels of detail, stratifying meshes at the individual levels, and creating map data that includes road information of the individual meshes at the individual levels, the apparatus comprising:

a link-list creating unit that creates a list of boundary-exit links that exit from a mesh and a list of boundary-entrance links that enter a mesh for each of the meshes with reference to the road information of each of the meshes;

a route searching unit that, for individual combinations of two meshes, searches for all routes from boundary-exit links in one mesh in each of the combinations of two meshes to boundary-entrance links in the other mesh in each of the combinations of two meshes; and

a search-range-data creating unit that creates, from data for identifying meshes to which links that constitute each of the searched routes belong, search range data for identifying meshes that are used to search for routes from one mesh in each of the combinations of two meshes to the other mesh in each of the combinations of two meshes.

7. An apparatus for creating map data for navigation for setting a plurality of levels corresponding to levels of detail, stratifying meshes at the individual levels, and creating map data that includes road information of the individual meshes at the individual levels, the apparatus comprising:

a link-list creating unit that creates a list of boundary-exit links that exit from a mesh and a list of boundary-entrance links that enter a mesh for each of the meshes with reference to the road information of each of the meshes;

a route searching unit that performs a search from boundary-exit links in a first mesh until the search cannot be performed and, after performing the search, obtains all routes from the boundary-exit links in the first mesh to boundary-entrance links in a second mesh with reference to the search result; and

a search-range-data creating unit that creates, from data for identifying meshes to which links that constitute each of the searched routes belong, search range data for identifying meshes that are used to search for routes from the first mesh to the second mesh.

8. A navigation apparatus that searches for a route to a destination location, the navigation apparatus comprising:

a map-data storage unit that stores, for individual combinations of two meshes at a level immediately below a top level, data for identifying meshes that are used to search for routes from one mesh in each of the combinations of two meshes to the other mesh in each of the combinations of two meshes as search range data, together with road information of the individual meshes at individual levels, in map data, performs control so that a link that constitutes road information at the top level does not cross over meshes at the level immediately below the top level, and stores the map data, which includes, in a link record of the link, identification data of a mesh at the level immediately below the top level where the link exists;

a destination-location setting unit that sets a destination location; and

a route searching unit that obtains individual nodes at the top level on a starting location side and a destination location side and searches for a route between the nodes, using links at the top level having mesh numbers of meshes that are defined to be used for route search in the search range data.