Apparatus storing a presentation of topological structures and methods of building and searching the representation

• US 5,694,534 A
• Filed: 12/13/1996
• Issued: 12/02/1997
• Est. Priority Date: 07/25/1985
• Status: Expired due to Term

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Loughmiller, George E. Jr., White, Marvin S. Jr.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): HONG, STEPHEN S
• Application Number:
  US08/766,646
• Time in Patent Office: 354 Days
• Field of Search: 395/133, 395/140, 395/141, 395/121, 395/128, 364/449, 364/474.28, 364/603, 364/615, 340/988, 340/995
• US Class Current: 345/440
• CPC Class Codes: G01C 15/00 Surveying instruments or accessories not provided for in groups G01C1/00 - G01C13/00
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

A data storage medium storing a representation of a topological structure having topological features, on which is stored a digital data base including a plurality of carrier blocks of data representing the topological features t a given level of detail, each one of the carrier blocks being a representation of a carrier which is a closed set containing in its interior a given topological object. Also disclosed are methods for building the carrier blocks, for building a hierarchy of carrier blocks, and for searching the digital data base at all hierarchical levels.

Claims

1. Apparatus storing a representation of a topological structure having topological features, comprising:

a) a data storage medium; and

b) a digital data base stored on said data storage medium, said digital data base including a plurality of carrier blocks of data representing the topological features at a given level of detail, said data of each one of said carrier blocks being a representation of a carrier which is a closed set including in its interior a given topological object, and wherein said closed set is a smallest closed set and is a sub-complex X_i of a topological complex X, the sub-complex X_i having a set of n-cells, where 0≦

n≦

the dimension of the topological structure and the totality of said plurality of carrier blocks covers the topological complex X.

2. Apparatus, according to claim 1, wherein the areal coverage of the features of one portion of the topological structure provided by one said sub-complex X_i of one said carrier block may be larger than the areal coverage of the features of another portion of the topological structure provided by another sub-complex X_j of another said carrier block for i≠

j.

3. Apparatus, according to claim 2, wherein the size of each said carrier block of data is substantially the same as the size of each other said carrier block of data.

4. Apparatus, according to claim 3, wherein said data of each one of said carrier blocks are stored in bytes, and wherein the number of bytes in each said carrier block is substantially the same to provide said substantially the same size of carrier blocks.

5. Apparatus, according to claim 1, wherein said sub-complex X_i has an interior which is disjoint from the interior of another sub-complex X_j of said complex X for i≠

j, and wherein said sub-complexes X_i and X_j are topologically mutually adjacent having a common border.

6. Apparatus, according to claim 1, wherein n=0, 1 and 2.

7. Apparatus, according to claim 1, wherein the topological structure is a geographical area and wherein said digital data base corresponds to a map of the geographical area and said sub-complex X_i represents a certain portion of the geographical area.

8. Apparatus, according to claim 1, wherein adjacent carriers have a common boundary and only one of the carrier blocks representing one of the adjacent carriers has data identifying said boundary.

9. A method of building a digital data base representing a given topological structure, using a programmed computer, the digital data base having first and second levels of carrier blocks of data that are topologically equivalent, each of said carrier blocks of said first level having a topological sub-complex X_i corresponding to an element A_i of a partition P at the first level, each said sub-complex X_i having n-cells, where n=0, 1, 2 . . . , and the 2-cells c²_i of the sub-complex X_i being mutually adjacent, and where the totality of the carrier blocks of data of the first level constitute a topological complex X, and the totality of the carrier blocks of data of the second level constitute a topological complex X'"'"', comprising the steps of:

a) providing each said sub-complex X_i on a data storage medium;

b) for each said sub-complex X_i, fusing all the 2-cells c²_i in one said sub-complex X_i to form a single 2-cell c'"'"'²_i ;

c) identifying a 1-complex of 1-cells c¹_i on the boundary of the single 2-cells c'"'"'_2i and the 0-cells c⁰_i bounding those 1-cells c¹_i, where those 0-cells c⁰_i incident to t 1-cells c¹_i are essential 0-cells c⁰_i, where t=2;

d) constructing connected chains of 1-cells c¹_i so that each chain c¹_i is bounded by the essential 0-cells c⁰_i, where these chains of 1-cells c¹_i are common to adjacent sub-complexes X_i or on the boundary of the entire complex X;

e) fusing each chain of 1-cells c¹_i to form a 1-cell c'"'"'¹_i ; and

f) for each essential 0-cell c⁰_i, creating a chain of 0-cells c⁰_k having a single 0-cell and mapping this chain into the 0-cell c'"'"'⁰_m as a copy of the essential 0-cell c⁰_i, whereby the n-cells c'"'"'²_i, c'"'"'¹_i and c'"'"'⁰_m constitute the topological complex X'"'"'.

10. A method, according to claim 9, wherein the step of fusing each chain of 1-cells c'"'"'_i comprises reducing the geometrical complexity of the 1-cells c'"'"'¹_i.

11. A method, according to claim 10, wherein the step of reducing comprises using a straightening algorithm.

12. A method, according to claim 9, further comprising iterating the steps a)-f) until a resulting topological complex X", X"'"'"' . . . does not exceed a given complexity threshold.

13. A method, according to claim 12, wherein the step of iterating comprises the steps of:

a) initially providing the complex X'"'"';

b) creating a fused complex X" using the steps a)-e) of claim 9 and then storing the fused complex X";

c) determining if the stored complex X" exceeds a given complexity threshold; and

d) if the given complexity threshold is exceeded by the complex X", setting X" as the initial complex and returning to step b) of claim 12.

14. A method of building a digital data base, representing a given topological structure, using a programmed computer, the digital data base corresponding to a complex X having a plurality of elements A_i ={c²_j } of a partition P and a plurality of n-cells corresponding to topological features of the topological structure, wherein n=0, 1, 2, comprising the steps of:

a) initializing a counter k;

b) selecting an arbitrary 2-cell c²_j in the complex X not already included in a prior element A_i in the partition P;

c) incrementing the counter k and initializing a register A_k storing element A_k to store only the selected 2-cell c²_j of a sub-complex X_k ;

d) adding all 1-cells and 0-cells incident to the selected 2-cells c²_j to provide a sub-complex X_k being a topological closed set;

e) selecting another 2-cell c²_j in the complex X not already included in a prior element A_i and adjacent a 2-cell c²_j in the sub-complex X_k ;

f) testing whether adding the 2-cell c²_j selected in step e) and all 1-cells and 0-cells incident thereto to the sub-complex X_k would cause the sub-complex X_k to exceed a given threshold of complexity;

g) going to step h) or step i) if the test of step f) does not or does show, respectively, the given threshold being exceeded or not being exceeded;

h) adding the 2-cell c²_j tested in step f) to register A_k and adjoining this 2-cell c²_j and all its incident 1-cells and 0-cells to keep the sub-complex X_k a closed set;

i) returning to step e);

j) since element A_k and sub-complex X_k are complete, adding element A_k to a register P storing the partition P and storing the sub-complex X_k ; and

k) going to step b) if there remains any 2-cell c²_j in some element A_i.

15. A method of searching a digital data base using a programmed computer, the digital data base having a hierarchy of levels of carrier blocks of data, each level in the hierarchy, constituting topological complexes X, X'"'"', X" . . . , each of the complexes X, X'"'"', X" . . . containing successively more generalized information and the complex containing the most generalized information being the root, each of the complexes X, X'"'"', X" . . . constituting n-cells, where n=0, 1,2 . . . and the digital data base representing a topological structure, comprising the steps of:

a) initializing a first list of selected cells and a second list of current carrier blocks;

b) setting the second list to be the root;

c) setting the current hierarchical level to be the root;

d) selecting from the second list of current carrier blocks, the 0-cells, 1-cells and 2-cells that fall within a specified range from a point;

e) exiting if the current hierarchical level is 0;

f) replacing the second list of current carrier blocks with another list containing one carrier block for each 2-cell at the current level in the first list of selected cells, whereby each said one carrier block of said other list is at the next level of the hierarchy;

g) decrementing the current level; and

h) returning to step d).

16. A method of searching a digital data base using a programmed computer, the digital date base having a plurality of carrier blocks at a given level constituting a topological complex, each of the carrier blocks containing topological n-cells, comprising the steps of:

a) initializing a first list of selected n-cells and a second list of current carrier blocks;

b) setting the second list of current carrier blocks to be a given carrier block;

c) selecting from the second list of current carrier blocks the n-cells that fall within a given range of a point;

d) exiting if no n-cells selected in step c) is on a boundary of a carrier corresponding to the carrier block to output the first list of selected n-cells;

e) for each n-cell in the first list, if the selected n-cell of step c) is on the boundary of a carrier and another carrier block corresponding to an adjacent carrier is not in the second list, adding that other carrier block to the second list; and

f) returning to step c).

17. A method of searching a digital data base using a programmed computer, the digital data base having a hierarchy of carrier blocks and each level in the hierarchy of carrier blocks of data constituting topological complexes X, X'"'"', X" . . . , each of the complexes containing successively more generalized information and the complex containing the most generalized information being the root, each of the complexes constituting topological n-cells, the method being searching from a lesser detailed hierarchical level to the root, comprising the steps of:

a) initializing a first list of selected cells and a second list of current carrier blocks;

b) setting the second list of current carrier blocks to a given carrier block;

c) selecting from the second list of current carrier blocks the n-cells that fall within a specified range of a point;

d) exiting if the current level is the root to output the first list of selected cells; and

e) replacing the current carrier blocks in the second list with a single carrier block at the next more generalized level in the hierarchy.

18. Apparatus storing a representation of a topological structure having topological features, comprising:

a) a data storage medium; and

b) a digital data base stored on said data storage medium, said digital data base including (i) a plurality of carrier blocks of data representing the topological features at a given level of detail, said data of each one of said carrier blocks of said plurality being a representation of a carrier which is a closed set including in its interior a given topological object, (ii) at least one other carrier block of data being in a hierarchical relationship with respect to said plurality of carrier blocks so as to represent the topological features at another level of detail, said at least one other carrier block representing a complex X'"'"' which is topologically equivalent to a complex X represented by said plurality of carrier blocks, and (iii) wherein said at least one other carrier block of said complex X'"'"' constitutes an index to said plurality of carrier blocks of said complex X.

19. Apparatus, according to claim 18, wherein a carrier of a carrier block at one level has the same boundary as a corresponding carrier of another carrier block at another level, and only one carrier block representing a carrier has data identifying the same boundary.

20. Apparatus storing a representation of a topological structure having topological features, comprising:

a) a data storage medium; and

b) a digital data base stored on said data storage medium, said digital data base including (i) a plurality of carrier blocks of data representing the topological features at a given level of detail, said data of each one of said carrier blocks of said plurality being a representation of a carrier which is a closed set including in its interior a given topological object, (ii) at least one other carrier block of data being in a hierarchical relationship with respect to said plurality of carrier blocks so as to represent the topological features at another level of detail, said at least one other carrier block representing a complex X'"'"' which is topologically equivalent to a complex X represented by said plurality of carrier blocks, and (iii) wherein said data of said at least one other carrier block of said complex X'"'"' comprises more generalized information than the information of said plurality of carrier blocks of said complex X.