Data structure of map data, map data storage medium, map data updating method and map data processing apparatus

• US 20050058155A1
• Filed: 08/25/2004
• Published: 03/17/2005
• Est. Priority Date: 08/26/2003
• Status: Active Grant

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Shimotani, Mitsuo, Umezu, Masaharu, Mikuriya, Makoto, Ikeuchi, Tomoya, Ohki, Hidehiko
• Granted Patent: US 7,526,492 B2
• Time in Patent Office: Days
• US Class Current: 370/474
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: H04Q 3/0062 Provisions for network management

Abstract

For map data, a road system is represented by using node data, which is information concerning nodes representing points along a road, and link data, which is information concerning a link representing a road between the points. A link row is a series of links representing a series of roads in a road system, and as link row data, link data for the links that constitute the link row are arranged in the order in which the links are connected. The node data for the individual nodes of the road system are provided separately from the link row data, and to identify nodes, node identifiers are provided for the nodes of the road system. The link data includes information indicating a node identifier for a node that is located at one link end defined in the direction of the link row.

Claims

1. A data structure for map data comprising:

node data which indicates information concerning nodes that represent points along a road;

link data which indicates information concerning a link that represents a road between the points;

a link row which represents a series of roads as a series of links in a road system;

link row data in which the link data for links constituting the link row are arranged in the order that the links are connected; and

a node identifier which identifies the nodes,

wherein

the road system is expressed by using the nodes and the links;

the node data for each of the nodes of the road system are provided separately from the link row data;

the node identifiers are provided for each of the nodes of the road system; and

the link data include information that indicates the node identifier for a node located at one link end that is defined in accordance with the direction of the link row.

2. The data structure for map data according to claim 1, wherein node numbers representing an arrangement of the node data are employed as the node identifiers.

3. The data structure for map data according to claim 1, wherein

connected link information representing links connected to a node are provided in response to each of the node, and includes connected link designation information in response to a link row that the links belong to;

and

the connected link designation information depicts a link that is selected from a corresponding link row in accordance with a direction of the link row.

4. The data structure for map data according to claim 2, wherein

connected link information representing links connected to a node are provided in response to each of the node, and includes connected link designation information in response to a link row that the links belong to;

and

the connected link designation information depicts a link that is selected from a corresponding link row in accordance with a direction of the link row.

5. The data structure for map data according to claim 3, wherein the connected link designation information depicts a link by using a link row identifier, which is provided for a link row to identify the link row, and an intra-link-row link identifier, which is provided for a link, in accordance with the direction of the link row, to identify a link in the link row.

6. The data structure for map data according to claim 3, wherein

for each of the link row, one link is selected from links connected to a node in accordance with the direction of a link row;

and

a node-base link identifier is provided to the link to identify the selected link.

7. The data structure for map data according to claim 3, wherein

in a case where a link is divided, link row data are provided for a link row segment consisting of a link row composed of link segments obtained by dividing the link;

and

link data for the link segments include information concerning the link row segment.

8. The data structure for map data according to claim 1, wherein node associated information is provided for a node and includes a node identifier for an associated node.

20. A map data processing apparatus comprising:

a map data acquisition unit for obtaining map data having a data structure according to any one of claims 1 to 10;

a map update data acquisition unit for obtaining map update data used to update the map data; and

a map data updating unit for employing the map update data obtained by the map update data acquisition unit to update the map data obtained by the map data acquisition unit.

9. A data structure for map data comprising:

nodes representing points along a road;

links representing the road between the points; and

link numbers within a specific range are provided for the links in a road system respectively,

wherein

the road system is expressed by using the nodes and the links;

the link numbers within the specific range provided for a before-division link are distributed to link segments obtained by division; and

the range for link numbers for the link segments obtained by the distribution is determined in accordance with a range obtained by equally dividing the specific range for the link numbers of the before-division link.

10. A data structure for map data comprising:

nodes representing points along a road;

links representing the road between the points; and

link numbers within a specific range are provided for the links in a road system respectively,

wherein

the road system is expressed by using the nodes and the links;

the link numbers within the specific range provided for a before-division link are distributed to link segments obtained by division; and

the range for link numbers for the link segments obtained by the distribution is determined in accordance with a ratio of link lengths of the link segments to a link length of the before-division link.

11. An updating method for map data that has a data structure including

node data which indicates information concerning nodes that represents points along a road;

link data which indicates information concerning a link that represents a road between the points;

a link row which provides a series of roads as a series of links in a road system;

link row data in which the link data for links constituting the link row are arranged in the order that the links are connected; and

a node identifier which identifies the nodes,

wherein

the road system is expressed by using the nodes and the links;

the node data for each of the nodes of the road system are provided separately from the link row data;

the node identifiers are provided for each of the nodes of the road system;

node numbers representing an arrangement of the node data are employed as the node identifiers; and

the link data include information that indicates the node identifier for a node located at one link end that is defined in accordance with the direction of the link row,

the updating method comprising a step of;

updating the map data while node identifiers for conventional existing nodes are not changed, in a case where a node is discontinued or established.

12. An updating method for map data that has a data structure including

node data which indicates information concerning nodes that represents points along a road;

link data which indicates information concerning a link that represents a road between the points;

a link row which provides a series of roads as a series of links in a road system;

link row data in which the link data for links constituting the link row are arranged in the order that the links are connected; and

a node identifier which identifies the nodes,

wherein

the road system is expressed by using the nodes and the links;

the node data for each of the nodes of the road system are provided separately from the link row data;

the node identifiers are provided for each of the nodes of the road system;

the link data include information that indicates the node identifier for a node located at one link end that is defined in accordance with the direction of the link row;

connected link information representing links connected to a node are provided in response to each of the node, and includes connected link designation information in response to a link row that the links belong to;

the connected link designation information depicts a link that is selected from a corresponding link row in accordance with a direction of the link row; and

the connected link designation information depicts a link by using a link row identifier, which is provided for a link row to identify the link row, and an intra-link-row link identifier, which is provided for a link, in accordance with the direction of the link row, to identify a link in the link row,

the updating method comprising a step of;

updating the map data while, at least, either link row identifiers for conventional existing link rows or intra-link-row link identifiers for conventional existing links are not changed, in a case where a link is discontinued or established.

13. An updating method for map data that has a data structure including

node data which indicates information concerning nodes that represents points along a road;

link data which indicates information concerning a link that represents a road between the points;

a link row which provides a series of roads as a series of links in a road system;

link row data in which the link data for links constituting the link row are arranged in the order that the links are connected; and

a node identifier which identifies the nodes,

wherein

the road system is expressed by using the nodes and the links;

the node data for each of the nodes of the road system are provided separately from the link row data;

the node identifiers are provided for each of the nodes of the road system;

the link data include information that indicates the node identifier for a node located at one link end that is defined in accordance with the direction of the link row;

connected link information representing links connected to a node are provided in response to each of the node, and includes connected link designation information in response to a link row that the links belong to;

the connected link designation information depicts a link that is selected from a corresponding link row in accordance with a direction of the link row; and

the connected link designation information depicts a link by using a link row identifier, which is provided for a link row to identify the link row, and an intra-link-row link identifier, which is provided for a link, in accordance with the direction of the link row, to identify a link in the link row,

the updating method comprising a step of;

employed link row data obtained by updating to update the connected link information, in a case where a link is discontinued or established.

14. An updating method for map data that has a data structure including

nodes representing points along a road;

links representing the road between the points; and

link numbers within a specific range are provided for the links in a road system respectively,

wherein

the road system is expressed by using the nodes and the links,

the updating method comprising steps of;

distributing the link numbers within the specific range provided for a before-division link to link segments obtained by division; and

determining the range for link numbers for the link segments obtained by the distribution in accordance with a range obtained by equally dividing the specific range for the link numbers of the before-division link.

15. An updating method for map data that has a data structure including

nodes representing points along a road;

links representing the road between the points; and

link numbers within a specific range are provided for the links in a road system respectively,

wherein

the road system is expressed by using the nodes and the links,

the updating method comprising steps of;

distributing the link numbers within the specific range provided for a before-division link to link segments obtained by division; and

determining the range for link numbers for the link segments obtained by the distribution in accordance with a ratio of link lengths of the link segments to a link length of the before-division link.

16. A map data storage medium in which map data is stored, the map data comprising:

node data which indicates information concerning nodes that represents points along a road;

link data which indicates information concerning a link that represents a road between the points;

a link row which provides a series of roads as a series of links in a road system;

link row data in which the link data for links constituting the link row are arranged in the order that the links are connected; and

a node identifier which identifies the nodes,

wherein

the road system is expressed by using the nodes and the links;

the node data for each of the nodes of the road system are provided separately from the link row data;

the node identifiers are provided for each of the nodes of the road system;

node numbers representing an arrangement of the node data are employed as the node identifiers; and

the link data include information that indicates the node identifier for a node located at one link end that is defined in accordance with the direction of the link row.

21. A map data processing apparatus comprising:

a map data reading unit for reading map data stored in a map data storage medium according to any one of claims 16 to 19;

a map update data acquisition unit for obtaining map update data used to update the map data stored in the map data storage medium; and

a map data updating unit for employing the map update data obtained by the map update data acquisition unit to update the map data read by the map data reading unit.

17. A map data storage medium in which map data is stored, the map data comprising:

node data which indicates information concerning nodes that represents points along a road;

link data which indicates information concerning a link that represents a road between the points;

a link row which provides a series of roads as a series of links in a road system;

link row data in which the link data for links constituting the link row are arranged in the order that the links are connected; and

a node identifier which identifies the nodes,

wherein

the road system is expressed by using the nodes and the links;

the node data for each of the nodes of the road system are provided separately from the link row data;

the node identifiers are provided for each of the nodes of the road system;

node numbers representing an arrangement of the node data are employed as the node identifiers;

the link data include information that indicates the node identifier for a node located at one link end that is defined in accordance with the direction of the link row;

connected link information representing links connected to a node are provided in response to each of the node, and includes connected link designation information in response to a link row that the links belong to; and

the connected link designation information depicts a link that is selected from a corresponding link row in accordance with a direction of the link row.

18. A map data storage medium in which map data is stored, the map data comprising:

nodes representing points along a road;

links representing the road between the points; and

link numbers within a specific range are provided for the links in a road system respectively,

wherein

the road system is expressed by using the nodes and the links;

the link numbers within the specific range provided for a before-division link are distributed to link segments obtained by division; and

the range for link numbers for the link segments obtained by the distribution is determined in accordance with a range obtained by equally dividing the specific range for the link numbers of the before-division link.

19. A map data storage medium in which map data is stored, the map data comprising:

nodes representing points along a road;

links representing the road between the points; and

link numbers within a specific range are provided for the links in a road system respectively,

wherein

the road system is expressed by using the nodes and the links;

the link numbers within the specific range provided for a before-division link are distributed to link segments obtained by division; and

the range for link numbers for the link segments obtained by the distribution is determined in accordance with a ratio of link lengths of the link segments to a link length of the before-division link.