Data structure of digital map file

• US 6,636,802 B1
• Filed: 05/23/2001
• Issued: 10/21/2003
• Est. Priority Date: 11/24/1998
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Ihara, Yasuhiro, Fukuda, Hisaya, Suzuki, Akihiro, Nakano, Nobuyuki, Ueyama, Yoshiki
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US09/856,541
• Time in Patent Office: 881 Days
• Field of Search: 701/208, 701/207, 701/209, 701/210, 701/211, 701/212, 701/213, 701/23, 701/24, 701/25, 342/357, 340/990, 340/995, 340/450, 340/451, 340/457
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3896 Transmission of map data from central databases

Abstract

A terminal device for reading a cartographic file in which updating one cartographic file does not require updating cartographic files in the neighboring units. For this purpose, cartographic files which represent respective units extracted by dividing a map into a plurality of areas each comprise node records generated for respective nodes and link records generated for respective links. Given node records contain coordinate information about neighboring nodes which define connections of roads between its unit and a neighboring unit. The cartographic files are stored in a first storage device. The data processing portion executes a process of searching for a route by using the cartographic files. During the route search, the data processing portion traces the connection from a road in one unit to a road in another, neighboring, unit on the basis of the coordinate information about the neighboring nodes of said one unit and said neighboring another unit.

Claims

1. A terminal device for reading a cartographic file from a storage device in which cartographic files are stored as digital data generated about individual units defined by dividing a map into a plurality of areas, wherein:

each said unit containing a road network represented by nodes and links, each of the cartographic file comprises node records generated for respective nodes and link records generated for respective links;

the node records each containing information about a non-neighboring node representing an intersection on the road network or information about a neighboring node defining a connection of roads between its unit and another unit adjoining said unit; and

the information about the neighboring node being coordinate information about the neighboring node;

said terminal device comprising;

an input device responsive to an operation by a user for generating information specifying a map area;

a data processing portion for specifying a record region where a necessary cartographic file is stored on the basis of the information generated by said input device; and

a read control portion for reading the cartographic file from said storage device on the basis of the record region specified by said data processing portion;

wherein said data processing portion performs a given process by using the node records and the link records recorded in the cartographic file read by said read control portion; and

wherein said data processing portion traces a connection from a road in one unit to a road in another neighboring unit on the basis of the coordinate information about the neighboring nodes of the one unit and the neighboring another unit.

2. The terminal device according to claim 1, wherein each link record contains attribute information which shows an attribute of the road represented by said link;

and

said data processing portion traces the connection from the road in the one unit to the road in the neighboring another unit also on the basis of the attribute information about the links connected to the neighboring nodes of the one unit and the neighboring another unit.

3. The terminal device according to claim 1, wherein the node records which contain the information about the neighboring nodes are successively recorded in each cartographic file.

4. The terminal device according to claim 3, wherein said data processing portion traces the connection from the road in the one unit to the road in the neighboring another unit by searching only the node records which contain the information about the neighboring nodes in the cartographic file representing the neighboring another unit.

5. The terminal device according to claim 1, wherein in each cartographic file, the node records which contain the information about neighboring nodes are successively recorded in an ascending or descending order of the coordinates of the neighboring nodes.

6. The terminal device according to claim 5, wherein said data processing portion traces the connection from the road in the one unit to the road in the neighboring another unit by searching only the node records which contain the information about the neighboring nodes in the cartographic file representing the neighboring another unit.

7. The terminal device according to claim 1, wherein in each cartographic file, the node records which contain the information about the neighboring nodes are successively recorded in an order in which the neighboring nodes follow one after another in one direction along the boundary of the unit.

8. The terminal device according to claim 7, wherein when said data processing portion traces the connection from the road in the one unit to the road in the neighboring another unit, said data processing portion searches, in the cartographic file representing the neighboring another unit, only the node records which contain the information about the neighboring nodes which are located on the boundary between the neighboring another unit and the one unit, in an order reverse to the order in which the node records of the one unit are recorded.

9. The terminal device according to claim 3, wherein the units are formed by dividing the map into polygonal areas, and

in each cartographic file, the node records which contain the information about the neighboring nodes located on each side of the unit are successively recorded.

10. The terminal device according to claim 9, wherein said data processing portion traces the connection from the road in the one unit to the road in the neighboring another unit by searching, in the cartographic file representing the neighboring another unit, only the node records which contain the information about the neighboring nodes which are located on a given side of the neighboring unit,

wherein the given side of the neighboring unit adjoins the side of the one unit to which the neighboring nodes belong.

11. The terminal device according to claim 9, wherein the node records which contain the information about the neighboring nodes located on each side of the unit are recorded in an ascending or descending order of the coordinate information about the neighboring nodes.

12. The terminal device according to claim 11, wherein when said data processing portion traces the connection from the road in the one unit to the road in the neighboring another unit, said data processing portion searches, in the cartographic file representing the neighboring another unit, only the node records which contain the information about the neighboring nodes located on a given side of the neighboring unit, in the order in which said node records are recorded;

and

wherein the given side of the neighboring unit adjoins the side of said one unit to which the neighboring nodes belong.

13. A terminal device for reading a cartographic file from a storage device in which cartographic files are stored as digital data generated for individual units formed by dividing a map into a plurality of areas, wherein

each of the cartographic files stored in the storage device is provided with a file name uniquely corresponding to the map area represented by itself;

said terminal device comprising;

an input device responsive to an operation by a user for generating information specifying a map area;

a data processing portion for specifying a record region where a necessary cartographic file is recorded on the basis of the information generated by said input device; and

a read control portion for reading the cartographic file from the storage device on the basis of the record region specified by said data processing portion.

14. The terminal device according to claim 13, wherein:

each unit contains a road network represented by nodes and links, and each cartographic file comprises node records generated for respective nodes and link records generated for respective links;

said data processing portion performs a process of searching for a route by using the node records and the link records recorded in the cartographic file which said read control portion has read this time; and

when the route search ends in the area which the cartographic file read in this time represents, said data processing portion calculates a map area required for a further route search and specifies a record region where a cartographic file to be read next is stored on the basis of the calculated map area.

15. A terminal device for reading a cartographic file from a storage device in which cartographic files are stored as digital data generated for individual units formed by dividing a map into a plurality of areas, wherein:

each of the unit contains a background which is divided into objects each capable of being drawn with one stroke, the plurality of objects being grouped so that ones having the same attribute are contained in the same group; and

the cartographic file contains background records in which information about the objects is recorded for each group;

said terminal device comprising;

an input device responsive to an operation by a user for generating information specifying a map area;

a data processing portion for specifying a record region where a necessary cartographic file is stored on the basis of the information generated by said input device;

a read control portion for reading the cartographic file from the storage device on the basis of the record region specified by said data processing portion; and

an output device;

wherein said data processing portion causes said output device to display the background on the basis of the background records contained in the cartographic file read by said read control portion.

16. The terminal device according to claim 15, wherein

each object comprises element points representing a shape;

each background record contains coordinate values of the element points of each object, the coordinate values being arranged in the order in which the element points are traced in the one stroke; and

the coordinate values of the element points are each represented by an absolute coordinate value based on an origin in the unit or by a relative coordinate value with respect to the coordinate value of another element point.

17. The terminal device according to claim 15, wherein, in each object, the element point which corresponds to a pen-down position is represented by the relative coordinate value when a given condition is satisfied.

18. The terminal device according to claim 17, wherein the given condition is satisfied when the distance between the pen-down position and the pen-up position immediately before is equal to or smaller than a given value.

19. The terminal device according to claim 17, wherein the given condition is satisfied when the relative coordinate value of the element point corresponding to the pen-down position can be represented in a predetermined or smaller number of bits.

20. The terminal device according to claim 15, wherein in each object, the element points are each represented by a direct coordinate value when a given condition is satisfied.

21. The terminal device according to claim 19, wherein the given condition is satisfied when the distance between an element point and the element point immediately before is equal to or larger than a given value.

22. The terminal device according to claim 19, wherein the given condition is satisfied when the coordinate value of the element point represented by the relative coordinate value exceeds a predetermined number of bits.

23. A recording medium in which cartographic files are recorded as digital data generated for individual units formed by dividing a map into a plurality of areas, the cartographic files having a predetermined data structure for reading by a computer device, said recording medium comprising:

node records generated for respective nodes which form a road network in the unit in each cartographic file; and

link records generated for respective links which form the road network in the unit in each said cartographic file;

said node records each containing information about a non-neighboring node which represents an intersection on the road network, or coordinate information showing coordinates of a neighboring node which defines a connection of roads between a unit and a unit adjoining said unit;

wherein said recording medium allows the computer device to;

generating area information specifying a map area in response to an operation by a user;

specify a record region where a required cartographic file is recorded on the basis of the generated area information;

read the cartographic file on the basis of the specified record region; and

while searching for a route by using the node records and the link records recorded in the read cartographic file, trace a connection from a road in one unit to a road in another neighboring unit on the basis of the coordinate information about the neighboring nodes of the one unit and the neighboring another unit.

24. The recording medium which contains the cartographic files according to claim 23, wherein:

each of said link record contains attribute information which shows an attribute of the road represented by said link; and

while searching for a route, the computer device traces the connection from the road in the one unit to the road in the neighboring another unit also on the basis of the attribute information about the links connected to the neighboring nodes of the one unit and the neighboring another unit.

25. The recording medium which contains the cartographic files according to claim 23, wherein said node records which contain the information about the neighboring nodes are successively recorded.

26. The recording medium which contains the cartographic files according to claim 23, wherein said node records which contain the information about the neighboring nodes are successively recorded in an ascending or descending order of the coordinates of the neighboring nodes.

27. The recording medium which contains the cartographic files according to claim 23, wherein said node records which contain the information about the neighboring nodes are successively recorded in an order in which the neighboring nodes follow one after another in one direction along the boundary of the unit.

28. A recording medium in which predetermined data is recorded for reading by a computer device, and in which cartographic files are recorded as digital data generated for individual units formed by dividing a map into a plurality of areas, having a structure, said recording medium comprising:

the cartographic files as digital data generated for the individual units formed by dividing the map into a plurality of areas; and

management information for managing record regions where said cartographic files are recorded, where said cartographic files are provided with names represented in a tree structure;

wherein said recording medium allows the computer device to;

when area information specifying a map area is entered from outside, specify the name of a necessary cartographic file on the basis of the input area information; and

reading the cartographic file from the record region uniquely corresponding to the name of the specified cartographic file by referring to said management information.

29. A recording medium in which cartographic files are recorded as digital data generated for individual units formed by dividing a map into a plurality of areas, said cartographic files having a predetermined data structure for reading by a computer device, wherein:

each of the unit containing backgrounds, each background being divided into objects each capable of being drawn with one stroke;

wherein said recording medium comprises;

information which show attributes of the backgrounds; and

object records which contain information required to draw the objects;

wherein said information showing the attributes of the backgrounds and said object records of the objects are successively recorded so that the plurality of objects are grouped according to their respective attributes; and

wherein said recording medium allows said computer device to draw a map on the basis of said attribute information about the backgrounds and said object records contained in the cartographic file.

30. The recording medium which contains the cartographic files according to claim 29, wherein each object comprises element points representing a shape of the object;

and

each of said object records contains coordinate values of the element points of its object, said coordinate values being arranged in an order in which the element points are traced in the one stroke; and

wherein the coordinate values of said element points are each represented by an absolute coordinate value based on an origin in the unit or by a relative coordinate value with respect to the coordinate value of another element point.

31. The recording medium which contains the cartographic files according to claim 29, wherein in each object, the element point which corresponds to a pen-down position is represented by the relative coordinate value when a given condition is satisfied.

32. The terminal device according to claim 29, wherein in each object, the element points are each represented by a direct coordinate value when a given condition is satisfied.

33. A terminal device for reading a cartographic file from a storage device in which cartographic files are stored as digital data generated for individual units formed by dividing a plurality of maps on different scales each into a plurality of areas, wherein:

the plurality of cartographic files have a hierarchical structure based on the scales, each unit containing a road network represented by nodes and links, each cartographic file at least containing node records which are generated for respective nodes and contain coordinate information about nodes, and link records which are generated for respective links; and

in each cartographic file, the node records are recorded in an ascending or descending order of the coordinate information about the nodes;

said terminal device comprising;

an input device for generating information specifying a map area;

a data processing portion for specifying a record region where a necessary cartographic file is recorded on the basis of the information generated by said input device; and

a read control portion for reading the cartographic file from the storage device on the basis of the record region specified by said data processing portion;

wherein said data processing portion searches for a node in a unit at a higher level which corresponds to a node contained in a unit at a lower level on the basis of the coordinate information recorded in the cartographic file read by said read control portion.

34. The terminal device according to claim 33, wherein said data processing portion searches for the node in the unit at the higher level corresponding to the node contained in the unit at the lower level also on the basis of the order in which the node records are recorded.

35. A system in which a center station provides a cartographic file to a terminal device through a transmission path, said system comprising:

said center station which comprises;

a first storage device containing the cartographic file, the cartographic file representing a map of a predetermined area;

a read control portion for reading, as cartographic data, part or all of the cartographic file from said first storage device;

a packet assembler for assembling packets in a form appropriate for the transmission path by using the cartographic data read by said read control portion; and

a transmitting portion for transmitting the packets assembled by said packet assembler to said terminal device through the transmission path;

said terminal device which comprises;

a receiving portion for receiving the packets transmitted by said transmitting portion through the transmission path;

a data processing portion for disassembling the packets received by said receiving portion and restoring the cartographic data; and

a second storage device having an internal storage medium for storing a cartographic file;

wherein when a cartographic file related to the cartographic data restored this time is already stored in said second storage device, said data processing portion reads that cartographic file from said second storage device, and said data processing portion performs the process of adding the restored cartographic data to the second cartographic file thus read and stores the cartographic file in said second storage device.

36. The map providing system according to claim 35, wherein said data processing portion generates a plurality of cartographic files when necessary.

37. The map providing system according to claim 35, wherein the cartographic file comprises a plurality of units in which the map of predetermined area is sectioned into a plurality of areas and management information for managing each of the units, and wherein in said center station:

said read control portion reads the cartographic data, unit by unit, from the cartographic file stored in said first storage device; and

said packet assembler assembles the packets by using the unit read by said read control portion, a file ID specifying the cartographic file, a unit ID specifying the unit, and data size of the unit.

38. The map providing system according to claim 37, wherein said data processing portion further extracts the file ID, the unit ID and the data size from the packets received at said receiving portion;

and

said data processing portion disassembles the packets received at said receiving portion and restores the cartographic data by using the extracted file ID, unit ID and data size.

39. The map providing system according to claim 35, wherein the cartographic file further comprises basic data schematically showing the predetermined area and detailed data showing the area in detail;

and

the basic data and the detailed data have data structures which can be separated from each other.

40. The map providing system according to claim 39, wherein:

the basic data further comprises basic background data representing background of the map, basic character/symbol data schematically representing a character and a symbol to be displayed in the map, and major road network data representing a major road network existing in the map;

the detailed data further comprises detailed background data representing details of the background of the map, detailed character/symbol data representing a detailed character and symbol to be displayed in the map, and minor road network data representing a minor road network existing in the map; and

the detailed background data, the detailed character/symbol data and the minor road network data are formed as differential data of the basic background data, the basic character/symbol data and the major road network data, and the basic data and the detailed data are combined to represent a relatively detailed map.

41. The map providing system according to claim 39, wherein said read control portion further reads, as the cartographic data, only the basic data contained in the cartographic file stored in said first storage device.

42. The map providing system according to claim 41, wherein said read control portion further reads, as the cartographic data, only the detailed data contained in the cartographic file stored in said first storage device.

43. The map providing system according to claim 39, wherein said read control portion further reads, as the cartographic data, the basic data and the detailed data contained in the cartographic file stored in said first storage device.

44. The map providing system according to claim 41, wherein said data processing portion further disassembles the packets received by said receiving portion to restore the basic data.

45. The map providing system according to claim 44, wherein said read control portion in said center station further reads, as the cartographic data, only the detailed data contained in the cartographic file stored in said first storage device;

and

said data processing portion in said terminal device further disassembles the packets received by said receiving portion to restore the detailed data.

46. The map providing system according to claim 43, wherein said data processing portion further disassembles the packets received at said receiving portion to restore the basic data and the detailed data.