Method of storing a topological network, and methods and apparatus for identifying series of 1-cells in a network stored by such a method

• US 5,754,846 A
• Filed: 10/01/1991
• Issued: 05/19/1998
• Est. Priority Date: 10/01/1990
• Status: Expired due to Fees

• Current Assignee: Mannesmann VDO AG (Continental AG)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Driessen, Leonardus M. H. E., Janse, Cornelis P.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US07/769,613
• Time in Patent Office: 2,422 Days
• Field of Search: 364/443, 364/444, 364/448, 364/420, 364/449, 364/449.1, 364/449.4, 364/449.5, 365/189.01, 365/600, 395/800, 395/325, 395/611, 395/615, 340/990, 340/995
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A topological network, comprising a set of 0-cells (nodes) (28, 29) interconnected by a set of 1-cells (aa, bb, . . . , gg)₁ is divided into sections (E, F, G) corresponding to discrete parcels of data for storage in a mass memory such as a CD-ROM. A boundary node (28, 29) is defined at each point where the network traverses a boundary between sections. The parcel of data for a given section includes a chain list record for each 1-cell in the section, which chain list record generally refers directly (TP) to a further 1-cell in the network terminating at the same node. However, no chain list record refers directly to a 1-cell outside the section of the network to which the data parcel relates. An indirect reference (0-C'"'"') across the section boundary can be made easily, while an overall saving in data volume is obtained compared with a known method. Further information can be introduced into the data parcels by ordering techniques, enabling the network data to be used in a particularly efficient and systematic manner.

Claims

1. A computer-implemented method for arranging digital data representing a topological network in a memory, the network comprising a set of 0-cells (nodes) and a set of 1-cells and being divided into sections, a boundary node being defined at each point where the network traverses a boundary between sections, comprising:

storing discrete parcels of data corresponding to each section of the topological network in a mass memory;

for a given section, storing in the data parcel a chain list record for each 1-cell in the section and

storing in each chain list record for a 1-cell terminating at a non-boundary node, a reference to a further 1-cell in the same section of the network terminating at the same node, such that no chain list record in a data parcel refers directly to a 1-cell outside the section of the network to which that data parcel relates.

2. A method as claimed in claim 1, comprising:

storing, in the data parcel for a given section of the network, a node list record for each node in the section; and

storing, in the node list record for a boundary node in a given section, a reference to a corresponding node in an adjacent section, and a thread pointer referring to a 1-cell in the given section, but no direct reference to any 1-cell outside the given section.

3. A method as claimed in claim 2, comprising storing, in the chain list record for a 1-cell, references to a first and a second node which terminate the 1-cell and corresponding first and second thread pointers each indicating a further 1-cell terminated by the first or second node respectively, except that where a node referred to in a chain list record is a boundary node and no further 1-cell in the same section remains to be indicated, storing, in the space allocated for the thread pointer, a special pointer indicating that the node is a boundary node.

4. A method as claimed in claim 3 comprising choosing for inclusion the further 1-cell indicated by each thread pointer in a chain list record by following a particular sense of rotation about the terminating node and wherein the thread pointer in the node list record for each boundary node indicates the first 1-cell within the section, counting from the section boundary in the particular sense of rotation about the boundary node.

5. A method as claimed in claim 4 comprising:

for a boundary node located on the boundary of three or more sections, choosing for inclusion the node list record to refer to the corresponding boundary node only in the section following next in the particular sense of rotation.

6. A method as claimed in claim 4 comprising including, in the data parcel for a section of the network, information linking the boundary nodes in accordance with a sense of rotation around the section boundary which is opposite to the particular sense of rotation according to which the 1-cells are indicated by the thread pointers in the chain list records.

7. The method of claim 1, further comprising identifying for processing a series of 1-cells forming a route through a topological network represented by the data parcels stored in the mass memory given a current 1-cell and direction of traversing that 1-cell, the method comprising repeatedly finding a further 1-cell by

(a) selecting from the chain list record the current 1-cell the terminating node in the given direction of traversing the 1-cell;

and

(b) selecting for processing from that chain list record a reference to a further 1-cell leading from said terminating node;

wherein, in a case where the terminating node is a boundary node and, in step (b), the chain list record is found to contain to direct reference to a further 1-cell leading from the boundary node, a step (b1) is performed which comprises using information outside the chain list record to locating for processing a reference to a further 1-cell in an adjacent section of the network each time making a further 1-cell a new current 1-cell, and each time traversing the current 1-cell only if it forms a part of the desired route.

8. A method of identifying a further 1-cell, given a current 1-cell and a direction of traversing that 1-cell in a topological network section represented by a data parcel stored in a mass memory in accordance with claim 2, the method comprising the steps of:

(a) finding in the chain list record for the current 1-cell the terminating node in the given direction of traversing the 1-cell; and

(b) looking in that chain list record for a reference to a further 1-cell leading from said terminating node;

wherein, in a case where the terminating node is a boundary node and, in step (b), the chain list record is found to contain no direct reference to a further 1-cell leading from the boundary node, a step (b1) is performed which comprises using information outside the chain list record to find a reference to a further 1-cell in an adjacent section of the network.

9. A method as claimed in claim 8, wherein the step (b1) comprises using the node list record for that node to identify the corresponding node in an adjacent section of the network and using the thread pointer of the corresponding node list record in a data parcel representing the corresponding node into the adjacent network section.

10. A method of identifying a further 1-cell, given a current 1-cell and a direction of traversing that 1-cell in a topological network section represented by a data parcel stored in a mass memory in accordance with claim 1, the method comprising the steps of:

(a) finding in the chain list record for the current 1-cell the terminating node in the given direction of traversing the 1-cell; and

(b) looking in that chain list record for a reference to a further 1-cell leading from said terminating node;

wherein, in a case where the terminating node is a boundary node and, in step (b), the chain list record is found to contain no direct reference to a further 1-cell leading from the boundary node, a step (b1) is performed which comprises using information outside the chain list record to find a reference to a further 1-cell in an adjacent section of the network.

11. A method of identifying a series of 1-cells which bound a particular 2-cell in a topological networks stored in accordance with a method as claimed in claim 10, the method comprising the steps of:

(c) choosing a first current 1-cell which bounds the particular 2-cell and choosing a direction so as to pass around the 2-cell in accordance with a sense of rotation opposite to the particular sense of rotation and

(d) using a method as claimed in claim 9 to identify a series of 1-cells, traversing the first 1-cell indicated by the thread pointer at each 0-cell until the first current 1-cell is reached again.

12. A method as claimed in claim 11, comprising the step, upon reaching a boundary node, of determining whether the part of the particular 2-cell lying beyond the section boundary is of interest and, if that part is not of interest, replacing the step (b) by a step (b2) which comprises identifying the next following boundary node on the section boundary, in accordance with the said opposite sense of rotation around the 2-cell boundary, and using the node list record for said next following boundary node to identify a further 1-cell of the series within the section boundary.

13. A mass memory device wherein are stored data parcels representing sections of a topological network, characterized in that the data are stored in accordance with a method as claimed in claim 1.

14. A device as claimed in claim 13 wherein the topological network is a road network and the mass memory device is a Compact Disc Read-Only Memory (CD-ROM).

15. An apparatus for reading a topological database stored in a mass memory device in accordance with a method as claimed in any of claims 1 to 6, the apparatus comprising:

means for reading from a mass memory device a first data parcel representing a first section of a topological network;

means for reading from the data parcel a chain list record corresponding to a 1-cell in the first section of the network, which chain list record, for a given node terminating the 1-cell, may or may not refer directly to a further 1-cell in the first section which is also terminated by that node;

means responsive to the reading of a chain list record which does not refer directly to such a further 1-cell for using information outside the chain list record for the node to identify an adjacent second section of the network; and

means for reading a second data parcel for the second section of the network and for using information in the second data parcel to identify a further 1-cell leading from the corresponding boundary node into the second section of the network.

16. A computer readable storage medium embodying a data structure for storing electronic map data, the electronic map being composed of a plurality of discrete parcels, each parcel comprising at least one 1-cell and at least two 0-cells, the data structure comprising:

a plurality of respective chain lists, each respective chain list being for listing 1-cells from a respective one of the discrete parcels, each 1-cell being stored with an indication of 0-cells which are end points of the 1-cell, none of the chain lists containing any reference to any feature of any discrete parcel other than the respective discrete parcel; and

a plurality of respective node lists, each respective node list being for listing 0-cells for a respective one of the discrete parcels, each 0-cell being stored with an indication of those 1-cells within the respective discrete parcel that are connected with that 0-cell, at least one of the 0-cells being also stored with an indication of a connection to a 0-cell outside the respective discrete parcel, none of the node lists containing any reference to a 0-cell outside the respective discrete parcel.

17. The medium of claim 16 wherein, at least one of the chain lists includes for a particular 1-cell, at least one thread pointer connecting that particular 1-cell to a second 1-cell via one of the end points of that particular 1-cell.

18. The medium of claim 17 wherein a plurality of thread pointers are listed for the particular 1-cell in a particular sense of rotation about the one of the end points.

19. The medium of claim 16 wherein, for a 1-cell located at a boundary of three or more of the discrete parcels, a node list record refers to a corresponding 1-cell only in the discrete parcel following next in a particular sense of rotation.

20. The medium of claim 17 wherein when the one of the end points is on a boundary of the respective discrete parcel for that particular 1-cell, the thread pointer indicates that the one of the end points is a boundary node.