WO2004012171A1 - 地図データ製品および地図データ処理装置 - Google Patents

地図データ製品および地図データ処理装置 Download PDF

Info

Publication number
WO2004012171A1
WO2004012171A1 PCT/JP2003/009650 JP0309650W WO2004012171A1 WO 2004012171 A1 WO2004012171 A1 WO 2004012171A1 JP 0309650 W JP0309650 W JP 0309650W WO 2004012171 A1 WO2004012171 A1 WO 2004012171A1
Authority
WO
WIPO (PCT)
Prior art keywords
map
information
mesh
data
recording medium
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2003/009650
Other languages
English (en)
French (fr)
Inventor
Takashi Nomura
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Faurecia Clarion Electronics Co Ltd
Original Assignee
Xanavi Informatics Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from JP2002220922A external-priority patent/JP4145596B2/ja
Priority claimed from JP2002220923A external-priority patent/JP4145597B2/ja
Application filed by Xanavi Informatics Corp filed Critical Xanavi Informatics Corp
Priority to US10/522,629 priority Critical patent/US7783687B2/en
Priority to EP03771424A priority patent/EP1548686B1/en
Publication of WO2004012171A1 publication Critical patent/WO2004012171A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/38—Electronic maps specially adapted for navigation; Updating thereof
    • G01C21/3863—Structures of map data
    • G01C21/387—Organisation of map data, e.g. version management or database structures
    • G01C21/3881—Tile-based structures
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09B—EDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS
    • G09B29/00—Maps; Plans; Charts; Diagrams, e.g. route diagram
    • G09B29/10—Map spot or coordinate position indicators; Map reading aids
    • G09B29/106—Map spot or coordinate position indicators; Map reading aids using electronic means

Definitions

  • the present invention relates to a map data product and a map data processing apparatus.
  • Navigation devices that calculate routes, display recommended routes, and perform navigation are known. It is also known that the route calculation data used for route calculation is managed in units obtained by dividing the map into meshes. It is also known that route calculation data is managed by dividing it into multiple levels with different scale ratios, and using multiple levels of route calculation data for route calculation. Disclosure of the invention
  • the present invention provides a map data product and a map data processing apparatus that can efficiently read map data provided on a recording medium or the like.
  • the data product that can be read by the computer or the map data processing apparatus of the present invention has map data having information relating to the map.
  • the map data consists of a structure in which a map is divided into a plurality of mesh-shaped sections, and information related to the map is divided corresponding to the divided sections, and a section set in which information related to the map is collected from a plurality of adjacent sections. Structure that is managed in units and processed by the map data processing device in units of partitions With.
  • a partition set consists of a core partition that consists of one or more partitions that do not overlap with another partition set, and an overlap that consists of one or more partitions that correspond to the core partitions of another partition set.
  • it is composed of a wrap section.
  • the information related to the map corresponding to the top lap section is generated by thinning out the information related to the map corresponding to the core section of the other section set.
  • the information about the map is the information about the route on the map used for route calculation, and the intersection of the road is a node
  • the information about the route on the map is a plurality of nodes existing on one road
  • the information about the route on the map corresponding to the core section is composed of the own node information and the adjacent node information, and the adjacent node information of the node connected to each own node. It is preferable that the information on the route on the map corresponding to the overlap section is generated by deleting the adjacent node information of the predetermined node from the information on the route on the map corresponding to the core section.
  • the information regarding the map corresponding to the section set has a structure that is continuously recorded as one lump on the recording medium.
  • the map-related information further has a structure that can be processed by the map data processing device in units of sections.
  • it has a structure that has management information for information related to maps in units of partition sets, and information about maps acquired by the map data processing device can be updated in units of partition sets using management information. Is preferred.
  • the information about the map is preferably information about the route on the map used for route calculation.
  • the data product that can be read by another computer or map data processing apparatus of the present invention has map data having information relating to the map.
  • the map data includes a structure in which a map is divided into a plurality of mesh-shaped sections, and information related to the map is divided corresponding to the divided sections, and information related to the map is collected from a plurality of adjacent sections.
  • the structure is managed in units of image sets and processed by the map data processing device in units of partition sets.
  • the partition set includes a first partition and one or more partitions adjacent to the first partition.
  • the information about the map corresponding to the first section is composed of information about the divided map, and the information about the map corresponding to one or more sections adjacent to the first section is divided. Consists of information generated by thinning out information about the map.
  • a data product that can be read by another computer or map data processing apparatus of the present invention has a map data containing information about the map.
  • the map data includes a structure having information on a map in a plurality of level units having different scale ratios, and a map is divided into a plurality of mesh-shaped sections for each level, and the map data is mapped to the divided section units.
  • a structure having a management table having information for managing the partition set, and the management table has information by which a correspondence relation between the levels of the partition set of each level can be obtained by calculation.
  • the management table has information indicating the position of the reference partition representing the partition set, information on the number of partition directions in the partition set, and information on the number of divided horizontal directions.
  • the partition set has a rectangular shape
  • the reference partition representing the partition set is a partition located at the lower left of the partition set.
  • the information for managing the partition set is preferably stored in the order in which the reference partitions representing the partition set are arranged in the horizontal direction and the vertical direction.
  • the map is divided into a plurality of mesh-like blocks, and the plurality of sections are sections obtained by further dividing each block, and a management table is provided for each block. Is preferred.
  • the information about the map acquired by the map data processing apparatus can be updated in units of partition sets using a management table.
  • the intersection of roads on the map is a node
  • the information on the map has information on the node
  • the information on the map divided into sections is the information of the nodes in the section and the corresponding nodes at other levels. It also has node correspondence information between levels, and grasps the correspondence relationship between levels of nodes using the correspondence relationship between levels of partition sets and node correspondence information between levels of partitions constituting the partition set. Preferred to be able to That's right.
  • the information about the map is preferably information about the route on the map used for route calculation.
  • the data product is preferably a recording medium on which map data is recorded.
  • a map data processing apparatus of the present invention includes a recording medium driving unit on which the recording medium is mounted, and a processing unit that performs map data processing based on map data recorded on the recording medium.
  • the processing unit when the information about the map is information about the route on the map used for route calculation, the processing unit performs route calculation based on the information about the route on the map recorded in the recording medium. Is preferred. Brief Description of Drawings
  • Fig. 1 is a diagram for explaining the exchange of map data.
  • Fig. 2 is a block diagram of the in-vehicle navigation device.
  • Figure 3 is a conceptual diagram illustrating the relationship between map data levels, blocks, and meshes.
  • Fig. 4 is a diagram for explaining the concept of a mesh set.
  • FIG. 5 is a diagram schematically showing the relationship between the block management table, the mesh management table, and the actual mesh set data.
  • FIG. 6 shows the block management table
  • FIG. 7 shows the contents of the mesh management table.
  • FIG. 8 shows the file management table in detail.
  • FIG. 9 shows the mesh set data for connection / partial restriction data.
  • FIG. 10 is a diagram showing the contents of the reference mesh data of the connection / partial restriction data.
  • FIG. 11 is a diagram showing details of the connection portion data.
  • Fig. 12 shows the connection data part of the overlap mesh.
  • Figure 13 shows the mesh set data of the inter-level correspondence data.
  • Fig. 14 is a diagram showing the contents of the reference mesh data of the inter-level correspondence data.
  • Figure 15 shows the details of the inter-level correspondence data.
  • Figure 16 shows the details of the correspondence information.
  • Fig. 17 shows the details of the node correspondence information.
  • FIG. 18 is a diagram showing details of adjacent node correspondence information.
  • FIG. 19 is a diagram for explaining the route information list identification information.
  • FIG. 20 is a diagram for explaining the association of mesh sets between levels.
  • Figure 21 is a diagram for explaining how map data is updated and managed by the navigation device.
  • Fig. 22 is a diagram showing a flow chart of control that performs route calculation by reading route calculation data.
  • FIG. 23 is a diagram showing a detailed flowchart of the process of step S 3 in FIG.
  • Fig. 24 is a diagram for explaining how mesh sets are managed using the file management table. BEST MODE FOR CARRYING OUT THE INVENTION
  • FIG. 1 is a diagram for explaining the exchange of map data such as map display data and route calculation data in the present embodiment.
  • the in-vehicle navigation device 1 reads map data, management information, guidance search data, and the like from a recording medium 2 such as CD-ROM or DV-ROM.
  • Removable memory 3 receives update data such as map data.
  • the rim bubble memory 3 is a replaceable recording medium in which update data is recorded in order to update a part of the map data.
  • the navigation device 1 can also be connected to a communication device 4 such as a mobile phone.
  • the navigation device 1 can be connected to the Internet 5 via the communication device 4 and further connected to the map server 6 via the Internet 5.
  • the map server 6 holds from the old map data to the latest map data in the map database 7, and also holds from the guide search data to the latest guide search data in the guide search database 8. Accordingly, the map server 6 can provide update data for updating a part of the map data to the navigation apparatus 1 via the internet 5.
  • Guided search data refers to POI and other location information, type and name attribute information. It is data that stores information.
  • the navigation device 1 has a control device 1 1 and a nonvolatile memory 1 2.
  • the control device 11 is composed of a microprocessor and its peripheral circuits.
  • the non-volatile memory 12 is a non-volatile memory such as a hard disk or a flash memory provided inside the navigation apparatus 1.
  • the nonvolatile memory 12 may be any storage device as long as the written data is not lost even when the navigation device 1 is turned off.
  • the recording medium 2 is mounted on the navigation device 1, it remains in the navigation device 1 unless it is replaced with a new recording medium 2. Therefore, it may be referred to as fixed media for the rim bubble memory 3.
  • the map database 7 and the guidance search database 8 have all the old and new map data and guidance search data, they are databases of mother data.
  • the map server 6 uses the map data overnight base 7 and the guidance search database 8 to store the recording medium 2 having the initial (before update) map data 2 and the removable memory 3 having the update data. Can be prepared.
  • FIG. 2 is a block diagram of the in-vehicle navigation device 1.
  • the navigation device 1 includes a control device 1 1, a non-volatile memory 1 2, a current location detection device 1 3, a DVD drive device 14, a memory 1 5, a communication interface 1 6, and a rim bubble memory reading device 1 7 Monitor 1 8 and input device 1 9.
  • the current location detection device 1 3 is a current location detection device that detects the current location of the vehicle.For example, a direction sensor that detects the traveling direction of the vehicle, a vehicle speed sensor that detects the vehicle speed, or a GPS signal from a GPS (G1 obal Positioning System) satellite. It consists of GP S sensor to detect.
  • the DVD drive device 14 is a device that loads the recording medium 2 and reads map data and the like. In the present embodiment, the recording medium 2 is DVD-ROM. It may be a CD-ROM or other recording medium.
  • the memory 15 is a memory for storing vehicle position information detected by the current position detection device 13 or node information on the recommended route calculated by the control device 11 or link information. It also stores a mesh management table, which will be described later.
  • the memory 15 is a working area of the control device 11.
  • Communication interface 1 6 is an interface for connecting the communication device 4.
  • the mobile phone can be used or connected to the Internet via the communication interface 16.
  • the removable memory reading device 17 is a device that can be loaded with the removable memory 3 and read data from the removable memory 3.
  • the monitor 18 is a display device that displays a map, a recommended route, and various information.
  • the monitor 18 may be provided integrally as a part of the navigation apparatus main body, or may be provided separately as a housing. Furthermore, only the monitor 18 may be connected to the navigation device main body by a cable or the like and provided at a separated position.
  • the input device 19 is an input device for inputting the destination of the vehicle or the like when searching for a route. It may be a remote control, or it may be composed of an evening panel provided on the monitor 18 screen.
  • the control device 1 1 uses the current location information of the vehicle detected by the current location detection device 1 3 and the map data stored in the recording medium 2 or nonvolatile memory 1 2 to display the road map and calculate the route ( Performs various navigation processes such as route search) and route guidance.
  • Various processing programs executed by the control device 11 are incorporated in a ROM (not shown) provided in the control device 11.
  • Map data is information about the map.
  • Background (for map display) data location data, route calculation data, guidance data (intersection name, road name, direction name, direction guide, facility information, etc.) Etc.
  • the background data is data for displaying the background of roads and road maps.
  • the locator data is used to identify the current location of the vehicle and map matching.
  • the route calculation data is network data consisting of branch information that is not directly related to the road shape, and is mainly used when computing recommended routes (route search).
  • Guidance data is data consisting of the name of an intersection, etc., and is used to guide the recommended route to the driver based on the calculated recommended route.
  • the map data in this embodiment is managed by the concept of level, block, and mesh.
  • the map data is divided into seven levels with different scale ratios, the level of the most detailed scale ratio is set to level 0, and the level of the most extensive map is set to level 6.
  • Each level includes map data with different scale ratios, but the target area is the same for each level. In other words, if the whole of Japan is the target, the map data of the whole of Japan with different scale ratios for each level is available.
  • One block 10 4 is divided into a plurality of meshes 10 5 and managed.
  • management is performed with p X q meshes.
  • the number of divided meshes between each block 10 4 is the same number p X q at the same level.
  • Level 1 and Level 2 the number of blocks that divide area 1 0 1 and the number of meshes that divide each block are different. This is handled by Level 2 which handles a wide area map with a smaller scale ratio (large denominator value) and Level 1 which handles a detailed map with a larger scale ratio (small denominator value) than Level 2. This is because the amount of data is different ( ie, appropriate division is performed according to the amount of data handled at each level. However, within the same level, the size of one block and the size of one mesh Note that the number of divided blocks at each level in Fig. 3 is an example, and is not necessarily limited to this number.
  • a mesh may be called a cell
  • a block may be called a first division unit
  • a mesh may be called a second division unit.
  • these blocks and meshes may be called geographically divided units.
  • the route calculation data in the map data will be described.
  • the route calculation data is divided into mesh units and managed as described above.
  • the concept of mesh set is further introduced.
  • Fig. 4 is a diagram for explaining the concept of a mesh set.
  • Reference numeral 2 0 1 is the mesh described above.
  • each mesh is referred to as a reference mesh.
  • a unit obtained by collecting a plurality of reference meshes 2 0 1 is called a core mesh 2.0 2.
  • six reference meshes 20 1 that are adjacent to each other are collected to form a core mesh 20 2.
  • a reference mesh 2 0 1 indicated by a broken line is appropriately arranged around the core mesh 2 0 2. This is called overlap mesh 2 0 3.
  • the core mesh 2 0 2 and the overlapping mesh 2 0 3 are combined to form a mesh set 2 0 4.
  • the number of reference meshes 20 1 constituting the core mesh 2 0 2 varies depending on the mesh set 2 0 4. In the example of FIG. 4, the number is six, but one or a plurality of reference meshes 20 1 constitute a mesh set 204.
  • the shape of the core mesh 20 2 is a rectangular shape (quadrangle) in the present embodiment. However, the shape may be not only rectangular but also L-shaped. That is, it may be a mesh set 20 4 of any shape composed of a plurality of adjacent reference meshes 20 1. However, the rectangular shape is most preferable.
  • the core mesh 20 2 is set without overlapping and without a gap in the block.
  • the overlap mesh 2 0 3 set around the core mesh 2 0 2 overlaps with the reference mesh constituting the core mesh of another mesh set. It may also overlap with the reference mesh that makes up the overlapping meshes of other mesh sets. Also, a mesh composed of one core mesh and one or more reference mesh overlap mesh There is also a set.
  • the route calculation data is managed as mesh data of the reference mesh.
  • the mesh data of the reference mesh composing the overlapping mesh is generated by thinning out the data from the mesh data of the reference mesh composing the mesh of another corresponding mesh set. That is, the mesh data of the overlap mesh is composed of coarse data that is less than the mesh data of the core mesh. Details will be described later.
  • the route calculation data is managed in units of reference meshes, and further managed in units of mesh sets.
  • the route calculation data managed in units of mesh sets is stored in recording medium 2 in units of mesh sets.
  • the route calculation data stored in the recording medium 2 in units of mesh sets can be continuously read out from the recording medium 2 in units of mesh sets.
  • the data for each mesh set is basically stored in the order of data for the core mesh and data for the overlap mesh. Depending on the application, it is also possible to read mesh data from the position of any reference mesh that makes up the mesh set.
  • the concept of mesh setting is introduced to the route calculation device.
  • the map display data used to display the map on the monitor 18 does not need to introduce the concept of a mesh set.
  • the map display data simply needs to read the mesh data in the range corresponding to the display screen of the monitor 18. That is, if mesh data is stored in order, for example, in the east-west direction, it may be read out in that order.
  • route calculation data it is not always efficient to read mesh data arranged in a certain direction such as the east-west direction.
  • a mesh set is configured along the main road, it may be efficient when calculating the route.
  • the most suitable mesh set for route calculation is set according to the location.
  • the mesh set is set manually, for example, based on experience.
  • a certain rule may be set along a main road or a highway as described above, or set according to the administrative division of a prefecture or a municipality.
  • the route calculation data is managed by the concept of level, block, mesh set, and reference mesh. Route calculation data is prepared as mesh data for each reference mesh.
  • the block is managed by the block management table, and the mesh set in each block is managed by the mesh management table.
  • FIG. 5 is a diagram schematically showing the relationship between the block management table, the mesh management table, and mesh set data which is actual data.
  • mesh set data is a collection of mesh data of the reference mesh that constitutes the mesh set.
  • the block management table contains information about all blocks within that level. For example, in level 1 of Fig. 3, there are 16 blocks, and there are 16 corresponding block information. In level 2, the four blocks of level 1 are managed as one block, so there are four blocks and corresponding four block information.
  • Fig. 5 shows that there is one mesh management table per block.
  • the mesh set is managed by this mesh management table. For example, it manages access to the recording medium 2 and non-volatile memory 12 2 for acquiring the mesh set data, and correspondence of mesh sets between levels. More precisely, the mesh management table has information for managing the mesh set, and the control device 11 uses this table to manage the mesh set.
  • Fig. 6 shows the level 1 block management table.
  • the data size of the block management table (Nos. 1 to 23) is accommodated in No. 1 “Size of the block management table”. The size is expressed in terms of the number of words as 2 bytes per word.
  • Size of the block management table For item 2 “Number of block management information”, the number of The number of storage management information is accommodated.
  • Item numbers 3 to 6 contain numbers indicating the range of this block on the map in latitude and longitude. However, in the case of longitude, the value minus 1 0 0 from the longitude is stored, and in the case of latitude, the value obtained by multiplying the latitude by 3 Z 2 is stored.
  • Item 7 “Pointer to mesh management table” stores the identification information indicating whether the storage location of the mesh management table is on recording medium 2 or non-volatile memory 12 and its access address. Is done. This will be further described later.
  • Fig. 7 shows the contents of the mesh management table accessed by "Pointer to mesh management table" in the block management table.
  • the size of the mesh management table (items 1 to 7) is stored in No. 1 “Size of mesh management table”. The size is accommodated in words.
  • the number of reference meshes in the latitudinal direction managed in this table is stored in No. 2 “Reference number of meshes in the latitudinal direction”.
  • the value of n X 4 is accommodated. No. 3
  • the number of reference meshes in the longitude direction managed in this table is stored in the “number of reference meshes in the longitude direction”.
  • level 1 block 1 0 2 in Fig. 3 there are n reference meshes in the north-south direction, so there are n meshes in the “reference mesh management number in the latitudinal direction” and m meshes in the east-west direction. Therefore, m is accommodated in the “reference mesh management number in the longitude direction”.
  • Item Nos. 4 and 5 “Lower latitude” and “Left longitude” indicate the position of the lower left reference mesh that makes up the file management table described below. For latitude and longitude, the values obtained by the above calculation are stored.
  • the latitude representing the position of the reference mesh is, for example, the latitude on the lower side (south side) of the reference mesh
  • the longitude is, for example, the longitude on the left side (west side) of the reference mesh.
  • Item 6 “File management table category” indicates the type of file management table. For example, 0 is indicated for the background data only, and 1 is indicated when the route calculation data is managed by the mesh set.
  • the file management table of No. 7 contains information such as the size of each mesh set described below.
  • the lower left reference mesh is a reference mesh that represents a mesh set.
  • the mesh sets are managed in the order in which they are located from the left end (west end). In other words, the mesh set is managed in the order in which the lower left reference mesh is arranged based on the longitude and latitude directions.
  • the mesh (mesh set) data head pointer of No. 1 contains the address of the recording medium 2 of the leftmost mesh set data of each row. In the case of the bottom row; the address of the recording medium 2 to the mesh set recorded first in the block is stored.
  • Item 2 is the relative number of the lower left reference mesh of the core mesh. The relative number of the reference mesh is the number assigned to the block with the lower left reference mesh set to 1, in the row from left to right, and from the bottom row to the top row in ascending order.
  • Item 3 is the reference mesh number in the latitudinal direction in the core mesh.
  • Item number 4 is the number of reference meshes in the longitude direction in the core mesh.
  • the mesh set has a rectangular shape in the present embodiment. Therefore, the number of reference meshes constituting the core mesh can be calculated by multiplying the values of No. 3 and No. 4. If the core mesh is not rectangular, an approximate range of core mesh can be assumed from these values.
  • Item 5 is the lower latitude (the number of relative reference meshes from the lower left reference mesh in the core mesh) of the mesh set including the burlap mesh.
  • Item No. 6 is the leftmost longitude (number of relative reference meshes from the lower left reference mesh in the core mesh), including the top wrap mesh.
  • No. 7 is the reference mesh number in the latitudinal direction in the mesh set including the overwrap mesh (rectangular area). Area size).
  • Item 8 is the number of reference meshes (rectangular area size) in the longitude direction in the mesh set including the overwrap mesh.
  • Item 9 contains information indicating the storage location of the mesh set data. If the mesh set data has not been updated, information indicating that it is stored on the recording medium 2 is entered.
  • the storage address can be obtained by adding the contents of the mesh (mesh set) data head pointer of No. 1 and the mesh set data size stored sequentially. If the mesh set data has been updated, the fact that it is stored in the non-volatile memory 12 and its address are entered.
  • the update file name may be used instead of the address.
  • Item No. 10 is the connection / partial restriction mesh set data size.
  • Item No. 1 is the mesh set data size corresponding to the level.
  • No. 2 to No. 1 1 are management information (management data) of one mesh set.
  • No. 1 2 to No. 2 1 are management information of the right mesh set.
  • the management information of the mesh set on the right is followed.
  • the management information of the mesh set is stored from the left end (west end) to the right end (east end). Since the core mesh of the mesh set is composed of a plurality of reference meshes, there is a line in which no lower left reference mesh of any core mesh exists. There is no mesh set management information in such a row.
  • Fig. 24 is a diagram for explaining how mesh sets are managed using the file management table.
  • Reference numerals 3 0 1 to 3 0 9 denote core meshes of each mesh set.
  • the lower left reference mesh of the core mesh 3 0 1, 3 0 2, 3 0 3 is located in the lower end row.
  • the mesh set including the core mesh 3 0 1 is managed as the leftmost mesh set in the bottom row.
  • the mesh set on the right side is a mesh set including the core mesh 30 2, and the mesh set on the right side is including the core mesh 30 3.
  • In the bottom row + first row there is no data mesh in the file management table because there is no core mesh where the lower left reference mesh is located.
  • the mesh set including the core mesh 30 4 is managed as the lower end row + the left end mesh set in the second row.
  • the mesh set that includes the core mesh 30 5 is managed as the lower end row + the left end mesh set in the second row.
  • the mesh set that includes the core mesh 30 5 is managed from the left end.
  • the mesh set that includes the core mesh 3 06 is managed from the left end.
  • the mesh set that includes the core mesh 30 8 and the mesh set that includes the core mesh 30 9 are managed from the left end.
  • the mesh set data is a collection of mesh data of the reference mesh that constitutes the mesh set.
  • the route calculation data is managed as mesh data of each reference mesh.
  • the route calculation data is divided into connection / partial restriction data and inter-level correspondence data.
  • FIG. 9 is a diagram showing the mesh set data of the connection / partial restriction data.
  • the data block shown in FIG. 9 is stored in the recording medium 2 or the nonvolatile memory 12.
  • the number of reference meshes in No. 1 is the total number of reference meshes that make up the mesh set. This is the sum of the total number of reference meshes that make up the core mesh and the total number of reference meshes that make up the overlap mesh.
  • the reference mesh data will be placed after that many minutes.
  • Item 2 is the offset size to the reference mesh data. There are as many offset and size accommodation fields as the number of reference meshes.
  • No. 3 to No. 7 are the reference mesh data.
  • Mesh data of n reference meshes are arranged.
  • FIG. 10 is a diagram showing the contents of the reference mesh data of connection / partial restriction data
  • c item number 1 is a mesh code.
  • the mesh code is information for specifying each reference mesh, and is determined based on, for example, the latitude and longitude of the lower left corner. They can be obtained by the same calculation as the latitude / longitude mesh code of the block management table in Fig. 6, and they can be combined.
  • Item number 2 is mesh identification information. This information identifies whether the reference mesh data is the reference mesh in the core mesh or the reference mesh in the overlap mesh.
  • Item 3 is core mesh identification information. Used for overwrap mesh. At the same level, there may be multiple overlapping meshes used in multiple core meshes with the same mesh code.
  • Item No. 4 is route information list identification information. When attention is paid to the core mesh including the reference mesh, this is information indicating whether or not a route information list exists between adjacent core meshes. The route information list identification information will be further described later.
  • Item 5 is offset information. The offset information is the offset value up to the beginning of the partial regulation. That is, it corresponds to the size of the connection data.
  • Item 6 is the connection data.
  • Item No. 7 is partial restriction data. Partial restriction data is a collection of restriction information that can be set for each link.
  • FIG. 11 is a diagram showing details of connection part data of item number 6 in FIG.
  • roads are represented by the concept of links, nodes, and link strings.
  • a node is an intersection or a specific point on the road.
  • a link corresponds to a road between nodes, and a link string is a single road represented by multiple links.
  • Connection section data is connection information of this node. It consists of the local node information of a node existing on one link string and the adjacent node information of the node connected to that node. The local node information and adjacent node information store the position coordinates of the node.
  • the following information is added to the local node information in addition to the position coordinate information.
  • Fig. 12 shows the connection data part of the overlap mesh.
  • the overlap mesh connection data is the same as the core mesh connection data. There is no need. That is, the data may be coarser than the core mesh. Therefore, the mesh data of the reference mesh that constitutes the core mesh at the same position is copied, and a flag is set to enable or disable the own node.
  • the invalid node flag of No. 5's own node information 3 and No. 6's own node information 4 is turned on, and these data are thinned out. In this way, mesh data of an overlap mesh can be easily generated.
  • once a node is invalidated, it can be easily revalidated, so it is definitely easy to update data.
  • Figure 13 shows the mesh set data of the inter-level correspondence data.
  • the data cluster shown in Fig. 13 is stored in recording medium 2.
  • the connection / partial control data in Fig. 9 is stored after the mesh set data.
  • the contents of each item number are the same as in Figure 9.
  • Fig. 14 is a diagram showing the contents of the reference mesh data for the level correspondence data.
  • the mesh codes, mesh identification information, core mesh identification information, and offset information for items 1 to 4 are the same as in Fig. 10.
  • Item No. 5 is inter-level correspondence data.
  • FIG. 15 is a diagram showing details of the inter-level correspondence data of item number 5 in FIG.
  • Item No. 1 is the inter-level header.
  • Item number 2 is the number of supported levels.
  • the maximum number of correspondence to the lower level is set. Shows the maximum level of correspondence (existing position) of the lower level node corresponding to the own level node. Set the number of (lower) levels that describe the correspondence based on this level.
  • No. 3 to No. 7 are correspondence information. Correspondence information is provided for n nodes required for editing existing in the mesh at its own level.
  • Fig. 16 shows the details of each piece of correspondence information.
  • Item No. 1 is correspondence information of the corresponding own node
  • Item Nos. 2 to 7 are correspondence information of adjacent nodes connected to the corresponding own node.
  • the example in Fig. 16 is when m nodes are connected to a local node.
  • Fig. 17 shows the details of the node correspondence information.
  • Item No. 1 contains the number of adjacent nodes of the corresponding node. In the case of the local node in Figure 16 m is entered.
  • Item number 2 is self-level information. The node number at the corresponding level of the corresponding node is entered.
  • No. 3 to No. 6 Is lower level information. The number of corresponding levels set in item No. 2 in Fig.
  • the lower level information is arranged in order from the nearest level based on that level.
  • the lower level information stores the existing area at the lower level of the corresponding node and the own node number of the lower level.
  • the existence area is information that can identify the corresponding block and the corresponding reference mesh.
  • FIG. 18 is a diagram showing details of adjacent node correspondence information.
  • Item No. 1 contains the node number at the corresponding level of the adjacent node of the corresponding node.
  • Item No. 2 to Item No. 5 are lower level adjacency information. The number of corresponding levels set in item No. 2 in Fig. 5 is set, and the lower level information is arranged in order from the nearest level based on that level.
  • the lower-level adjacency information stores the lower-level existence area of the adjacent node of the corresponding node and the lower-level own node number.
  • the route information list is a list of previously calculated routes between mesh sets. In other words, route calculation (route search) between nodes included in a mesh set and nodes included in another mesh set is performed in advance, and the route with the lowest cost is selected and listed. Is.
  • the cost is a value that takes into account the distance of the route and other conditions.
  • the route information list is basically created for the combination of all mesh sets within that level.
  • the lower level that is, the level with detailed map data
  • processing time and output results become enormous if all mesh sets are created for each combination. Therefore, only the core meshes whose distance between the lower left reference meshes is within a predetermined distance should be created. For example, level 1 is created for the distance between the lower left reference meshes within 40 km, and level 2 is created for all combinations of mesh sets. These conditions may be changed as appropriate.
  • route information list identification information is provided in the reference mesh data. This route information list identification information is explained in more detail. Light up.
  • FIG. 19 is a diagram for explaining route information list identification information.
  • the core mesh of interest is core mesh X
  • core mesh X and core mesh a, c, e, b It is assumed that a route information list is created between them.
  • the mesh data of the reference mesh A of the core mesh X is as shown in Fig. 19 (b).
  • the route information list identification information of No. 4 contains information about the reference mesh adjacent to the reference mesh on the top, bottom, left, and right.
  • the upper reference mesh of the reference mesh A belongs to the core mesh d and there is no route information list between the core mesh X and the core mesh d, data without a route information list is entered. Since the lower reference mesh of the reference mesh A is in the own core mesh, NULL indicating that it is in the own core mesh is entered. Since the left reference mesh of reference mesh A is also in the own core mesh, N U L L is entered to indicate that it is in the own core mesh. 3 ⁇ 4
  • the right reference mesh of quasi-mesh A belongs to core mesh e, and since there is a route information list between core mesh X and core mesh e, data with a route information list with core mesh e is entered. . If there is a route information list, a pointer is entered so that the corresponding route information list can be referenced. Similarly, the mesh data of the reference mesh B of the core mesh X is as shown in Fig. 19 (c).
  • the route information list can be taken in, and the route calculation time can be shortened. In other words, by taking in the route information calculated in advance, route calculation such as Dijkstra method need not be performed each time, and the route calculation time can be shortened.
  • the map data is divided into seven levels with different scale ratios, the level of the most detailed scale ratio is set to level 0, and the level of the most extensive map is managed to level 6.
  • the route calculation data is Level 1, Level 2, Level Set on Bell 4.
  • the route calculation is basically performed using the route calculation data of the reference mesh of the adjacent core mesh at the same level.
  • route calculation is performed using the route calculation data in the upper level 2 on the way. .
  • route calculation is performed using route calculation data at higher level 4.
  • the route information list is used. For example, at level 1, even if the core meshes are separated, as described above, if there is a route information list within 40 Km between mesh sets, use it.
  • route calculation such as Dijkstra method is performed using the data of the mesh set to which the current location belongs. When it reaches the node of the over-wrap mesh, it goes up to level 2, which is the upper level, and further calculates the route. Similar processing is performed on the destination side. In level 2, there is a route information list as a rule, so the route with the lowest cost between the mesh set on the current location and the mesh set on the destination side that has been raised to level 2 is selected. If there is no route information list, route calculation is performed using the mesh set data of the level 2 mesh set. If necessary, the level is increased from the overlap mesh to upper level 4, and the route calculation is performed using the level 4 route calculation data. In this way, route calculation is performed, and the optimum route from the current location to the destination can be obtained.
  • level 2 which is the upper level
  • To raise to a higher level means to identify a higher level node corresponding to a lower level node and continue the route calculation from the identified higher level node.
  • To identify the higher-level node it is necessary to associate the lower-level node with the higher-level node. In order to make this correspondence, it is necessary to grasp the relationship (parent-child relationship) between the lower-level mesh set and the upper-level mesh set. For this association, the mesh set file management table described above is used in this embodiment.
  • the mesh set association between levels is the upper level that is located when the lower left reference mesh in the lower level core mesh is projected to the upper level. This is obtained by specifying the core mesh composed of the reference mesh.
  • FIG. 20 is a diagram for explaining the association of mesh sets between levels.
  • Reference mesh L 1 1 1 to L 1—1 7 constitutes a mesh set with level 1.
  • Reference mesh L 1-1 to 1: L 1-9 constitutes a core mesh, and reference mesh L 1 — 1 0 to: L 1 — 1 7 constitutes an overlap mesh.
  • Standard mesh L 2 ⁇ L 2—8 constitutes a mesh set with level 2.
  • the reference meshes L 2-1 to L 2-6 constitute the core mesh, and the reference meshes L 2-7 to L 2-8 constitute the overlap mesh.
  • the lower left lower reference mesh L 1—1 is included in the upper level reference mesh L 2—5, the lower left reference of the upper level core mesh including the reference mesh L 2—5 from the file management table. Find the mesh. This makes it possible to read the reference mesh in the upper level core mesh.
  • the relative number of the lower left reference mesh L1-1 itself is known.
  • the latitude and longitude information of the lower left reference mesh L 1 can be obtained by calculation.
  • the latitude and longitude information of the lower left reference mesh L1-1 can be grasped, it can be grasped which block it belongs to by referring to the upper level 2 block management table.
  • the mesh management table of the block can be referenced.
  • the nodes can be associated by searching the inter-level correspondence data in the mesh data of the reference mesh in the corresponding level 2 mesh set. In this way, the lower level 1 node and the upper level 2 node are associated with each other, and the route calculation can be performed from the lower level 1 to the upper level 2.
  • the lower left reference mesh of the lower level core set is based on which core set of the upper level belongs. Therefore, it is theoretically possible that the lower level core mesh is set to cross the boundary of the upper level core mesh. Basically, however, it is preferable to set the lower level core mesh to fit within the upper level core mesh. This allows the entire lower level core mesh to fit within a single higher level core mesh. —Use of per-wrap mesh
  • the lower level mesh set when raising from a lower level to an upper level, the lower level mesh set is raised from the burlap mesh.
  • the path calculation is performed up to the node of the upper lap mesh.
  • the mesh data of the reference mesh composing the core mesh at the same position is the mesh data of the reference mesh composing the burlap mesh. It is generated by thinning out the night.
  • an invalid node flag is provided in the own node information.
  • such a flag may not be provided, and only the node information necessary for the overlap mesh may be directly generated. By doing so, the data capacity of the mesh data of the overlapping lap mesh can be reduced.
  • the reference mesh Even if the reference mesh is located at the same position, it may become a reference mesh that constitutes an overlapping mesh of different mesh sets. In such a case, the mesh data for the overlapped mesh is generated differently by different mesh sets. In other words, the overlap mesh is generated by leaving only the necessary nodes according to the connection from the core mesh. Therefore, even if the same position is used, the route calculation data configured differs depending on which core mesh is adjacent to the overlap mesh. Of course, it may be the same data.
  • a mesh pattern for one-barlap mesh such as leaving only the main roads connected from the core mesh, such as main roads and expressways. This may be generated manually based on the experience of generating data for route calculation, or may be generated with the most efficient data by computer simulation. Further, as described above, the road type or the like may be determined and automatically generated based on certain rules. In addition, the link information necessary for the specification may be left from the core mesh data, and the unnecessary node may be generated by deleting the adjacent node information while leaving only the own node information.
  • FIG. 21 is a diagram for explaining how map data is updated and managed in the navigation device 1.
  • the navigation device 1 can update map data such as route calculation data in units of the mesh set described above.
  • the navigation device 1 reads the mesh management table and map data from the recording medium 2, and also reads the updated map data from the map server 6 via the removable memory 3 or Internet 5, and the latest map. Data can be used.
  • data is read only from recording media such as CD-ROM and DVD-ROM.
  • the map data in the recording medium 2 and the updated map data are mixed and used. For this reason, it has the non-volatile memory 12 which is a readable / writable medium.
  • the non-volatile memory 12 is composed of a non-volatile memory such as a hard disk or a flash memory, and the data is retained even when the navigation device is powered off.
  • the non-volatile memory 1 2 may be referred to as a cache medium 1 2.
  • the nonvolatile memory 12 includes the block management table 1 2 4 described with reference to FIG.
  • the block management table 1 24 has identification information as to whether the mesh management table of the corresponding block is on the recording medium 2 or the nonvolatile memory 12 and its access address.
  • the block management table stored in the recording medium 2 is read into the nonvolatile memory 12.
  • the mesh management table of each block is set on the recording medium 2.
  • a block mesh management table 1 2 5 having an updated mesh is created in the non-volatile memory 1 2, and the block management table 1 2 4 stores the corresponding block's
  • the cache management table is set in the non-volatile memory 12.
  • the program can determine whether the mesh management table is on the recording medium 2 or the nonvolatile memory 12 by referring to the block management table 1 2 4.
  • Reference numeral 1 2 6 is a memory in the memory 15 of the navigation device, and is an area for storing a mesh management table. Hereinafter referred to as memory 1 2 6.
  • the program After determining whether the mesh management table is on the recording medium 2 or the nonvolatile memory 12, the program reads the mesh management table from the corresponding media and stores it in the memory 1 26.
  • the mesh management table 1 2 7 read into the memory 1 2 6 has the mesh management information described in FIGS.
  • the map data for each mesh set is updated in the rim bubble memory 3
  • the map data of the mesh set is read into the nonvolatile memory 12 and stored as the map data 1 3 3.
  • the mesh management table on the non-volatile memory 1 2 is used.
  • write that the mesh set data of this mesh set is stored in the non-volatile memory 12 and its address. If the data size of the mesh set data has been changed, rewrite the contents of item numbers 10 and 11. Other items do not need to be rewritten by updating. Thereafter, the nonvolatile memory 12 can be accessed based on this content. That is, the map data of the mesh set that has not been updated can access the recording medium 2, and the updated mesh set map data can access the nonvolatile memory 12.
  • FIG. 22 is a flowchart of control in which the control device 11 reads the route calculation data and performs route calculation.
  • step S 1 the current location of the vehicle is detected using the current location detection device 13.
  • step S2 the destination specified by the user using the input device 19 is set.
  • step S3 the mesh set data of the necessary mesh set around the current position and destination of the vehicle is read.
  • step S4 route calculation (route search) is performed using Dijkstra method.
  • step S5 it is determined whether all the route calculations are completed. In other words, it is determined whether or not the route calculation from the current location to the destination location has been completed. If it is determined in step S5 that the process has not been completed, the process returns to step S3, and the mesh set data of the necessary mesh set is read and the path calculation is continued. If it is determined in step S5 that the route calculation has been completed, the process is terminated. While repeating steps S3 to S5, connect to the above-mentioned higher level as necessary.
  • FIG. 23 is a diagram showing a detailed flowchart of the processing in step S 3 in FIG.
  • step S 2 the block management table in the nonvolatile memory 1 2 is accessed. In this case, it is assumed that the block management table has already been read into the nonvolatile memory 12.
  • step S 2 2 based on the contents of the book management table, it is determined whether the file management table of the corresponding block is on the recording medium 2 or the nonvolatile memory 12. If it is determined in step S 2 2 that the recording medium 2 exists, the process proceeds to step S 2 3.
  • step S 2 3 the file management table of the corresponding block is read from the recording medium 2 into the memory 1 2 6 ( On the other hand, if it is determined in step S 2 2 that it is not on the recording medium 2, that is, it is on the nonvolatile memory 12, the process proceeds to step S 2 4.
  • step S 24 the file management table of the corresponding block is read from the nonvolatile memory 12 into the memory 1 26.
  • step S 2 5 the storage address of the corresponding mesh set is calculated based on the contents of the file management table read into memory 1 2 6.
  • step S 26 the mesh set data is read from the calculated storage location. In this case, if the mesh set data is not updated, the data is read from the recording medium 2 in units of mesh sets. When the mesh set data is updated, the data is read from the nonvolatile memory 12.
  • the route calculation data stored in the recording medium 2 is managed by introducing the concept of a mesh set composed of multiple reference meshes. As a result, it is possible to continuously read data from the recording medium 2 with a cluster of data suitable for route calculation. As a result, compared to reading out data managed in units of meshes for each mesh, the number of seeks on the read head of the DVD drive unit is drastically reduced, resulting in faster processing.
  • a file management table for managing mesh sets is provided.
  • the mesh set association (parent-child relationship) between levels can be easily grasped simply by referring to the file management table.
  • no special table is required.
  • map data such as route calculation data can be updated on a mesh set basis, when only a part of the map data is updated, the entire recording medium such as DVD-ROM that stores the map data is updated. There is no need to do.
  • the minimum update unit is the mesh set unit, which reduces the amount of communication (cost) required for unnecessary data updates. You can.
  • the update data can be managed easily and reliably. This facilitates the development of navigation device programs.
  • control program executed by the control device 11 of the navigation device has been described as being stored in the ROM, but it is not necessary to limit to this content.
  • the control program and its installation program may be provided on a recording medium such as DVD.
  • the recording medium need not be limited to D V D, and C D—R O M, magnetic tape, or any other recording medium may be used.
  • the program can be converted into a signal on a carrier wave carrying the transmission medium and transmitted.
  • the program may be provided in the same configuration as in Figure 1.
  • the recording medium 2 may be a program-provided recording medium
  • the map server 6 may be a server that provides an application program. In this way, the program can be supplied as computer-readable computer program products in various forms such as a recording medium and a carrier wave.
  • control program may be executed on a personal computer to realize a powerful navigation device.
  • the current location detection device 13 and the input device 19 may be connected to a predetermined I / O port of the personal computer.
  • update data may be written on a CD-ROM or DVD-ROM, and the recording medium 2 may be temporarily replaced and provided.
  • Initial map data may be received via the Internet 5 and stored in the non-volatile memory 12, and then updated and managed by the method described above.
  • the necessary map data can be received via the Internet 5 each time and stored in the non-volatile memory 12 each time. If there is an update thereafter, update management may be performed using the method described above.
  • the map data can be supplied as a map data product that can be read by various types of computers such as recording media and carrier waves, and navigation devices (map data processing devices).
  • the example in which the route calculation data is managed using the concept of mesh setting has been described.
  • the processing speed, such as data reading may be improved.
  • the concept of mesh setting can be used in other map designs.
  • the example in which the nonvolatile memory 12 is provided in the navigation device 1 has been described.
  • the present invention is not limited to this. It may be an external storage device connected by a cable or the like.

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Educational Administration (AREA)
  • Educational Technology (AREA)
  • Databases & Information Systems (AREA)
  • Business, Economics & Management (AREA)
  • Mathematical Physics (AREA)
  • Automation & Control Theory (AREA)
  • Navigation (AREA)

Abstract

コンピュータあるいは地図データ処理装置に読み込み可能なデータ製品は、地図に関する情報を有する地図データを有する。該地図データは、地図をメッシュ状の複数の区画に分割し、分割した区画単位に対応させて地図に関する情報を分割した構造と、地図に関する情報を、隣接する区画を複数集めた区画セット単位で管理し、区画セット単位で地図データ処理装置により処理される構造とを備える。

Description

明細書 地図データ製品および地図データ処理装置 次の優先権基礎出願の開示内容は引用文としてここに組み込まれる。
日本国特許出願 2 0 0 2年第 2 2 0 9 2 2号 （ 2 0 0 2年 7月 3 0 日出願） 日本国特許出願 2 0 0 2年第 2 2 0 9 2 3号 （2 0 0 2年 7月 3 0 日出願） 技術分野
本発明は、 地図データ製品および地図データ処理装置に関する。 背景技術
経路計算をし、 推奨経路を表示してナビゲーションを行うナビゲーション装置 が知られている。 経路計算に使用される経路計算用データは、 地図をメッシュ状 に分割した単位で管理することも知られている。 また、 経路計算用デ一夕を縮尺 率の異なる複数のレベルに分けて管理し、 経路計算にあたり複数のレベルの経路 計算用データを使い分けることも知られている。 発明の開示
しかし、 メッシュ状に分割した単位で経路計算用デ一夕を読み出すと、 読み出 し装置の読み出しへッドのシーク回数が増え、 読み出し時間がかかるという問題 が生じていた。
本発明は、 記録媒体などで提供される地図データを効率よく読み出すことが可 能なようにした地図データ製品および地図データ処理装置を提供する。
本発明のコンピュータあるいは地図データ処理装置に読み込み可能なデータ製 品は、 地図に関する情報を有する地図データを有する。 該地図データは、 地図を メッシュ状の複数の区画に分割し、 分割した区画単位に対応させて地図に関する 情報を分割した構造と、 地図に関する情報を、 隣接する区画を複数集めた区画セ ッ ト単位で管理し、 区画セッ ト単位で地図データ処理装置により処理される構造 とを備える。
このデータ製品において、 区画セッ トは、 他の区画セッ トとの間で重複しない 1以上の区画からなるコア区画と、 他の区画セッ トのコア区画に該当する 1以上 の区画からなるオーバ一ラップ区画とから構成されるのが好ましい。
また、 ォ一パーラップ区画に対応する地図に関する情報は、 他の区画セッ トの コア区画に対応する地図に関する情報から間引いて生成されるのが好ましい。 こ の場合、 地図に関する情報は、 経路計算に使用される地図上の経路に関する情報 であり、 道路の交差点をノードとし、 地図上の経路に関する情報は、 1本の道路 上に存在する複数のノードの自ノード情報とそれぞれの自ノードに接続されるノ 一ドの隣接ノード情報とからなり、 コア区画に対応する地図上の経路に関する情 報は、 自ノード情報と隣接ノード情報とから構成され、 オーバーラップ区画に対 応する地図上の経路に関する情報は、 コア区画に対応する地図上の経路に関する 情報から、 所定のノードの隣接ノード情報を削除して生成されているのが好まし い。
また、 区画セッ トに対応する地図に関する情報は、 記録媒体上に 1つのかたま りとして連続して記録される構造であるのが好ましい。
また、 地図に関する情報は、 さらに、 区画単位で地図データ処理装置により処 理可能な構造を備えるのが好ましい。
また、 区画セッ ト単位の地図に関する情報の管理情報を有する構造をさらに備 え、 地図データ処理装置が取得した地図に関する情報は、 管理情報を使用して、 区画セッ ト単位で更新可能であるのが好ましい。
また、 地図に関する情報は、 経路計算に使用される地図上の経路に関する情報 であるのが好ましい。
本発明の他のコンピュータあるいは地図データ処理装置に読み込み可能なデー 夕製品は、 地図に関する情報を有する地図データを有する。 該地図データは、 地 図をメッシュ状の複数の区画に分割し、 分割した区画単位に対応させて地図に関 する情報を分割した構造と、 地図に関する情報を、 隣接する区画を複数集めた区 画セッ ト単位で管理し、 区画セッ ト単位で地図データ処理装置により処理される 構造とを備え、 区画セットは、 第 1の区画と、 第 1の区画に隣接する 1以上の区 画からなり、 第 1の区画に対応する地図に関する情報は、 分割された地図に関す る情報からなり、 第 1の区画に隣接する 1以上の区画に対応する地図に関する情 報は、 分割された地図に関する情報から間引いて生成された情報からなる。
本発明の他のコンピュータあるいは地図データ処理装置に読み込み可能なデー タ製品は、 地図に関する情報を有する地図デ一夕を有する。 該地図データは、 縮 尺率が異なる複数のレベル単位で地図に関する情報を備えた構造と、 各レベル毎 に、 地図をメッシュ状の複数の区画に分割し、 分割した区画単位に対応させて地 図に関する情報を分割した構造と、 地図に関する情報を、 隣接する区画を複数集 めた区画セッ ト単位で管理し、 区画セッ ト単位で地図データ処理装置により処理 される構造と、 各レベル内において、 区画セッ トを管理する情報を有する管理テ 一ブルを備える構造とを備え、 管理テーブルは、 各レベルの区画セッ トのレベル 間の対応関係を演算により求めることが可能な情報を有する。
このデータ製品において、 管理テーブルは、 区画セッ トを代表する基準区画の 位置を表す情報と、 区画セッ トの分割たて方向の数に関する情報と、 分割横方向 の数に関する情報とを有するのが好ましい。 この場合、 区画セッ トは矩形形状を 有し、 区画セッ トを代表する基準区画は、 区画セッ トの左下に位置する区画であ るのが好ましい。 さらに、 この場合、 区画セッ トを管理する情報は、 区画セッ ト を代表する基準区画が分割横方向および分割たて方向を基準として並ぶ順序で格 納されるのが好ましい。
また、 各レベル内において、 地図をメッシュ状の複数のブロックに分割し、 複 数の区画は、 各ブロックをさらに分割して得られた区画であり、 管理テーブルは、 各ブロック毎に設けられるのが好ましい。
また、 地図データ処理装置が取得した地図に関する情報は、 管理テーブルを使 用して、 区画セッ ト単位で更新可能であるのが好ましい。
また、 地図上の道路の交差点をノードとし、 地図に関する情報はノードに関す る情報を有し、 区画単位に分割した地図に関する情報は、 該区画内のノードと他 のレベルの対応するノードとのレベル間ノ一ド対応情報をさらに有し、 区画セッ 卜のレベル間の対応関係と区画セッ トを構成する区画のレベル間ノード対応情報 を使用して、 ノードのレベル間の対応関係を把握することが可能であるのが好ま しい。
また、 地図に関する情報は、 経路計算に使用される地図上の経路に関する情報 であるのが好ましい。
上記のデータ製品は、 地図データが記録された記録媒体であるのが好ましい。 本発明の地図データ処理装置は、 上記記録媒体を搭載する記録媒体駆動部と、 記録媒体に記録された地図データに基づき、 地図デ一夕の処理を行う処理部とを 備える。
この地図データ処理装置において、 地図に関する情報は経路計算に使用される 地図上の経路に関する情報であるとき、 処理部は、 記録媒体に記録された地図上 の経路に関する情報に基づき、 経路計算を行うのが好ましい。 図面の簡単な説明
図 1は、 地図データの授受について説明する図である。
図 2は、 車載用ナビゲ一シヨン装置のブロック図である。
図 3は、 地図データのレベル、 ブロック、 メッシュの関係を説明する概念図で ある。
図 4は、 メッシュセッ トの概念を説明する図である。
図 5は、 プロック管理テ一ブルとメッシュ管理テーブルと実際のデータである メッシュセッ トデ一夕との関係を概略的に示す図である。
図 6は、 ブロック管理テーブルを示す図である。
図 7は、 メッシュ管理テーブルの内容を示す図である。
図 8は、 ファイル管理テーブルを詳細に示す図である。
図 9は、 接続 ·部分規制データのメッシュセッ トデ一夕を示す図である。 図 1 0は、 接続 · 部分規制データの基準メッシュデータの内容を示す図である 図 1 1は、 接続部データの詳細を示す図である。
図 1 2は、 オーバーラップメッシュの接続データ部を示す図である。
図 1 3は、 レベル間対応データのメッシュセッ トデータを示す図である。 図 1 4は、 レベル間対応データの基準メッシュデータの内容を示す図である。 図 1 5は、 レベル間対応データの詳細を示す図である。 図 1 6は、 対応情報の詳細を示す図である。
図 1 7は、 自ノード対応情報の詳細を示す図である。
図 1 8は、 隣接ノード対応情報の詳細を示す図である。
図 1 9は、 経路情報リスト識別情報について説明する図である。
図 2 0は、 レベル間におけるメッシュセッ トの関連付けを説明する図である。 図 2 1は、 ナビゲーション装置での地図データの更新管理の様子を説明する図 である。
図 2 2は、 経路計算用データを読み込んで経路計算を行う制御のフローチヤ一 トを示す図である。
図 2 3は、 図 2 2のステップ S 3の処理の詳細なフローチヤ一トを示す図であ る。
図 2 4は、 メッシュセッ トをファイル管理テーブルで管理する様子を説明する ための図である。 発明を実施するための最良の形態
図 1は、 本実施の形態において、 地図表示用データや経路計算用デ一夕などの 地図データの授受について説明する図である。 車載用ナビゲ一シヨン装置 1は、 C D— R O Mや D V D— R O Mなどの記録媒体 2から、 地図データや管理情報や 案内検索データなどを読み取る。 リムーバブルメモリ 3からは、 地図データなど の更新データの提供を受ける。 リム一バブルメモリ 3は、 地図デ一夕の一部を更 新するために更新データ等が記録された取り替え可能な記録媒体である。
また、 ナビゲーシヨン装置 1は、 携帯電話などの通信装置 4とも接続可能であ る。 ナビゲーシヨン装置 1は、 通信装置 4を介してインタネッ ト 5に接続し、 さ らにィン夕一ネッ ト 5を介して地図サーバ 6に接続することができる。 地図サー バ 6は、 古い地図データから最新の地図データまでを地図データベース 7に保有 し、 また、 せい案内検索データから最新の案内検索データまでを案内検索データ ベース 8に保有する。 従って、 地図サーバ 6は、 地図データの一部を更新する更 新データをィンタ一ネッ ト 5を介してナピゲ一ション装置 1に提供することがで きる。 なお、 案内検索データとは、 P O I等の位置情報、 種別、 名称等の属性情 報を格納したデータである。
ナビゲーシヨン装置 1は、 制御装置 1 1と不揮発性メモリ 1 2を有する。 制御 装置 1 1は、 マイクロプロセッサおよびその周辺回路から構成される。 不揮発性 メモリ 12は、 ナピゲ一ション装置 1の内部に設けられたハードディスクゃフラ ッシュメモリなどの不揮発性メモリである。 不揮発性メモリ 1 2は、 ナビゲーシ ョン装置 1の電源が落とされても、 書きこまれたデータが消えない記憶装置であ ればどのようなものでもよい。
記録媒体 2は、 一旦ナビゲ一シヨン装置 1に搭載すると、 新たな記録媒体 2と 入れ替えない限りナピゲーション装置 1に搭載したままの状態となる。 従って、 リム一バブルメモリ 3に対して固定メディァと称してもよい。 地図データベース 7や案内検索データベース 8は、 新旧すベての地図データや案内検索データなど を有しているためマザ一データのデータベースである。 地図サーバ 6は、 地図デ 一夕ベース 7や案内検索データベース 8を使用して、 初期の （更新前の） 地図デ —夕などを有する記録媒体 2や、 更新用データを有するリムーパブルメモリ 3を 準備することができる。
図 2は、 車載用ナビゲ一シヨン装置 1のブロック図である。 ナビゲ一シヨン装 置 1は、 制御装置 1 1、 不揮発性メモリ 1 2、 現在地検出装置 1 3、 DVD駆動 装置 14、 メモリ 1 5、 通信インタ一フェース 1 6、 リム一バブルメモリ読込装 置 1 7、 モニタ 1 8、 入力装置 1 9を有する。
現在地検出装置 1 3は車両の現在地を検出する現在地検出装置であり、 例えば 車両の進行方位を検出する方位センサや車速を検出する車速センサや G P S (G1 obal Positioning System) 衛星からの GP S信号を検出する GP Sセンサ等から 成る。 DVD駆動装置 1 4は、 記録媒体 2を搭載して地図データなどを読み込む 装置である。 本実施の形態では、 記録媒体 2は D VD— R OMとする。 なお、 C D— ROMや他の記録媒体であってもよい。
メモリ 1 5は、 現在地検出装置 1 3によって検出された車両位置情報等を格納 したり、 制御装置 1 1が演算した推奨経路上のノード情報やリンク情報等を格納 するメモリである。 さらに、 後述するメッシュ管理テーブルを格納したりもする。 メモリ 1 5は制御装置 1 1のワーキングエリアである。 通信ィンタ一フェース 1 6は、 通信装置 4を接続するインタ一フェースである。 通信インターフェース 1 6を介して携帯電話の利用や、 インターネッ トとの接続が可能である。 リム一バ ブルメモリ読込装置 1 7は、 リムーバブルメモリ 3を装填しリムーバブルメモリ 3からデータを読み込むことが可能な装置である。
モニタ 1 8は、 地図や推奨経路や各種情報を表示する表示装置である。 モニタ 1 8は、 ナビゲーシヨン装置本体の一部として一体に設けてもよいし、 筐体とし ては別々に設けてもよい。 さらに、 モニタ 1 8のみを、 ナビゲ一シヨン装置本体 とケーブルなどによって接続し、 分離した位置に設けるようにしてもよい。 入力 装置 1 9は、 経路探索時に車両の目的地等を入力したりする入力装置である。 リ モコンであってもよいし、 モニタ 1 8の画面上に設けられた夕ツチパネルなどで 構成してもよい。 制御装置 1 1は、 現在地検出装置 1 3で検出された車両の現在 地情報と記録媒体 2や不揮発性メモリ 1 2に格納された地図データなどを使用し て、 道路地図の表示、 経路計算 （経路探索） 、 経路誘導等の各種のナビゲーショ ン処理を行う。 なお、 制御装置 1 1が実行する各種の処理プログラムは、 制御装 置 1 1内部に設けられた R O M (不図示） に組み込まれている。
一地図データの構造—
上述した地図デ一夕のデータ構造について、 さらに詳しく説明する。 地図デ一 夕は、 地図に関する情報であり、 背景 （地図表示用） データ、 ロケ一夕用データ、 経路計算用データ、 誘導データ （交差点名称 ·道路名称 ·方面名称 ·方向ガイ ド 施設情報など） などである。 背景データは道路や道路地図の背景を表示するため のデータである。 ロケータ用データは、 車両の現在地の特定やマップマッチング などに使用されるデータである。 経路計算用データは、 道路形状とは直接関係し ない分岐情報などから成るネッ トワークデータであり、 主に推奨経路を演算 （経 路探索） する際に用いられる。 誘導データは、 交差点の名称などから成るデータ であり、 演算された推奨経路に基づき運転者等に推奨経路を誘導する際に用いら れる。
本実施の形態の地図データは、 レベル、 ブロック、 メッシュという概念で管理 する。 本実施の形態では、 地図データを縮尺率が異なる 7つのレベルに分け、 最 詳細の縮尺率のレベルをレベル 0とし、 最広域地図のレベルをレベル 6とする。 各レベルは縮尺率が異なる地図デ一夕を含むものであるが、 対象となる領域は各 レベルとも同じである。 すなわち、 日本全土が対象であると、 各レベルごとに縮 尺率が異なる日本全土の地図データを有する。 例えば、 レベル 0では縮尺率 1 / 6 2 5 0、 レベル 1では縮尺率 1 / 2 5 0 0 0、 レベル 2では縮尺率 1ノ 1 0 0 0 0 0、 レベル 3では縮尺率 1 / 4 0 0 0 0 0、 レベル 4では縮尺率 1 / 1 6 0 0 0 0 0、 レベル 5では縮尺率 1 / 6 4 0 0 0 0 0、 レベル 6では縮尺率 1 Z 1 2 8 0 0 0 0 0 0の日本全土の地図データを有する。 すなわち、 レベル 0〜 6に 対応して 7つの地図データのセッ 卜がある。
図 3は、 地図データのレベル、 プロック、 メッシュの関係を説明する概念図で ある。 代表して、 レベル 1 と 2を示している。 符号 1 0 1は、 本地図データの対 象となる領域を示す。 日本全土の地図データを扱うとすると、 領域 1 0 1は日本 全土を含む範囲となる。 レベル 1もレベル 2も同じ範囲の領域を対象としている。 レベル 1では、 領域 1 0 1は、 4 X 4 = 1 6の複数のプロック 1 0 2に分けられ て管理される。 一つのブロック 1 0 2は、 複数のメッシュ 1 0 3に分けられて管 理される。 本実施の形態では、 m X n枚のメッシュで管理する。 各プロック 1 0 2間の分割メッシュの数は、 同じレベルでは同一数 m X nである。
レベル 2では、 領域 1 0 1は、 2 X 2 = 4の複数のプロック 1 0 4に分けられ て管理される。 一つのブロック 1 0 4は、 複数のメッシュ 1 0 5に分けられて管 理される。 本実施の形態では、 p X q枚のメッシュで管理する。 各ブロック 1 0 4間の分割メッシュの数は、 同じレベルでは同一数 p X qである。
レベル 1とレベル 2では、 領域 1 0 1を分割したブロックの数、 各ブロックを 分割したメッシュの数は異なる。 これは、 縮尺率の小さい （分母の値が大きい） より広域地図を扱うレベル 2と、 レベル 2に比べて縮尺率の大きい (分母の値が 小さい） より詳細地図を扱うレベル 1 とでは、 扱うデータ量も異なるためである ( すなわち、 各レベルにおいて扱うデータ量に応じた適切な分割を行うようにして いる。 ただし、 同一レベル内では、 1つのブロックの大きさおよび 1つのメッシ ュの大きさは同じである。 なお、 図 3の各レベルの分割ブロック数は、 1例であ り、 必ずしもこの数に限られるものではない。
上記分割のたて方向は緯度方向に対応し、 横方向は経度方向に対応する。 上記 ブロック、 メッシュの呼び名は、 本実施の形態で便宜上名づけたものである。 従 つて、 必ずしもこれらの名称に限定されるものではない。 メッシュをパ一セルと 言ってもよいし、 ブロックを第 1の分割単位、 メッシュを第 2の分割単位と言つ てもよい。 また、 これらのブロック、 メッシュは地理的に分割された単位と言つ てもよい。
一経路計算用デーダ一
以下、 地図データのうち経路計算用データについて説明する。 経路計算用デー 夕は、 上述したようにメッシュ単位に分割され管理される。 本実施の形態では、 さらにメッシュセッ トという概念を導入する。
図 4は、 メッシュセッ トの概念を説明する図である。 符号 2 0 1は前述したメ ッシュである。 以下、 各メッシュを基準メッシュと言う。 基準メッシュ 2 0 1を 複数集めた単位をコアメッシュ 2. 0 2と言う。 図 4の例では、 お互いに隣接する 基準メッシュ 2 0 1が 6枚集められてコアメッシュ 2 0 2を構成している。 コァ メッシュ 2 0 2の回りには、 破線で示された基準メッシュ 2 0 1が適宜配置され ている。 これをオーバーラップメッシュ 2 0 3 と言う。 このコアメッシュ 2 0 2 とオーバ一ラップメッシュ 2 0 3を合わせてメッシュセッ ト 2 0 4を構成する。 コアメッシュ 2 0 2を構成する基準メッシュ 2 0 1の枚数は、 メッシュセッ ト 2 0 4によって異なる。 図 4の例では 6枚であるが、 1枚あるいは複数の基準メ ッシュ 2 0 1でメッシュセッ ト 2 0 4が構成される。 また、 コアメッシュ 2 0 2 の形状は、 本実施の形態では、 矩形状 （4角形） とする。 ただし、 矩形状のみな らず L字状等の形状であってもよい。 すなわち、 複数の隣接する基準メッシュ 2 0 1で構成されるあらゆる形状のメッシュセッ ト 2 0 4であってもよい。 ただし 矩形状が最も好ましい。
コアメッシュ 2 0 2は、 プロック内において重複することなくまた隙間があく ことなく設定される。 コアメッシュ 2 0 2周辺に設定されるォ一バーラップメッ シュ 2 0 3は、 他のメッシュセッ トのコアメッシュを構成する基準メッシュと重 複する。 また、 他のメッシュセッ トのオーバ一ラップメッシュを構成する基準メ ッシュと重複する場合もある。 また、 基準メッシュ 1枚のコアメッシュと 1また は複数の基準メッシュからなるオーバーラップメッシュとで構成されるメッシュ セッ 卜もある。
各基準メッシュに対応するデータをメッシュデータと言う。 経路計算用データ は、 基準メッシュのメッシュデータとして管理される。 オーバーラップメッシュ を構成する基準メッシュのメッシュデ一夕は、 対応する他のメッシュセッ トのコ ァメッシュを構成する基準メッシュのメッシュデ一夕からデータを間引いて生成 される。 すなわち、 オーバ一ラップメッシュのメッシュデータは、 コアメッシュ のメッシュデータより少ない、 粗いデ一夕で構成される。 詳細は、 さらに後述す る。
このようにして、 経路計算用データは、 基準メッシュ単位で管理され、 さらに メッシュセッ ト単位で管理される。 メッシュセッ ト単位で管理される経路計算用 データは、 記録媒体 2にメッシュセッ ト単位で格納される。 メッシュセッ ト単位 で記録媒体 2に格納された経路計算用データは、 記録媒体 2からメッシュセッ ト 単位で連続的に読み出すことが可能となる。 これにより、 メッシュ単位で管理さ れたデータをメッシュ毎に読み出すことに比べ、 D V D駆動装置の読み取りへッ ドのシーク回数が激減し、 処理の高速化が実現される。 メッシュセッ ト単位のデ 一夕は、 基本的にはコアメッシュのデ一夕、 オーバーラップメッシュのデータの 順に格納する。 また、 アプリケーションによっては、 メッシュセッ トを構成する 任意の基準メッシュの位置からメッシュデータを読み出すことも可能である。 なお、 本実施の形態では、 上述したように経路計算用デ一夕に対してメッシュ セッ 卜の概念を導入している。 モニタ 1 8に地図を表示するために使用される地 図表示用データでは、 特にメッシュセッ トの概念を導入する必要はない。 これは、 地図表示用データは、 単にモニタ 1 8の表示画面に対応した範囲のメッシュデ一 夕を読み込むだけでよい。 すなわち、 メッシュデータが例えば東西方向に順に並 んで格納されていれば、 順次その順番で読み出せばよい。
しかし、 経路計算用データでは、 必ずしも、 東西方向などの一定方向に並ぶメ ッシュデータを読み込んでも効率が良いとは限らない。 例えば、 幹線道路に沿つ てメッシュセッ トを構成しておけば、 経路計算時に効率がよい場合がある。 本実 施の形態では、 経路計算に最も適したメッシュセッ トを、 場所場所に応じて適宜 設定していく。 メッシュセッ トの設定は、 例えば、 経験をベースに人手により設 定してもよいし、 あるいは、 コンピュータのシミュレーションによりもつとも効 率のよい構成を設定してもよいし、 また、 一定の法則により設定するようにして もよい。 一定の法則とは、 例えば上述したように幹線道路や高速道路に沿って設 定したり、 県や市町村の行政区画に対応して設定したりすればよい。
—メッシュセッ 卜の管理一
次に、 上述したメッシュセッ トの管理について説明する。 経路計算用データは、 上述した通り、 レベル、 ブロック、 メッシュセッ ト、 基準メッシュという概念で 管理される。 各基準メッシュのメッシュデータとして経路計算用データが準備さ れる。 簡単に言うとブロック管理テーブルによりブロックを管理し、 メッシュ管 理テーブルにより各ブロック内におけるメッシュセッ トを管理する。
図 5は、 プロック管理テ一ブルとメッシュ管理テーブルと実際のデータである メッシュセッ トデータとの関係を概略的に示す図である。 ここで、 メッシュセッ トデ一夕とは、 メッシュセッ トを構成する基準メッシュのメッシュデータの集ま りである。 まず、 レベル Xのデータには 1つのブロック管理テーブルがあること を示している。 ブロック管理テーブルには、 そのレベル内におけるすべてのプロ ックに関する情報がある。 例えば、 図 3のレベル 1では 1 6枚のブロックがあり， 対応する 1 6個のブロック情報がある。 レベル 2では、 レベル 1の 4枚のブロッ クが 1枚のブロックとして管理されるため、 4枚のブロックがあり、 対応する 4 個のブロック情報がある。 図 5ではさらに、 1枚のブロックに 1つのメッシュ管 理テーブルがあることを示している。
このメッシュ管理テーブルによりメッシュセッ トを管理する。 例えば、 メッシ ュセッ トデータを取得するための記録媒体 2や不揮発性メモリ 1 2へのアクセス や、 レベル間のメッシュセットの対応関係などを管理する。 正確に言うと、 メッ シュ管理テーブルはメッシュセッ トを管理するための情報を有し、 制御装置 1 1 がこのテーブルを使用してメッシュセッ トを管理する。
図 6は、 レベル 1のブロック管理テーブルを示す図である。 項番 1の 「プロッ ク管理テーブルのサイズ」 には、 ブロック管理テーブル （項番 1〜 2 3まで） の データサイズが収容される。 サイズは 2パイ ト 1ワードとしてワード数で表現さ れる。 項番 2の 「ブロック管理情報の数」 には、 ブロック管理テーブル内のプロ ック管理情報の数が収容される。 レベル 1では図 3にも示した通り 1 6枚のプロ ックが存在するので 1 6が収容される。 項番 3 ~ 6には、 このブロックの地図上 の範囲を緯度および経度で示す数字が収容される。 ただし、 経度の場合は経度か らマイナス 1 0 0 した値が収容され、 緯度の場合は緯度に 3 Z 2を掛けた値が収 容される。 例えば、 東経 1 3 6度の場合は 3 6が収容され、 北緯 3 3度 2 0分の 場合は （ 3 3 + 2 0 / 6 0 ) X ( 3 / 2 ) = 5 0が収容される。 項番 7の 「メッ シュ管理テーブルへのポインタ」 には、 メッシュ管理テーブルの格納先が記録媒 体 2上にあるか不揮発性メモリ 1 2上にあるかの識別情報と、 そのアクセスァド レスが格納される。 この内容については、 さらに後述する。
図 7は、 ブロック管理テーブルの 「メッシュ管理テ一ブルへのポインタ」 でァ クセスされるメッシュ管理テ一ブルの内容を示す図である。 項番 1の 「メッシュ 管理テーブルのサイズ」 には、 メッシュ管理テーブル （項番 1〜 7まで） のデー 夕サイズが収容される。 サイズはワード数で収容される。 項番 2の 「緯度方向の 基準メッシュ管理数」 には、 本テーブルで管理される緯度方向の基準メッシュ数 が収容される。 図 3のレベル 1の例では、 n X 4の値が収容される。 項番 3の
「経度方向の基準メッシュ管理数」 には、 本テーブルで管理される経度方向の基 準メッシュ数が収容される。 図 3のレベル 1のブロック 1 0 2を考えた場合、 南 北方向に n枚の基準メッシュがあるので 「緯度方向の基準メッシュ管理数」 には n、 東西方向には m枚のメッシュがあるので 「経度方向の基準メッシュ管理数」 には mが収容される。
項番 4、 5の 「下端緯度」 「左端経度」 には次に説明するファイル管理テープ ルを構成する左下基準メッシュの位置を示す。 緯度、 経度については前述した計 算により求められる値が収容される。 なお、 基準メッシュの位置を表す緯度とは 例えば基準メッシュの下側 （南側） の緯度であり、 経度とは例えば基準メッシュ の左側 （西側） の経度である。 項番 6の 「ファイル管理テーブル区分」 とはファ ィル管理テーブルの種類を示す。 例えば、 背景データのみの場合は 0で示し、 経 路計算用データをメッシュセッ 卜で管理する場合は 1で示される。 項番 7のファ ィル管理テーブルは次に説明する各メッシュセッ トのサイズ等の情報が収容され る。 図 8は、 上述した区分 1の場合のファイル管理テーブルを詳細に示す図である。 東西方向の基準メッシュの並びを 1行として下端行から上端行の順に管理する。 各行内においては、 左端 （西端） から順に右端 （東端） までの順に管理する。 た だし、 メッシュセッ トは複数の基準メッシュから構成されているので、 各メッシ ュセッ 卜のコアメッシュの左下基準メッシュがどの位置かによってメッシュセッ トを管理する。 すなわち、 あるメッシュセッ トのコアメッシュの左下基準メッシ ュが下端行に位置すれば、 そのメッシュセッ トはファイル管理テーブルの下端行 のデータとして管理する。 左下基準メッシュはメッシュセッ トを代表する基準メ ッシュである。 そして、 左下基準メッシュが下端行に位置するメッシュセッ トが 複数ある場合は、 左端 （西端） から位置する順でメッシュセッ トを管理する。 す なわち、 メッシュセッ トを経度方向および緯度方向を基準にして左下基準メッシ ュが並ぶ順序で管理する。
図 8において、 項番 1のメッシュ （メッシュセッ ト） データ先頭ポインタには、 各行の左端メッシュセッ トデータの記録媒体 2のァドレスが収容される。 下端行 の場合； そのプロックで最初に収録されるメッシュセッ 卜への記録媒体 2のアド レスが収容される。 項番 2は、 コアメッシュの左下基準メッシュの相対番号であ る。 基準メッシュの相対番号とは、 ブロックの左下基準メッシュを 1とし、 行内 を左から右へ、 下端行から上端行へ昇順に割り振った番号である。
項番 3は、 コアメッシュ内の緯度方向の基準メッシュ枚数である。 項番 4は、 コアメッシュ内の経度方向の基準メッシュ枚数である。 メッシュセッ トは、 上述 した通り、 本実施の形態では矩形形状をしている。 従って、 項番 3および項番 4 の値を掛け算することにより、 コアメッシュを構成する基準メッシュの数が計算 できる。 コアメッシュが矩形形状していない場合は、 これらの値より、 コアメッ シュの大体の範囲が想定できる。
項番 5は、 ォ一バーラップメッシュも含めたメッシュセッ トの下端緯度 （コア メッシュ内の左下基準メッシュからの相対基準メッシュ枚数） である。 項番 6は， ォ一バーラップメッシュも含めたメッシュセッ トの左端経度 （コアメッシュ内の 左下基準メッシュからの相対基準メッシュ枚数） である。 項番 7は、 ォーパーラ ップメッシュも含めたメッシュセッ ト内の緯度方向の基準メッシュ枚数 （矩形領 域サイズ） である。 項番 8は、 オーバ一ラップメッシュも含めたメッシュセッ ト 内の経度方向の基準メッシュ枚数 （矩形領域サイズ） である。 項番 9は、 メッシ ュセッ トデータの格納場所を示す情報が入る。 メッシュセッ トデ一夕が更新され ていない場合は、 記録媒体 2上に格納されている旨の情報が入る。 格納アドレス については、 項番 1のメッシュ （メッシュセッ ト） データ先頭ポインタの内容と、 順次格納されているメッシュセッ トデータサイズを加算して求めることができる。 メッシュセッ トデータが更新されている場合は、 不揮発性メモリ 1 2上に格納さ れている旨とそのアドレスが入る。 なお、 アドレスの代わりに更新ファイル名で あってもよい。 項番 1 0は、 接続 · 部分規制メッシュセッ トデータサイズである。 項番 1 1は、 レベル間対応メッシュセッ トデータサイズである。
項番 2〜項番 1 1が 1つのメッシュセッ トの管理情報 （管理データ） である。 項番 1 2〜項番 2 1は右隣りのメッシュセッ 卜の管理情報である。 次に、 その右 隣りのメッシュセッ トの管理情報が続く。 右端 （東端） まで行くと、 1行上
(北） に進み、 同様に左端 （西端） から右端 （東端） にメッシュセッ トの管理情 報が格納される。 メッシュセッ 卜のコアメッシュは複数の基準メッシュから構成 されているので、 いずれのコアメッシュの左下基準メッシュも存在しない行が生 じる。 そのような行には、 メッシュセッ トの管理情報は存在しない。
図 2 4は、 メッシュセッ トをファイル管理テーブルで管理する様子を説明する ための図である。 符号 3 0 1〜符号 3 0 9は各メッシュセッ トのコアメッシュを 示す。 コアメッシュ 3 0 1、 3 0 2、 3 0 3の左下基準メッシュは下端行に位置 する。 コアメッシュ 3 0 1を含むメッシュセッ トは下端行の左端メッシュセッ ト として管理される。 その右隣りのメッシュセッ トは、 コアメッシュ 3 0 2を含む メッシュセッ トであり、 その右隣りがコアメッシュ 3 0 3を含むメッシュセッ ト である。 下端行 + 1行目には、 左下基準メッシュが位置するコアメッシュは存在 しないためフアイル管理テーブルにはデー夕が存在しない。 下端行 + 2行目には， コアメッシュ 3 0 4の左下基準メッシュが位置するので、 コアメッシュ 3 0 4を 含むメッシュセッ トが下端行 + 2行目の左端メッシュセッ トとして管理される。 同様にして、 下端行 + 3行目で、 左端からコアメッシュ 3 0 5を含むメッシュセ ッ ト、 コアメッシュ 3 0 6を含むメッシュセッ ト、 コアメッシュ 3 0 7を含むメ ッシュセッ トが管理され、 下端行 + 4行目で、 左端からコアメッシュ 3 0 8を含 むメッシュセッ ト、 コアメッシュ 3 0 9を含むメッシュセッ 卜が管理される。 一メッシュセッ 卜 7 タ一
次にメッシュセッ トデ一夕について説明する。 メッシュセッ トデータは、 メッ シュセッ トを構成する基準メッシュのメッシュデータの集まりである。 上述した 通り、 経路計算用データは各基準メッシュのメッシュデータとして管理される。 経路計算用データは、 接続 · 部分規制データとレベル間対応データとに分かれる。 図 9は、 接続 · 部分規制データのメッシュセッ トデータを示す図である。 図 9 に示されるデータの固まりで記録媒体 2、 あるいは不揮発性メモリ 1 2に格納さ れる。 項番 1の基準メッシュ数は、 メッシュセッ トを構成する基準メッシュの合 計数である。 コアメッシュを構成する基準メッシュの全数とオーバーラップメッ シュを構成する基準メッシュの全数の合計である。 その数分だけ基準メッシュデ —夕が後に配置される。 項番 2は、 基準メッシュデータへのオフセッ ト ·サイズ である。 基準メッシュ数の数だけオフセッ トとサイズの収容フィールドが並ぶ。 項番 3〜項番 7は、 基準メッシュデ一夕である。 n個の基準メッシュのメッシュ データが並ぶ。
一接続部データー
図 1 0は、 接続 · 部分規制デ一夕の基準メッシュデータの内容を示す図である c 項番 1はメッシュコードである。 メッシュコードは、 各基準メッシュを特定する ための情報であり、 例えば左下角の緯度経度に基づいて決められる。 図 6のプロ ック管理テ一ブルの緯度経度メッシュコ一ドと同様な計算で求め、 それらを組み 合わせてもよい。 項番 2は、 メッシュ識別情報である。 本基準メッシュデータが コアメッシュ内の基準メッシュなのかオーバ一ラップメッシュ内の基準メッシュ なのかを識別する情報である。 項番 3は、 コアメッシュ識別情報である。 オーバ 一ラップメッシュの場合に使用される。 同一レベルにおいて、 複数のコアメッシ ュにて使用されるォ一バーラップメッシュには、 そのメッシュコードが同じもの が複数存在する場合がある。 従って、 どのメッシュセッ トのオーバ一ラップメッ シュであるかを特定するために、 所属する所属するコアメッシュの左下基準メッ シュのメッシュコードを設定する。 項番 4は、 経路情報リスト識別情報である。 当該基準メッシュを含むコアメッ シュを注目した場合、 隣接コアメッシュとの間で、 経路情報リストが存在するか 否かを示す情報である。 経路情報リスト識別情報については、 さらに後述する。 項番 5は、 オフセッ ト情報である。 オフセッ ト情報は、 部分規制デ一夕の先頭ま でのオフセッ ト値である。 すなわち、 接続部データの大きさに対応する。 項番 6 は、 接続部データである。 項番 7は、 部分規制データである。 部分規制データと は、 各リンクに設定が考えられる規制情報をまとめたものである。
図 1 1は、 図 1 0の項番 6の接続部データの詳細を示す図である。 本実施の形 態では、 道路をリンクとノードとリンク列という概念で表す。 ノードは交差点や 道路上特に指定された点を言う。 リンクはノード間の道路に該当し、 リンク列は 1本の道路を複数のリンクで表したものである。 接続部データは、 このノードの 接続情報である。 1本のリンク列上に存在するノードの自ノード情報とそのノー ドに接続するノードの隣接ノード情報からなる。 自ノード情報および隣接ノード 情報は、 そのノードの位置座標が格納される。
自ノード情報には、 位置座標の情報に加えて、 次のような情報が付加される。 ( 1 ) 下位レベル側のノードに、 「通常上位接続ノード」 又は 「末端上位接続ノ ード （接続する一つ上位レベルでのルートの妥当性が保証されるノード） 」 の識 別情報。 （ 2 ) 下位レベル側のノードに、 そのノードが経路情報リストデ一夕上 に存在するか否かを示す識別情報。 （ 3 ) 下位レベル側のノードに、 上位方向に 最大 4レベルまでの、 上位ノード存在有無フラグ。 （4 ) 自ノード情報に 「無効 ノードフラグ」 を新規に追加し、 無効ノードフラグが〇Nの場合は自ノード情報 は残し、 それに該当する 「隣接ノード情報」 を削除する。 これは、 異なるコアメ ッシュ毎に、 同じメッシュコードのォ一パーラップメッシュ （それぞれ採択され る自ノードが異なる） を重複して保持することと、 それらのオーバ一ラップメッ シュとコアメッシュ内の同じメッシュコ一ドの基準メッシュ （全ての自ノードが 有効） のノード及びリンクが同じ I D番号を有する必要性があるための処置であ る。
図 1 2は、 オーバーラップメッシュの接続データ部を示す図である。 オーバー ラップメッシュの接続データは、 コアメッシュの接続データと同じデ一夕である 必要はない。 すなわち、 コアメッシュより粗いデータであってよい。 従って、 同 じ位置のコアメッシュを構成する基準メッシュのメッシュデータをコピーして、 自ノードを有効とするか無効とするかのフラッグを設けるようにした。 図 1 2の 例では、 項番 5の自ノード情報 3と項番 6の自ノード情報 4の無効ノードフラグ O Nされて、 これらのデータが間引かれた状態となっている。 このようにするこ とにより、 オーバ一ラップメッシュのメッシュデータを容易に生成することがで きる。 さらに、 いったん無効にしたノードも容易に有効に戻すことができるので、 データの更新も間違いなく容易に行うことができる。
一レベル間対応デ一ター
図 1 3は、 レベル間対応データのメッシュセッ トデータを示す図である。 図 1 3に示されるデータの固まりで、 記録媒体 2に格納される。 図 9の接続 ·部分規 制データのメッシュセッ トデータの後に引き続き格納される。 各項番の内容は図 9と同様である。
図 1 4は、 レベル間対応デ一夕の基準メッシュデ一夕の内容を示す図である。 項番 1 ~ 4のメッシュコード、 メッシュ識別情報、 コアメッシュ識別情報、 オフ セッ ト情報は、 図 1 0 と同様である。 項番 5は、 レベル間対応データである。 図 1 5は、 図 1 0の項番 5のレベル間対応データの詳細を示す図である。
項番 1は、 レベル間対応ヘッダである。 項番 2は、 対応レベル数である。 下位レ ベルへの最大対応数が設定される。 自レベルノードに対応した下位レベルノ一ド の対応 （存在位置） を最大でどのレベルまで収録するのかを示す。 当該自レベル を基準として対応を記述するその （下位） レベルの数を設定する。 項番 3〜項番 7は、 対応情報である。 対応情報は、 自レベルのメッシュに存在する編集上必要 とされたノードの数 n個分設けられる。
図 1 6は、 各対応情報の詳細を示す図である。 項番 1は、 該当自ノードの対応 情報であり、 項番 2〜項番 7は、 該当自ノードに接続する隣接ノードの対応情報 である。 図 1 6の例は、 ある自ノードに m個のノードが接続されている場合であ る。 図 1 7は、 自ノード対応情報の詳細を示す図である。 項番 1は、 該当自ノード の隣接ノード数が入る。 図 1 6の自ノードの場合 mが入る。 項番 2は、 自レベル 情報である。 該当自ノードの該当レベルでのノード番号が入る。 項番 3〜項番 6 は、 下位レベル情報である。 図 1 5の項番 2で設定されている対応レベル数分設 定され、 当該レベルを基準として近いレベルから順に下位レベル情報を並べられ る。 下位レベル情報は、 該当自ノードの下位レベルでの存在領域と下位レベルの 自ノード番号が格納される。 存在領域とは、 該当ブロックと該当基準メッシュが 識別できる情報である。
図 1 8は、 隣接ノード対応情報の詳細を示す図である。 項番 1は、 該当自ノード の隣接ノードの該当レベルでのノード番号が入る。 項番 2〜項番 5は、 下位レべ ル隣接情報である。 図 1 5の項番 2で設定されている対応レベル数分設定され、 当該レベルを基準として近いレベルから順に下位レベル情報を並べられる。 下位 レベル隣接情報は、 該当自ノードの隣接ノ一ドの下位レベルの存在領域と下位レ ベルの自ノ一ド番号が格納される。
一経路情報リスト一
次に経路情報リス卜について説明する。 経路情報リストとはあるメッシュセッ 卜間の経路を予め計算しリストアップしておくものである。 すなわち、 あるメッ シュセッ トに含まれるノ一ドと他のメッシュセッ トに含まれるノ一ド間の経路計 算 （経路探索） を予め行い、 最小コストの経路を選択してリストアップしておく ものである。 コストとは、 経路の距離、 その他の条件を考慮した値である。
経路情報リストは、 基本的にはそのレベル内にある全てのメッシュセッ ト相互 の組み合わせ分作成される。 ただし、 下位レベルすなわち詳細地図データを有す るレベルでは、 全てのメッシュセッ ト相互の組み合わせ分作成すると、 処理時間 および出力結果が膨大なものとなる。 従って、 コアメッシュの左下基準メッシュ 間の距離が所定の距離以内のもの同士のみ作成するようにする。 例えば、 レベル 1では左下基準メッシュ間の距離が 4 0 k m以内のものについて作成し、 レベル 2については全てのメッシュセッ ト相互の組み合わせ分作成するようにする。 こ れらの条件は適宜変更してもよい。
このように作成された経路情報リストを使用することにより、 経路計算の時間 が大幅に削減される。 本実施の形態では、 経路情報リストを使用するために、 図 1 0の項番 4で説明したように、 基準メッシュデータの中に経路情報リスト識別 情報の項目を設けている。 この経路情報リスト識別情報についてさらに詳しく説 明する。
図 1 9は、 経路情報リス ト識別情報について説明する図である。 図 1 9 ( a ) において、 注目コアメッシュをコアメッシュ Xとし、 コアメッシュ Xとコアメッ シュ dとの間には経路情報リストがなく、 コアメッシュ Xとコアメッシュ a、 c 、 e、 bとの間には経路情報リストが作成されているとする。 この場合、 コアメッ シュ Xの基準メッシュ Aのメッシュデータは図 1 9 ( b ) のようになる。 項番 4 の経路情報リス ト識別情報には、 該当基準メッシュの上下左右に隣接する基準メ ッシュとの間に関する情報が入る。
具体的には、 基準メッシュ Aの上側基準メッシュはコアメッシュ dに属し、 コ ァメッシュ Xとコアメッシュ dとの間には経路情報リストはないため、 経路情報 リストなしのデータが入る。 基準メッシュ Aの下側基準メッシュは自コアメッシ ュ内であるため、 自コアメッシュ内であることを示す N U L Lが入る。 基準メッ シュ Aの左側基準メッシュも自コアメッシュ内であるため、 自コアメッシュ内で あることを示す N U L Lが入る。 ¾準メッシュ Aの右側基準メッシュはコアメッ シュ eに属し、 コアメッシュ Xとコアメッシュ eとの間には経路情報リス トが存 在するため、 コアメッシュ eとの経路情報リスト有りのデータが入る。 経路情報 リス卜有りの場合は、 該当経路情報リス卜が参照できるようにポインタが入る。 コアメッシュ Xの基準メッシュ Bのメッシュデータは、 同様に、 図 1 9 ( c ) の ようになる。
このように、 該当基準メッシュのメッシュデータの経路情報リスト識別情報の 項目を参照することにより、 隣接する基準メッシュとの間に経路情報リス卜があ るか否かを判断することができる。 そして、 経路情報リストがある場合は、 経路 情報リストを取りこむことができ、 経路計算時間を短縮することができる。 すな わち、 予め計算された経路情報を取り込むことにより、 その都度ダイクストラ法 等の経路計算をしなくてもよく、 経路計算時間の短縮を図ることができる。
—レベル間におけるメッシュセッ 卜の関連付け一
前述した通り、 本実施の形態では、 地図データを縮尺率が異なる 7つのレベル に分け、 最詳細の縮尺率のレベルをレベル 0とし、 最広域地図のレベルをレベル 6として管理している。 このうち、 経路計算用データはレベル 1、 レベル 2、 レ ベル 4に設ける。 現在地が検出され目的地が指定されると、 現在地および目的地 間の経路計算を行う。
レベル 1の地図表示で、 現在地が検出され目的地が設定され、 現在地および目 的地ともレベル 1の同じコアメッシュ内にあると、 該コアメッシュ内の基準メッ シュの経路計算用データを使用して経路計算を行う。 また、 現在地と目的地が隣 接するコアメッシュにある場合も、 基本的には、 同一レベルの隣接するコアメッ シュの基準メッシュの経路計算用データを使用して経路計算を行う。
しかし、 レベル 1において、 現在地が存在するコアメッシュと目的地が存在す るコアメッシュとが離れている場合、 途中の経路を上位レベル 2の経路計算用デ —夕を使用して経路計算を行う。 また、 上位レベル 2においても該当コアメッシ ュ間が離れている場合、 さらに上位レベル 4の経路計算用データを使用して経路 計算を行う。 このようにすることにより、 途中の経路は、 上位レベルの少ない容 量の経路計算用データを使用できるので、 経路計算の処理時間が短縮できる。 た だし、 前述したように、 メッシュセッ ト間の経路情報リストが存在する場合は、 経路情報リストを使用する。 例えば、 レベル 1 において、 コアメッシュ間が離れ ている場合であっても、 前述したように、 メッシュセッ ト間が 4 0 K m以内で経 路情報リストがある場合はそれを使用する。
レベル 1 において、 経路情報リストがない場合、 現在地の属するメッシュセッ トのデ一夕を使用して、 ダイクストラ法等の経路計算を行う。 そして、 オーバラ ップメッシュのノードまでたどり着くと、 上位レベルであるレベル 2に上げて、 さらに経路計算を続ける。 目的地側も同様の処理を行う。 レベル 2では、 原則と して経路情報リス 卜があるため、 レベル 2まで上げられた現在地側のメッシュセ ッ 卜と目的地側のメッシュセッ ト間の最小コストの経路を選択する。 経路情報リ ストがない場合は、 レベル 2のメッシュセッ トのメッシュセッ トデータを使用し て経路計算を行う。 また、 必要に応じてオーバラップメッシュから上位レベル 4 に上がり、 レベル 4の経路計算用データを使用して経路計算を行う。 このように して経路計算が行われ、 現在地から目的地までの最適な経路を取得することがで さる。
上記において、 下位レベルのォ一バラップメッシュから上位レベルに上げると いう表現をした。 上位レベルに上げるとは、 下位レベルのノードに対応する上位 レベルのノードを特定し、 特定された上位レベルのノードからさらに経路計算を 続けることを言う。 ここで、 上位レベルのノードを特定するためには、 下位レべ ルのノードと上位レベルのノ一ドの対応付けが必要である。 このような対応づけ を行うためには、 下位レベルのメッシュセッ トと上位レベルのメッシュセッ トの 関連 （親子関係） 付けを把握する必要がある。 この関連付けのために、 本実施の 形態では、 前述したメッシュセッ トのファイル管理テーブルを使用する。
レベル間 ( 1 レベル又は 2レベル以上の隔たりを対象) におけるメッシュセッ 卜の関連付けは、 下位レベルのコアメッシュ内の左下基準メッシュが上位レベル に対して投影された場合に、 そこに位置する上位レベルの基準メッシュによって 構成されるコアメッシュを特定することで求められる。
図 2 0は、 レベル間におけるメッシュセッ トの関連付けを説明する図である。 基準メッシュ L 1 一 1 ~ L 1— 1 7は、 レベル 1のあるメッシュセッ トを構成す る。 基準メッシュ L 1 一 1〜： L 1— 9はコアメッシュを構成し、 基準メッシュ L 1— 1 0〜： L 1— 1 7はオーバ一ラップメッシュを構成する。 基準メッシュ L 2 一：！〜 L 2— 8は、 レベル 2のあるメッシュセッ トを構成する。 基準メッシュ L 2— 1 ~ L 2— 6はコアメッシュを構成し、 基準メッシュ L 2— 7〜L 2— 8は オーバーラップメッシュを構成する。
下位レベルの左下基準メッシュ L 1— 1は、 上位レベルの基準メッシュ L 2― 5に含まれるため、 ファイル管理テ一ブルより、 基準メッシュ L 2— 5を含む上 位レベルのコアメッシュの左下基準メッシュを求める。 これにより、 上位レベル のコアメッシュ内の基準メッシュを読み取ることが可能となる。
具体的には、 次のような手順を取る。 （ 1 ) 左下基準メッシュ L 1— 1 自体の 相対番号は把握されいてる。 これにより、 左下基準メッシュ L 1 一 1の緯度経度 情報を計算により得ることができる。 （2 ) 左下基準メッシュ L 1— 1の緯度経 度情報が把握できると、 上位レベル 2のブロック管理テーブルを参照してどのプ ロックに属するかが把握できる。 （ 3 ) どのブロックに属するかが把握できると、 該当ブロックのメッシュ管理テ一ブルの参照が可能となる。 （4 ) 該当メッシュ 管理テ一プルのファイル管理テーブルを参照し、 左下基準メッシュ L 1一 1の緯 度経度情報に基づき、 左下基準メッシュ L 1— 1の位置が、 どのメッシュセッ ト のコアメッシュ内に位置するかを求めることができる。 このようにして、 レベル 間のメッシュセッ 卜の関連付けができる
レベル間のメッシュセッ 卜の関連付けができると、 上位レベル 2の該当メッシ ュセッ ト内の基準メッシュのメッシュデータにあるレベル間対応データを検索す ることにより、 ノード間の対応付けができる。 このようにして、 下位レベル 1の ノードと上位レベル 2のノードを対応付けし、 下位レベル 1から上位レベル 2に 上げて経路計算を行うことができる。
前述した通り、 下位レベルのコアセッ トの左下基準メッシュが上位レベルのど のコアセッ トに属するかを基準にしている。 従って、 下位レベルのコアメッシュ が、 上位レベルのコアメッシュの境界をまたぐように設定される場合も理論的に はあり得る。 しかし、 基本的には、 下位レベルのコアメッシュは、 上位レベルの コアメッシュ内に収まるよう設定するのが好ましい。 これにより、 下位レベルの コアメッシュ全体が、 上位レベルの 1つのコアメッシュの中に収まるようになる。 —ォ一パーラップメッシュの使用一
本実施の形態では、 下位レベルから上位レベルに上げるとき、 下位レベルのメ ッシュセッ 卜の才一バーラップメッシュから上げるようにしている。 すなわち、 下位レベルのメッシュセッ 卜において、 ォ一パーラップメッシュのノードまで経 路計算を行う。 そして、 オーバ一ラップメッシュのノードと上位レベルのノード - との対応付けを上記の方法で行い、 対応付けされた上位レベルのノ一ドからさら に経路計算を行うようにしている。
これは、 ォ一パーラップメッシュのデータ容量を小さく し、 経路計算の負荷を 小さくし、 さらに、 上位レベルとの対応付けの計算の負荷を小さくするためであ る。 上位レベルにつなげて経路計算を行う場合は、 上位レベルにつなげるための 経路計算用データとして長距離探索に必要なデータのみがオーバーラップデータ を構成すればよいからである。 これにより、 経路計算時間の短縮を図ることがで きる。
ォ一バーラップメッシュを構成する基準メッシュのメッシュデータは、 前述し たように、 同じ位置のコアメッシュを構成する基準メッシュのメッシュデータか らデ一夕を間引いて生成する。 前述した図 1 2の例では、 自ノード情報に無効ノ ードフラグを設けるようにする例を説明した。 しかし、 このようなフラグを設け ず、 オーバ一ラップメッシュに必要なノードの情報のみを直接生成するようにし てもよい。 このようにすることにより、 オーバ一ラップメッシュのメッシュデ一 夕のデータ容量を削減することができる。
同じ位置の基準メッシュであっても、 異なるメッシュセッ トのオーバ一ラップ メッシュを構成する基準メッシュとなる場合が生じる。 そのような場合、 オーバ —ラップメッシュのメッシュデータは、 異なるメッシュセッ トによつてそれぞれ 異なるように生成される。 すなわち、 オーバーラップメッシュはコアメッシュか らのつながりに応じて、 必要なノードのみを残すようにして生成する。 従って、 同じ位置であってもどのコアメッシュに隣接するオーバーラップメッシュかによ つて構成する経路計算用データは異なるようになる。 もちろん、 同じデータにな つてもよい。
ォ一バラップメッシュのメッシュデ一夕の生成方法として、 コアメッシュから つながる主要な道路、 例えば幹線道路や高速道路などのノ一ドのみを残す等各種 の方法が考えられる。 これは、 経路計算用データ生成の経験をベースに人手によ り生成するようにしてもよいし、 あるいは、 コンピュータのシミュレーションに よりもつとも効率のよいデータを生成するようにしてもよい。 また、 上述したよ うに道路種別などを判断して、 一定の規則のもと自動生成するようにしてもよい。 また、 コアメッシュのデータから仕様上必要なリンクの情報は残し、 不要なリン クについては自ノード情報のみを残して隣接ノード情報を削除するようにして生 成してもよい。
一ナビゲーショ'ン装置での地図データの更新管理一
図 2 1は、 ナビゲ一シヨン装置 1での地図データの更新管理の様子を説明する 図である。 本実施の形態のナビゲ一シヨン装置 1は、 上述したメッシュセッ ト単 位で経路計算用データなどの地図データの更新が可能である。 ナビゲーシヨン装 置 1は、 記録媒体 2からメッシュ管理テーブルおよび地図データを読み込み、 さ らに、 リム一バブルメモリ 3あるいはィンターネッ ト 5を介して地図サーバ 6か ら更新地図データを読み込み、 最新の地図データを使用することができる。 従来のナビゲ一ション装置の場合、 データの読み込み元は C D— R O Mや D V D一 R O Mなどの記録媒体のみであった。 本実施の形態のナビゲ一ション装置で は、 記録媒体 2中の地図データと更新された地図データとを混在させて使用する。 このため、 読み書き可能メディアである不揮発性メモリ 1 2を有する。 不揮発性 メモリ 1 2はハ一ドディスクやフラッシュメモリなどの不揮発性メモリで構成さ れ、 ナビゲーシヨン装置の電源が落とされてもデータは保持される。 不揮発性メ モリ 1 2は、 キャッシュメディア 1 2と呼んでもよい。
不揮発性メモリ 1 2は、 図 6で説明したブロック管理テーブル 1 2 4を有する。 ブロック管理テーブル 1 2 4は、 該当ブロックのメッシュ管理テーブルが記録媒 体 2上にあるのか不揮発性メモリ 1 2上にあるのかの識別情報およびそのァクセ スアドレスを有する。 新しい地図データを初めて使用するとき、 まずはじめに、 記録媒体 2に格納されたブロック管理テーブルを不揮発性メモリ 1 2に読みこむ。 初期値としては、 各ブロックのメッシュ管理テーブルは記録媒体 2上にあるとし て設定されている。 その後、 地図データのメッシュセット単位の更新に応じて、 更新されたメッシュを有するプロックのメッシュ管理テーブル 1 2 5を不揮発性 メモリ 1 2に作成し、 ブロック管理テーブル 1 2 4において、 該当ブロックのメ ッシュ管理テーブルは不揮発性メモリ 1 2上にある旨を設定する。 プログラムは、 プロック管理テーブル 1 2 4を参照することにより、 メッシュ管理テーブルが、 記録媒体 2上にあるのか不揮発性メモリ 1 2上にあるのかを判断することができ る。
符号 1 2 6は、 ナビゲ一シヨン装置のメモリ 1 5内にあるメモリであり、 メッ シュ管理テーブルを格納する領域である。 以下メモリ 1 2 6と言う。 プログラム は、 メッシュ管理テーブルが記録媒体 2上にあるのか不揮発性メモリ 1 2上にあ るのかを判断した後、 該当メディァからメッシュ管理テーブルを読み出し、 メモ リ 1 2 6に格納する。 メモリ 1 2 6に読み込まれたメッシュ管理テーブル 1 2 7 は、 上述した図 7、 図 8等に説明したメッシュ管理情報を有する。
リム一バブルメモリ 3でメッシュセッ ト単位の地図データが更新されると、 該 当メッシュセッ トの地図データは不揮発性メモリ 1 2に読み込まれ、 地図データ 1 3 3として格納される。 このとき、 不揮発性メモリ 1 2上のメッシュ管理テー ブルの該当メッシュセッ トの項番 9の格納場所に、 本メッシュセッ 卜のメッシュ セッ トデータは不揮発性メモリ 1 2に格納されている旨とそのァドレスを書きこ む。 また、 メッシュセッ トデータのデータサイズが変更されている場合は、 項番 1 0、 1 1の内容を書きかえる。 その他の項目は、 更新によって特に書きかえる 必要はない。 その後、 この内容に基づき、 不揮発性メモリ 1 2へアクセスするこ とができる。 すなわち、 更新されていないメッシュセッ トの地図データは記録媒 体 2へアクセスし、 更新されたメッシュセッ 卜地図データは不揮発性メモリ 1 2 へアクセスすることができる。
一経路計算の制御フローチヤ一ト―
図 2 2は、 制御装置 1 1が経路計算用データを読み込んで経路計算を行う制御 のフローチャートを示す図である。 ステップ S 1では、 現在地検出装置 1 3を使 用して、 車両の現在地を検出する。 ステップ S 2では、 ユーザが入力装置 1 9を 使用して指定した目的地を設定する。 ステップ S 3では、 車両の現在地や目的地 周辺の必要なメッシュセッ 卜のメッシュセッ トデータを読み込む。 ステップ S 4 では、 ダイクス トラ法等を使用して経路計算 （経路探索） を行う。 ステップ S 5 では、 すべての経路計算が完了したか否かを判断する。 すなわち、 現在地から目 的地までの経路計算がすべて完了したか否かを判断する。 ステップ S 5で、 まだ 完了していないと判断すると、 ステップ S 3に戻り、 さらに必要なメッシュセッ 卜のメッシュセッ トデータを読み込み、 経路計算を続行する。 ステップ S 5で、 経路計算が完了したと判断すると処理を終了する。 ステツプ S 3〜S 5を繰り _返 す中で、 適宜、 必要に応じて前述した上位レベルへの接続を行う。
図 2 3は、 図 2 2のステップ S 3の処理の詳細なフロ一チヤ一トを示す図であ る。 ステップ S 2 1で、 前述したように、 不揮発性メモリ 1 2にあるブロック管 理テーブルにアクセスする。 この場合、 ブロック管理テーブルはすでに不揮発性 メモリ 1 2に読みこまれた状態であることを前提とする。 ステップ S 2 2で、 ブ 口ック管理テーブルの内容に基づき、 該当ブロックのファイル管理テーブルが記 録媒体 2上にあるか不揮発性メモリ 1 2上にあるかを判断する。 ステップ S 2 2 で、 記録媒体 2にあると判断するとステップ S 2 3に進む。 ステップ S 2 3では， 記録媒体 2から該当ブロックのファイル管理テーブルをメモリ 1 2 6に読みこむ ( 一方、 ステップ S 2 2で、 記録媒体 2上にない、 すなわち、 不揮発性メモリ 1 2上にあると判断すると、 ステップ S 2 4に進む。 ステップ S 2 4では、 不揮発 性メモリ 1 2から該当ブロックのファイル管理テーブルをメモリ 1 2 6に読みこ む。 ステップ S 2 5では、 メモリ 1 2 6に読みこまれたファイル管理テ一ブルの 内容に基づき、 該当メッシュセッ トの格納先アドレスを計算する。 ステップ S 2 6で、 計算された格納先からメッシュセッ トデータを読みこむ。 この場合、 メッ シュセッ トデ一夕が更新されていない場合は、 記録媒体 2からメッシュセッ ト単 位でデ一夕が読み込まれる。 また、 メッシュセッ トデータが更新されている場合 は、 不揮発性メモリ 1 2からデータが読み込まれる。
以上説明したように、 本実施の形態の地図データの構造ゃナピゲーション装置 を使用した場合、 次のような効果を奏する。
( 1 ) 記録媒体 2に格納されている経路計算用データを、 複数の基準メッシュか ら構成されるメッシュセッ トという概念を導入して管理するようにした。 これに より、 経路計算に適したデータの固まりで、 記録媒体 2から連続的に読み出すこ とが可能となる。 その結果、 メッシュ単位で管理されたデータをメッシュ毎に読 み出すことに比べ、 D V D駆動装置の読み取りヘッ ドのシーク回数が激減し、 処 理の高速化が実現される。
( 2 ) オーバーラップメッシュという概念を導入したので、 下位レベルと上位レ ベルを接続する場合に、 経路計算の処理時間の短縮を図ることができる。
( 3 ) オーバーラップのメッシュデータ作成のための無効フラグを設けるように した。 これにより、 オーバーラップメッシュのデータの生成管理が容易となる。
( 4 ) メッシュセッ トを管理するファイル管理テーブルを設けるようにした。 こ れにより、 ファイル管理テーブルを参照するだけで、 レベル間のメッシュセッ ト の関連付け （親子関係） が容易に把握できるようになる。 また、 さらに特別なテ 一ブルを設ける必要がない。
( 5 ) メッシュセッ ト単位で経路計算用データなどの地図データの更新ができる ので、 地図データの一部のみ更新する場合、 地図データが格納された D V D— R O Mなどの記録媒体全体を新しいものにする必要がない。 更新の最小単位をメッ シュセッ ト単位とし、 不必要なデータ更新に掛かる通信量（コスト）も低減するこ とができる。
( 6 ) 更新データをインターネッ ト経由の通信によっても提供するので、 迅速に かつ安い費用で最新の更新データを提供することができる。
( 7 ) 予め作成された経路情報リストを適切に使用するので、 経路計算の時間が 大幅に削減される。
( 8 ) 不揮発性メモリにメッシュ管理テーブルを格納しながら、 地図データを管 理しているので、 更新データの管理を容易かつ確実に行うことができる。 これに より、 ナビゲ一ション装置のプログラム開発などが容易となる。
( 9 ) 全国分の更新データの一括配信を受けるのではなく、 ユーザが選んだ地域 のみの配信を受けるので、 その受信時間は必要最小限で済む。 また、 全ての地図 データを読み書き可能な大容量記憶装置に収録するのではないため、 ユーザが要 求する更新データのみを収録可能な記憶容量で十分である。
上記の実施の形態では、 ナビゲーシヨン装置の制御装置 1 1が実行する制御プ ログラムは R O Mに格納されている例で説明をしたが、 この内容に限定する必要 はない。 制御プログラムやそのインストールプログラムを D V Dなどの記録媒体 で提供してもよい。 なお、 記録媒体は D V Dに限定する必要はなく、 C D— R O M、 磁気テープやその他のあらゆる記録媒体を使用するようにしてもよい。
さらに、 それらのプログラムをインタ一ネッ トなどに代表される通信回線など の伝送媒体を介して提供することも可能である。 すなわち、 プログラムを、 伝送 媒体を搬送する搬送波上の信号に変換して送信することも可能である。 プロダラ ムを記録媒体ゃィンターネッ トで提供する場合は、 図 1 と同じような構成で提供 すればよい。 例えば、 記録媒体 2をプログラム提供の記録媒体にし、 地図サーバ 6をアプリケ一ションプログラムを提供するサーバーとすればよい。 このように, プログラムは、 記録媒体や搬送波などの種々の形態のコンピュータ読み込み可能 なコンピュータプログラム製品として供給できる。
また、 上述の制御プログラムをパソコン上で実行させて力一ナビゲ一ション装 置を実現するようにしてもよい。 その場合、 現在地検出装置 1 3や入力装置 1 9 などは、 パソコンの所定の I / Oポ一トなどに接続するようにすればよい。
上記の実施の形態では、 リム一バブルメモリ 3から更新デ一夕を提供する例を 説明したが、 この内容に限定する必要はない。 更新用データを C D— R O Mや D V D— R O Mなどに書きこんで、 記録媒体 2を一時的に入れ替えて提供するよう にしてもよい。
上記の実施の形態では、 記録媒体 2から初期の地図データを読み込む例を説明 したが、 この内容に限定する必要はない。 初期の地図データをインターネッ ト 5 を介して受け取って不揮発性メモリ 1 2に格納し、 その後前述した手法で更新管 理するようにしてもよい。 また、 インターネッ ト 5を介して必要な地図デ一夕を その都度受け取り、 その都度不揮発性メモリ 1 2に格納し、 その後更新がある場 合は、 前述した手法で更新管理をしてもよい。 このように、 地図データは、 記録 媒体や搬送波などの種々の形態のコンピュータやナビゲーシヨン装置 （地図デー 夕処理装置） に読み込み可能な地図データ製品として供給できる。
上記の実施の形態では、 経路計算用データをメッシュセッ 卜の概念を使用して 管理する例を説明した。 また、 地図表示用データでは特にメッシュセッ トの概念 を使用しなくてもよい旨説明した。 しかし、 地図表示用データにメッシュセッ ト の概念を使用して管理してももちろんよい。 経路計算用データほどの効果は得ら れないがデータの読み込み等の処理速度の向上が図られる場合もある。 また、 そ の他の地図デ一夕においてもメッシュセッ 卜の概念を使用することができる。 上記の実施の形態では、 不揮発性メモリ 1 2はナビゲーシヨン装置 1の内部に 設けられる例を説明したが、 この内容に限定する必要はない。 ケーブルなどによ つて接続される外部記憶装置であってもよい。
上記では、 種々の実施の形態および変形例を説明したが、 本発明はこれらの内 容に限定されるものではない。 本発明の技術的思想の範囲内で考えられるその他 の態様も本発明の範囲内に含まれる。

Claims

請求の範囲
1 . コンピュータあるいは地図データ処理装置に読み込み可能なデータ製品で あって、 地図に関する情報を有する地図データを有し、 該地図デ一夕は、
前記地図をメッシュ状の複数の区画に分割し、 分割した前記区画単位に対応さ せて前記地図に関する情報を分割した構造と、
前記地図に関する情報を、 隣接する前記区画を複数集めた区画セッ ト単位で管 理し、 前記区画セッ ト単位で前記地図データ処理装置により処理される構造とを 備える。
2 . 請求項 1記載のデータ製品において、
前記区画セッ トは、 他の区画セッ トとの間で重複しない 1以上の前記区画から なるコア区画と、 他の区画セッ トのコア区画に該当する 1以上の前記区画からな るォ一パーラップ区画とから構成される。
3 . 請求項 1〜 2のいずれか 1項記載のデータ製品において、
前記オーバーラップ区画に対応する前記地図に関する情報は、 他の区画セッ ト のコア区画に対応する前記地図に関する情報から間引いて生成される。
4 . 請求項 1〜 3のいずれか 1項記載のデータ製品において、
前記区画セッ トに対応する前記地図に関する情報は、 記録媒体上に 1つのかた まりとして連続して記録される構造である。
5 . 請求項 1〜 4のいずれか 1項記載のデータ製品において、
前記地図に関する情報は、 さらに、 前記区画単位で前記地図データ処理装置に より処理可能な構造を備える。
6 . 請求項 1〜 5のいずれか 1項記載のデータ製品において、
前記区画セッ ト単位の地図に関する情報の管理情報を有する構造をさらに備え. 前記地図データ処理装置が取得した前記地図に関する情報は、 前記管理情報を 使用して、 前記区画セッ ト単位で更新可能である。
7 . 請求項 1〜 6のいずれか 1項記載のデータ製品において、
前記地図に関する情報は、 経路計算に使用される地図上の経路に関する情報で ある。
8 . 請求項 3記載のデ一夕製品において、
前記地図に関する情報は、 経路計算に使用される地図上の経路に関する情報で あり、
道路の交差点をノードとし、
前記地図上の経路に関する情報は、 1本の道路上に存在する複数のノードの自 ノ一ド情報とそれぞれの自ノードに接続されるノードの隣接ノード情報とからな り、
前記コア区画に対応する前記地図上の経路に関する情報は、 前記自ノード情報 と前記隣接ノード情報とから構成され、
前記オーバーラップ区画に対応する前記地図上の経路に関する情報は、 前記コ ァ区画に対応する前記地図上の経路に関する情報から、 所定のノードの前記隣接 ノード情報を削除して生成されている。
9 . コンピュータあるいは地図データ処理装置に読み込み可能なデータ製品で あって、 地図に関する情報を有する地図データを有し、 該地図データは、 前記地図をメッシュ状の複数の区画に分割し、 分割した前記区画単位に対応さ せて前記地図に関する情報を分割した構造と、
前記地図に関する情報を、 隣接する前記区画を複数集めた区画セッ ト単位で管 理し、 前記区画セッ 卜単位で前記地図データ処理装置により処理される構造とを 備え、
前記区画セッ トは、 第 1の区画と、 第 1の区画に隣接する 1以上の区画からな Ό、 前記第 1の区画に対応する前記地図に関する情報は、 前記分割された地図に関 する情報からなり、
前記第 1の区画に隣接する 1以上の区画に対応する前記地図に関する情報は、 前記分割された地図に関する情報から間引いて生成された情報からなる。
1 0 . 請求項 1〜 6、 9のいずれか 1項記載のデータ製品は、 前記地図データ が記録された記録媒体である。
1 1 . 請求項 7〜 8のいずれか 1項記載のデータ製品は、 前記地図データが記 録された記録媒体である。
1 2 . 地図データ処理装置であって、
請求項 1 0から 1 1のいずれか 1項に記載のデータ製品である記録媒体を搭載 する記録媒体駆動部と、
前記記録媒体に記録された地図データに基づき、 地図データの処理を行う処理 部とを備える。
1 3 . 地図データ処理装置であって、
請求項 1 1に記載のデータ製品である記録媒体を搭載する記録媒体駆動部と、 前記記録媒体に記録された前記地図上の経路に関する情報に基づき、 経路計算 を行う処理部とを備える。
1 4 . コンピュータあるいは地図データ処理装置に読み込み可能なデータ製品 であって、 地図に関する情報を有する地図デ一夕を有し、 該地図データは、 縮尺率が異なる複数のレベル単位で前記地図に関する情報を備えた構造と、 各レベル毎に、 前記地図をメッシュ状の複数の区画に分割し、 分割した前記区 画単位に対応させて前記地図に関する情報を分割した構造と、
前記地図に関する情報を、 隣接する前記区画を複数集めた区画セッ ト単位で管 理し、 前記区画セッ ト単位で前記地図データ処理装置により処理される構造と、 前記各レベル内において、 前記区画セッ トを管理する情報を有する管理テープ ルを備える構造とを備え、
前記管理テーブルは、 各レベルの区画セッ トのレベル間の対応関係を演算によ り求めることが可能な情報を有する。
1 5 . 請求項 1 4記載のデータ製品において、
前記管理テーブルは、 前記区画セッ トを代表する基準区画の位置を表す情報と、 前記区画セッ トの分割たて方向の数に関する情報と、 分割横方向の数に関する情 報とを有する。
1 6 . 請求項 1 5記載のデ一夕製品において、
前記区画セッ トは矩形形状を有し、
前記区画セッ トを代表する基準区画は、 前記区画セッ 卜の左下に位置する区画 である。
1 7 . 請求項 1 6記載のデータ製品において、
前記区画セッ トを管理する情報は、 前記区画セッ トを代表する基準区画が分割 横方向および分割たて方向を基準として並ぶ順序で格納される。
1 8 . 請求項 1 4 ~ 1 7のいずれか 1項記載のデータ製品において、
前記各レベル内において、 前記地図をメッシュ状の複数のブロックに分割し、 前記複数の区画は、 前記各ブロックをさらに分割して得られた区画であり、 前記管理テーブルは、 前記各ブロック毎に設けられる。
1 9 . 請求項 1 4〜 1 8のいずれか 1項記載のデータ製品において、
前記地図データ処理装置が取得した前記地図に関する情報は、 前記管理テープ ルを使用して、 前記区画セッ ト単位で更新可能である。
2 0 . 請求項 1 4〜 1 9のいずれか 1項記載のデータ製品において、 前記地図上の道路の交差点をノードとし、
前記地図に関する情報は前記ノードに関する情報を有し、
前記区画単位に分割した地図に関する情報は、 該区画内のノードと他のレベル の対応するノ一ドとのレベル間ノード対応情報をさらに有し、
前記区画セッ トのレベル間の対応関係と前記区画セッ トを構成する区画のレべ ル間ノード対応情報を使用して、 ノードのレベル間の対応関係を把握することが 可能である。
2 1 . 請求項 1 4〜 2 0のいずれか 1項記載のデータ製品において、
前記地図に関する情報は、 経路計算に使用される地図上の経路に関する情報で ある。
2 2 . 請求項 1 4〜 2 0のいずれか 1項記載のデータ製品は、 前記地図データ が記録された記録媒体である。
2 3 . 請求項 2 1記載のデータ製品は、 前記地図データが記録された記録媒体 である。
2 4 . 地図データ処理装置であって、
請求項 2 2から 2 3のいずれか 1項に記載のデータ製品である記録媒体を搭載 する記録媒体駆動部と、
前記記録媒体に記録された地図データに基づき、 地図データの処理を行う処理 手部とを備える。
2 5 . 地図データ処理装置であって、
請求項 2 3に記載のデータ製品である記録媒体を搭載する記録媒体駆動部と、 前記記録媒体に記録された前記地図上の経路に関する情報に基づき、 経路計算 を行う処理部とを備える。
PCT/JP2003/009650 2002-07-30 2003-07-30 地図データ製品および地図データ処理装置 Ceased WO2004012171A1 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US10/522,629 US7783687B2 (en) 2002-07-30 2003-07-30 Map data product and map data processor
EP03771424A EP1548686B1 (en) 2002-07-30 2003-07-30 Map data product and map data processor

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2002-220922 2002-07-30
JP2002-220923 2002-07-30
JP2002220922A JP4145596B2 (ja) 2002-07-30 2002-07-30 地図データ処理装置
JP2002220923A JP4145597B2 (ja) 2002-07-30 2002-07-30 地図データ処理装置

Publications (1)

Publication Number Publication Date
WO2004012171A1 true WO2004012171A1 (ja) 2004-02-05

Family

ID=31190321

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2003/009650 Ceased WO2004012171A1 (ja) 2002-07-30 2003-07-30 地図データ製品および地図データ処理装置

Country Status (3)

Country Link
US (1) US7783687B2 (ja)
EP (1) EP1548686B1 (ja)
WO (1) WO2004012171A1 (ja)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4841242B2 (ja) * 2005-12-15 2011-12-21 アルパイン株式会社 地図データ更新方法および地図データ更新装置
JP5116236B2 (ja) * 2006-01-30 2013-01-09 アルパイン株式会社 地図データ作成方法及び地図データ作成装置
JP5001617B2 (ja) * 2006-09-29 2012-08-15 アイシン・エィ・ダブリュ株式会社 地図更新データ供給装置、バージョンテーブル、地図データ更新システム、地図更新データ供給プログラム、及び地図データ更新プログラム
JP5308621B2 (ja) * 2006-10-05 2013-10-09 日立オートモティブシステムズ株式会社 地図データ配信システム
JP2010519833A (ja) * 2007-02-27 2010-06-03 アゼリア ネットワークス 経路距離係数によるメッシュ状ネットワークにおける無線周波数管理のための方法およびシステム
JP5078712B2 (ja) * 2008-04-01 2012-11-21 任天堂株式会社 画像処理プログラム、画像処理装置、画像処理システム及び画像処理方法
JP5289431B2 (ja) * 2008-04-28 2013-09-11 三菱電機株式会社 ナビゲーション装置
DE102008052942A1 (de) 2008-10-23 2009-06-10 Daimler Ag Verfahren zum Betrieb eines Fahrzeugs
JPWO2011128948A1 (ja) * 2010-04-16 2013-07-11 三菱電機株式会社 ナビゲーション装置
JP2013037416A (ja) * 2011-08-04 2013-02-21 Kokusai Kogyo Co Ltd メッシュデータ検索システム
CN105026892B (zh) 2013-01-30 2018-02-27 赫力环球有限公司 用于在导航应用中使用的方法和装置
DE102013008936B4 (de) * 2013-05-24 2021-09-02 e.solutions GmbH Erstellung und Verwendung einer Datenstruktur für die Pfadermittlung in einem Verkehrswegenetz
JP6227658B2 (ja) * 2013-09-17 2017-11-08 三菱電機株式会社 地図情報処理装置、データ生成方法
CN103593468B (zh) * 2013-11-27 2016-11-16 北京金和软件股份有限公司 一种音频内容推送方法
US20220269281A1 (en) * 2021-02-23 2022-08-25 Ran Cheng Method and system for generating a topological graph map

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08122089A (ja) * 1994-10-27 1996-05-17 Toyota Motor Corp 経路探索装置
EP0838663A2 (en) 1996-10-25 1998-04-29 Navigation Technologies Corporation System and method for storing geographic data on a physical storage medium
US5845228A (en) 1996-02-08 1998-12-01 Mitsubishi Denki Kabushiki Kaisha Vehicle-route computing apparatus

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2949887B2 (ja) 1991-03-29 1999-09-20 株式会社デンソー 経路探索装置
JPH06323861A (ja) 1993-05-11 1994-11-25 Sumitomo Electric Ind Ltd 経路計算機能を有するナビゲーション装置
JPH0887234A (ja) 1994-09-19 1996-04-02 Mitsubishi Electric Corp 道路情報提供システム
JP3477329B2 (ja) * 1996-10-22 2003-12-10 株式会社ザナヴィ・インフォマティクス ナビゲーション装置
JP3866346B2 (ja) 1996-12-18 2007-01-10 株式会社ザナヴィ・インフォマティクス 地図データベース装置
JP3540140B2 (ja) 1997-12-17 2004-07-07 三菱電機株式会社 経路探索装置および記憶媒体
JP3171574B2 (ja) 1998-03-05 2001-05-28 松下電器産業株式会社 経路選出方法
JP3780715B2 (ja) 1998-10-13 2006-05-31 トヨタ自動車株式会社 車載ナビゲーション装置、車両用地図データ提供システム
JP3892643B2 (ja) 2000-05-23 2007-03-14 アルパイン株式会社 ナビゲーション装置
US6912462B2 (en) 2000-08-31 2005-06-28 Sony Corporation Information processing apparatus, information processing method and program storage media
JP3789306B2 (ja) 2001-01-10 2006-06-21 松下電器産業株式会社 経路探索方法

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08122089A (ja) * 1994-10-27 1996-05-17 Toyota Motor Corp 経路探索装置
US5845228A (en) 1996-02-08 1998-12-01 Mitsubishi Denki Kabushiki Kaisha Vehicle-route computing apparatus
EP0838663A2 (en) 1996-10-25 1998-04-29 Navigation Technologies Corporation System and method for storing geographic data on a physical storage medium

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
HIROSHI MISAWA ET AL.: "Chiri joho system well-informed geographer: an integrated geographic information system", NEC TECHNICAL JOURNAL, vol. 37, no. 5, 25 May 1984 (1984-05-25), pages 32 - 40, XP002973851 *
See also references of EP1548686A4

Also Published As

Publication number Publication date
US7783687B2 (en) 2010-08-24
EP1548686B1 (en) 2012-09-05
US20060167934A1 (en) 2006-07-27
EP1548686A4 (en) 2008-04-16
EP1548686A1 (en) 2005-06-29

Similar Documents

Publication Publication Date Title
JP4162959B2 (ja) 地図データ処理装置
KR100735441B1 (ko) 지도 구조를 가진 데이터를 기록한 기억매체, 지도 데이터 처리 프로그램을 기록한 기억매체, 지도 데이터 처리 방법 및 지도 데이터 처리 장치
JP5675751B2 (ja) ナビゲーションデータベースを構造化するための技法
US6023655A (en) Map database apparatus
EP2487461A1 (en) Vehicle navigation device and method
WO2004012171A1 (ja) 地図データ製品および地図データ処理装置
WO2004008073A1 (ja) ナビゲーション方法、ナビゲーションシステムのための処理方法、地図データ管理装置、地図データ管理プログラム、及びコンピュータプログラム
JP2004178248A (ja) 地図情報提供装置および地図情報提供プログラム
JP2006003385A (ja) 地図データ提供装置
JP4112274B2 (ja) 地図データ処理方法および地図データ処理プログラム
JP3866346B2 (ja) 地図データベース装置
US7577515B2 (en) Navigation apparatus, update data providing apparatus and update data providing method
JP4037167B2 (ja) 地図データ処理装置
JP5017157B2 (ja) 地図データ処理装置
JP2004177245A (ja) 地図情報処理装置および地図情報処理プログラム
JP4145596B2 (ja) 地図データ処理装置
JPH0553501A (ja) 経路テーブルを用いた最適経路決定方法
JP4145597B2 (ja) 地図データ処理装置
JP4388161B2 (ja) ルート計算装置
JP3892727B2 (ja) 地図情報作成方法及び作成装置
JPH08178682A (ja) 経路探索方法及び経路探索装置
JPH1183502A (ja) 地図データ表示装置及び地図データ表示方法並びに地図データ表示装置に使用される記録媒体
JPH07104175B2 (ja) 最適経路決定装置

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2003771424

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2003771424

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2006167934

Country of ref document: US

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 10522629

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 10522629

Country of ref document: US