US 5,694,534 AGrant

Apparatus Storing a Presentation of Topological Structures and Methods of Building and Searching the Representation

Issue Date:1997-12-02

•20 Claims

•16 Drawing Sheets

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.

Metadata

Assignee

Etak, Inc.

Inventors

Marvin S. White, Jr.
George E. Loughmiller, Jr.

Application Information

Application Number:US 7666462

Filing Date:1996-12-13

Priority Date:1985-07-25

Art Unit:242

Classifications

IPC:

G06T 900

Field of Search:

395364340133;140;141;121;128449;474.28;603;615988;995

Patent Drawings (16 sheets)

Description

Background of the Invention

1. Field of the Invention

The present invention relates generally to apparatus storing a representation of topological structures and methods of building and searching the representation. More particularly, the present invention relates to the storage of, and methods of building and searching, data bases representing topological structures, including geometric structures, for effectively processing the data and presenting the data, such as on a display.

2. Background Art

Representations of a wide variety of topological structures, including geometric structures, are used for many purposes, such as to convey information. These representations include maps of geographical areas, layouts and masks of integrated circuits, mechanical drawings, and other geometric representations. In this age of computer technology, these representations typically are provided in the form of digital data bases that are stored in memory and processed by a computer for a variety of purposes. One purpose may be to read out the information on, for example, a display. Another purpose might be to update the digital data base in view of changes that are made to the underlying geometric structure. For example, if a new street is added to a neighborhood, the corresponding digital data base portion of the map stored in memory should be updated to include that street.

Moreover, in a given computer system, the amount of memory that is available for the storage of data usually is limited. Accordingly, it is advantageous to store efficiently a representation of a given geometric structure so as to minimize the memory occupied by the digital data base. Furthermore, it may be important to access quickly and in sequence portions of the digital data base so as to be able to properly display part of the geometric structure. For example, in two co-pending patent applications, Ser. No. 06/618,041, now U.S. Pat. No. 4,796,191, filed Jun. 7, 1984 and Ser. No. 06/663,862, now U.S. Pat. No. 4,914,605, filed Oct. 22, 1984, and assigned to the assignee of the present invention, a computerized vehicle navigation system and moving map display are disclosed, respectively. The on-board computer of the vehicle calculates the position of the vehicle and accesses the digital map data base to show to the driver the vehicle position via a display of a map. As the vehicle moves, its position on the map changes and the area of displayed map changes.

In order to accomplish all of the above, the entire representation of a given topological or geometric structure should be divided into small pieces, so that the corresponding digital data base portions stored in memory can be effectively processed or displayed. In one prior technique, a digital data base is produced and stored by first providing an electronic grid overlay of equal-sized grid cells on the representation, such as the map. Each cell of the grid overlay is then optically scanned and the resulting data digitized and stored at a given location in memory as a block of data.

One problem with the above grid overlay approach is that the memory space is inefficiently utilized. The reason for this is that a given cell of the grid may overlay a detailed street network while another cell of the grid may overlay no street network or a much less detailed street network. Yet, the same memory space as used for the former is still allocated to the latter even though there is little or no map information underlying that particular cell.

Another problem is that a given street or other map feature may cut across the boundary or boundaries of two or more mutually adjacent cells. A consequence of this is that one or more of three disadvantageous compromises must be made to properly store such a feature. Either the feature must be split at the cell boundary or boundaries, which may not occur at natural features like a street intersection, thereby having to store the same feature in two or more blocks of data, or the feature must be referenced or indexed in the digital map data base more than once, i.e., once for each cell it crosses, thereby requiring more memory space for the index and greater access time to the feature since the index and separate blocks of data must be accessed once for each such cell. Alternatively, the index can allocate the feature to only one of the cells and not the others that are crossed, but this reduces the accuracy of the index.

Another approach to creating and storing the digital data base is known as the "quad tree" technique. In this approach, the map, for example, is overlayed with an electronic grid that divides the map initially into quarter sections or cells. Then, each initial quarter cell that overlays a detailed street network is itself further divided into quarter cells, and so on. An initial quarter cell that does not overlay much street detail and, therefore, has relatively little geographic information, is not further divided. In other words, the size of the grid cell is adapted or altered depending on the amount of data it overlays. After the digitizing and storing, the result is that less memory storage space is utilized for those quarter cells that overlay sections of the map having little detail and more storage space is available for the scanned areas having more detail.

While the quad tree technique has the advantage of a more efficient utilization of memory space than the technique described above using a grid overlay of equal-sized cells, it still suffers from the above-described problem relating to a given feature crossing two or more mutually adjacent cell boundaries. Analogous methods use hexagonal and triangular grid cells, but these essentially are not different from the quad tree grid overlay.

Moreover, and as will be described more fully below, the grid cells of any of the above techniques are not "closed topological cells", as this term is known in the art of cartography. In other words, the resulting digital data base does not have topological information about the underlying geometric structure. This lack of information has certain disadvantages including, for example, the inability to retrieve the network of streets for what is known as "minimum path finding".

Another approach to creating and storing the data base is known as DIME (an acronym for Dual Incidence Matrix Encoding). In this approach, an example of which is described and illustrated more fully below, the map, for example, is represented topologically using topological "open" "n-cells". Each DIME computer record corresponds to a single line segment in the map and information is recorded about the endpoints of the line segment and the areas to the left and right of that line segment. One disadvantage is that DIME data bases typically are organized by street names, which is inefficient because this requires considerable memory space.

Furthermore, while DIME has the advantage of storing topological information, its data base organization is inefficient for retrieval purposes. Each line segment retrieved by the computer from the DIME data base may require an I/O (input/output) operation, which is relatively time consuming. In other words, a DIME data base is not organized in a manner that enables it to be relatively quickly accessed so as to, for example, effectively display a moving map. Thus, in the example of a moving map display in a vehicle, one I/O operation per street segment would be far too slow, because the vehicle could be driven faster than the map data could be retrieved to display the corresponding street segment, thereby making the map useless for navigation.

Another problem indicated above with the prior techniques is that a separate digital index must be stored and accessed in memory to enable the computer to access a desired portion of the digital data base. For example, in using a DIME data base, in which the data of the line segments are stored as coordinates of the line segment endpoints, additional indices are required to be stored to access the portion of the data base that represents street segments within, for example, a given range such as a rectangular window. This has the disadvantage of utilizing additional storage space in the memory to store the index.

Summary of the Invention

In one aspect the present invention constitutes apparatus storing a representation of a topological structure having topological features, including a data storage medium, and a digital data base stored on the data storage medium, the digital data base including a plurality of carrier blocks of data representing the topological features at a given level of detail, the data of each one of the carrier blocks being a representation of a carrier which is the smallest topological closed set including in the interior thereof a given topological object.

In another aspect, the invention constitutes a method of building a digital data base, representing a given topological having topological features, using a programmed computer, the digital data base including a plurality of carrier blocks of data representing the topological features at a given level of detail, the data of each one of the carrier blocks being a representation of a carrier which is the smallest topological closed set including in the interior thereof a given topological object, comprising the steps of:

a) providing on a data storage medium a stored digital data base representing a topological structure having a partition P of topological open sets;

b) accessing the topological open sets of the partition P;

c) generating from the accessed topological open sets the plurality of carrier blocks; and

d) storing the plurality of carrier blocks on a data storage medium.

In yet another aspect, the invention constitutes a method of building a more generalized or less detailed topological complex X' from a plurality of carrier blocks of data representing a more detailed topological complex X, using a programmed computer, wherein the data of each of the carrier blocks represents a topological closed set of n-cells, and wherein said plurality of carrier blocks include data representing mutually-adjacent boundaries as n-cells and interiors thereof as n-cells, comprising the steps of:

a) providing said plurality of carrier blocks of data as a digital data base on a data storage medium;

b) accessing said plurality of carrier blocks on said digital data base:

c) generating from said accessed plurality of carrier blocks at least one other carrier block of data corresponding to said complex X', said other carrier block of data representing a topological closed set which is topologically equivalent to said data of said plurality of carrier blocks, and wherein said n-cells of said common boundary and said n-cells of said interior are absorbed in said other carrier block; and

d) storing said other carrier block on a data storage medium.

In order to create additional levels in the hierarchy, another computer program described below is executed and iterates the above-described program to create a a still less detailed complex X" from the complex X', and so on. Embodiments of these two program are given below and called, respectively, NEXT LEVEL and HIERARCHY.

In still another aspect, the invention relates to three different methods for searching the digital data base having a hierarchy of carrier blocks of data, the carrier blocks at each level in the hierarchy 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, and each of the complexes having n-cells, where n=0, 1, 2 . . . The three different search algorithms are called, respectively, TOP-DOWN, ACROSS and BOTTOM-UP. For example, in a structure where n=2, TOP-DOWN comprises 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 be the root;

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

d) selecting from the second list of 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 the most detailed level;

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, the one carrier block of said other list being at the next level of the hierarchy;

g) incrementing the current level; and

h) returning to step d).

Brief Description of the Drawings

FIG. 1 is a representation of a geometric structure, particularly a map, used to explain combinatorial topology.

FIG. 2A illustrates pictorially the technique of fusion that may be used on topological 1 -cells in accordance with the present invention.

FIG. 2B shows pictorially the technique of fusion that may be used on topological 2-cells in accordance with the present invention.

FIGS. 2C and 2D are used to illustrate the principles of "topological equivalence" and "topological difference" respectively.

FIG. 3 illustrates pictorially digital map structure carrier topology used to explain partitioning by carriers and a hierarchy of carriers in accordance with the principles of the present invention.

FIGS. 3A and 3B show carrier blocks and the data contained in carrier blocks, respectively.

FIGS. 3C-1 and 3C-2 illustrate pictorially a given arbitrary geometric structure and a carrier for the geometric structure, respectively.

FIGS. 4A-1 and 4A-2 are pictorial illustrations of an example of a DIME digital data base of a topological complex X used to explain the flow charts of FIGS. 4B and 4C.

FIGS. 4B and 4C are flow charts of embodiments of a computer program used for building carrier blocks.

FIGS. 5A and 5B are flow charts of embodiments of a computer program for creating a next level of carrier blocks.

FIG. 5C is an illustration of a topological sub-complex X.sub.i used to explain the flow charts of FIGS. 5A and 5B.

FIG. 6A is a flow chart of one embodiment of a computer program for creating a hierarchy of greater than two levels of carrier blocks.

FIG. 7A is a flow chart of one embodiment of a computer program used to perform a "top-down" search of carrier blocks.

FIG. 7B is an illustration similar to FIG. 3 and used to explain the flow chart of FIG. 7A.

FIG. 8A is a flow chart of one embodiment of a computer program used to perform an "across" search of carrier blocks.

FIG. 8B is a pictorial illustration of a moving map display used to explain the computer program of FIG. 8A.

FIG. 9A is a flow chart of one embodiment of a computer program for performing a "bottom-up" search of carrier blocks.

FIG. 10 shows pictorially carriers in order to explain another data encoding feature of the present invention.

Detailed Description of the Invention

The present invention applies generally to topological representations, including geometric representations, of any kind, including maps, mechanical drawings, and integrated circuit masks or layouts. The invention will be described in particular to maps and digital map data bases. Also, while the invention will be described and claimed in relation to "digital" data bases, it also applies to data bases that are "analog" and to analog computers which process analog data bases.

I. Overview of Known Mathematical Combinatorial Topology

In order to understand the present invention, and to provide nomenclature, an overview of certain mathematical theory, known as combinatorial topology, will be given. Reference will be made to 2-dimensional geometric structures, such as maps, but, the principles apply to 3-dimensional and higher-dimensional geometric structures as well. Reference also will be made to FIG. 1 which illustrates a map M of three states, New Mexico, Oklahoma and Texas, and to FIGS. 2A and 2B which illustrate the topological principles of fusion.

The fundamental objects for 2-dimensional geometric structures in combinatorial topology are 0-cells, 1-cells, and 2-cells. In general, an n-cell is a connected, n-dimensional geometric object. Thus, as shown in FIG. 1, a 0-cell is a point, a 1-cell is an open line segment of any shape not intersecting itself or any other n-cell, and a 2-cell is an "open" disc stretched and formed to any shape not intersecting itself or any other n-cell. The term "open" has a certain topological meaning. That is, a 2-cell is open if its boundary of 0-cells and 1-cells is not included and would be closed if its boundary were included. For purposes of describing the present invention, the 2-cell is considered to be an open cell, although in mathematical literature the usage may vary. Accordingly, for example, as shown in FIG. 1, the map M shows four 0-cells labeled 1-4, respectively, five 1-cells labeled a-f, respectively, and three 2-cells (open discs) referenced NM (New Mexico), OK (Oklahoma) and TX (Texas).

A given n-cell will be denoted by c.sup.n.sub.i, where the superscript n gives the cell dimension and the subscript i selects from a set of cells {c.sup.n.sub.i }.

Furthermore, a 2-dimensional complex X or "2-complex" is a collection of 0-, 1-, and 2-cells formed according to the following set of three recursive rules:

1) A 0-dimensional complex or "0-complex" is a collection of 0-cells.

2) A 1-dimensional complex or "1-complex" includes a 0-complex (also known as the 0-skeleton), together with a set of 1-cells satisfying the conditions that (a) each 1-cell is bounded in the 0-complex, and each 0-cell of the complex is on the boundary of some 1-cell of the 1-complex. Thus, for example, the 1-cell labeled d in FIG. 1 is bounded by the 0-complex of 0-cells labeled 2 and 4 and each such 0-cell is on the boundary of this 1-cell.

3) A 2-complex includes a 1-complex (also known as a 1-skeleton), together with a collection of 2-cells satisfying the conditions that (a) each 2-cell is bounded in the 1-complex and each 1-cell of the complex is on the boundary of some 2-cell of the 2-complex. Thus, for example, the 2-cell labeled OK (Oklahoma) is bounded in the 1-cells labeled b, d and f, and each such 1-cell is on the boundary of the 2-cell labeled OK.

Thus, the 2-complex is similar to a jigsaw puzzle whose pieces are the above-described fundamental topological objects, i.e., n-cells, where n is the dimension. Similar definitions can be made for complexes of any dimension, such as a 3-dimensional complex which would have 0-, 1-, 2-, and 3-cells. A practical example of a 2-complex is a DIME data base representing, for example, a street map of a city, as will be described below in relation to FIGS. 4A-1 and 4A-2.

A 2-dimensional complex may be embedded in a 3-dimensional space. For example, a map sheet is a 2-dimensional and a complex representing it is 2-dimensional, but each point may have x, y and z coordinates as for an elevation map. The dimensionality of the map does not limit the number of coordinates.

A "sub-complex" is a subset of the 0-, 1-, and 2-cells that satisfies the conditions for a complex. Thus, the 1-skeleton of a 2-complex is an example of a sub-complex. Also, the closure of a set of 2-cells, which is a set of 2-cells, the 1-cells bounding any of the 2-cells, and the 0-cells bounding any of those 1-cells, is a sub-complex. For example, with reference to FIG. 1, a closed set would include the 2-cell TX, the 1-cells c, e, f and the 0-cells 1, 3, 4.

A "carrier" also is a mathematical term used in topology, and this will be defined and explained in more detail below in relation to FIGS. 3C-1 and 3C-2.

A linear combination of n-cells of the same dimension is called a "chain" and is denoted by:

FIGS. 2A and 2B illustrate the topological principle of fusion. As illustrated in FIG. 2A, a pair of 1-cells, c.sup.1.sub.i and c.sup.1.sub.j, may be "fused" to form a single 1-cell c'.sup.1.sub.i if the pair of cells share a common 0-cell, i.e., if they are adjacent. FIG. 2A shows the common 0-cell c.sup.0.sub.2. Likewise, as shown in FIG. 2B, a pair of adjacent 2-cells c.sup.2.sub.i and c.sup.2.sub.j may be fused to form a chain or single 2-cell c'.sup.2.sub.i. Fusion, which will also be described in more detail in relation to FIG. 3, preserves the topological characteristics of the complex, so that the complex after fusion is "topologically equivalent" to the complex prior to fusion.

Reference will now be made to FIGS. 2C nd 2D to explain more fully complexes which are "topologically equivalent" or "topologically different". A topological transformation is a continuous deformation, intuitively a rubber sheet transformation, where neither rips nor folds are permitted. A precise definition of topological equivalence in terms of mappings and continuity can be found in any text on topology, but the intuitive idea will suffice here. The three items in FIG. 2C are topologically equivalent but the two items a, b in FIG. 2D are not, because a cut must be made in the interior of item a to deform it into item b. Conversely, the points on the boundary of the hold in item b must coalesce into a single item point (a singularity) to transform item b into item a. This would also violate the requirements for topological equivalence.

Furthermore, chains of adjacent 1-cells can be fused into a single 1-cell, and chains of adjacent 2-cells can be fused to create a single larger 2-cell, both by iterating pairwise fusion of the adjacent n-cells as given above. Thus, for example, while not shown, the chain c'.sup.1.sub.i shown in FIG. 2A and the chain c'.sup.2.sub.i shown in FIG. 2B can be fused, respectively, with similar adjacent chains to create a still single larger 1-cell or 2-cell, respectively.

In summary, the fusion operation converts a given complex X into another topologically equivalent complex X':

As will be described more fully below in relation to FIG. 3, while the original unfused n-cells and the fused chain of n-cells are topologically equivalent, they are not the same thing, although they both represent the same region or area of the geometric structure, i.e., the map M in the example. The unfused n-cells, such as the unfused 2-cells shown in FIG. 2B, represent the geometric region in finer detail than the fused n-cell, i.e., the 2-cell c'.sup.2.sub.i shown in FIG. 2B, which represents the geometric region as a single atomic entity.

II. Partitioning By Carriers In Accordance With the Present Invention; Index; Hierarchy of Carrier Blocks; Summary

A. Carriers

Reference now will be made to FIG. 3 to explain the principles of the present invention. These include, among other principles, partitioning a representation of a topological structure, e.g. a geometric structure such as the map M, by "carriers" as described below, as opposed, for example, to partitioning the map M by using a grid overlay or by partitioning the map M using street names and topological open n-cells as DIME does. That is, the present invention organizes data into a data base by "carriers".

FIG. 3 shows a digital map structure carrier topology of the present invention at, for example, three hierarchical levels 1-3. While only three such levels 1-3 are shown and will be described, the principles of the present invention apply to any number of levels. As will be further described as one example, at level 3 there is a complex X which may have some of its n-cells fused to create a complex X' of level 2 which, in turn, may have some of its n-cells fused to create a complex X" of level 1.

Accordingly, consider a partition P (at a given level) of the set of 2-cells c.sup.2.sub.j :

Thus, for example, at level 3 shown in FIG. 3, the partition P includes elements A.sub.1 -A.sub.4, each having a set of mutually adjacent 2-cells c.sup.2.sub.j. At level 2, the partition P includes two elements A'.sub.1 and A'.sub.2.

For each of the elements A.sub.i of the partition P at a given level 1-3, in accordance with the present invention a sub-complex X.sub.i is constructed having the 2-cells c.sup.2.sub.j in A.sub.i, all 1-cells c.sup.1.sub.j incident to those 2-cells c.sup.2.sub.j, and all 0-cells c.sup.0.sub.j incident to the 1-cells c.sup.1.sub.j. The sub-complex X.sub.i thus represents a carrier which is a topological closed set and the collection {X.sub.i : A.sub.i in P} at a given respective level 1-3 covers the entire complex X.

Furthermore, the interior of sub-complex X.sub.i is disjoint from the interior of sub-complex X.sub.j for j not equal to i, the advantages of which are related, for example, to map editing described below. However, although such interiors are disjoint, mutually adjacent sub-complexes X.sub.i and X.sub.j have a chain of 1-cells K.sup.1.sub.k on their common boundary. That is, the same chain of 1-cells K.sup.1.sub.k occurs in both sub-complexes X.sub.i and X.sub.j. For example, the sub-complex X.sub.1 corresponding to element A.sub.1 and the sub-complex X.sub.4 corresponding to element A.sub.4 of level 1 have a common chain K.sup.1.sub.k at their common border, as shown in FIG. 3.

Each such sub-complex X.sub.i, in accordance with the present invention, is said to "carry" a subset of the 0-, 1-, and 2-cells in its interior and accordingly is called herein the "carrier" for such a subset. The digital representation of each carrier is called herein a "carrier block", because it is stored as a single block of data in memory. For example, FIG. 3A shows a data storage memory SM having groups of carrier blocks CB corresponding to a given level 1-3. Each carrier block CB has a block of digital data representing the corresponding sub-complex X.sub.i at the given level.

Thus, as shown in FIG. 3B, the stored data of a given carrier block CB are 0-cells (as XY coordinate data), and 1-cells and 2-cells (shape information such as DIME encodes 1-cells and 2-cells). In addition, and as will be further described regarding the INDEX feature of the present invention, the given carrier block CB may store a pointer to a carrier block CB of another hierarchical level, so that, for example, the carrier block CB for sub-complex X.sub.1 of level 3 of complex X will have a pointer to the sub-complex X'.sub.1 of level 2 of complex X'. Also as shown in FIG. 3B, the given carrier block CB may include street names and other information that street names and such other information in addition to streets of the map M may be, for example, displayed.

As previously described, and as will be further described below in Section IIC (HIERARCHY) a chain of 2-cells c.sup.2.sub.j may be constructed, and to avoid proliferation of notation, the chain is denoted by A.sub.i as well:

Because the 2-cells c.sup.2.sub.j of an element A.sub.i are mutually adjacent, this chain can be fused together to form a single 2-cell c'.sup.2.sub.i. Thus, for example, and as will be further described below, the chain of 2-cells c.sup.2.sub.j of each respective element A.sub.1 -A.sub.4, is fused into a respective single 2-cell of the complex X' of level 2, as shown.

Thus, regarding the partition P at a given level as a set of elements A.sub.i or chains of 2-cells, and as will be further described below, n-cells of the complex X can be fused to create the topologically equivalent complex X', as follows:

For each element A.sub.i in the partition P:

1) A.sub.i .fwdarw.c'.sup.2.sub.i ; that is the chain of 2-cells is fused into one 2-cell, such as {c.sup.2.sub.3 } at level 3 being fused into c'.sup.2.sub.3 at level 2 as pictorially shown in FIG. 3.

2) The boundary of sub-complex X.sub.i .fwdarw. a set of chains of 1-cells {K.sup.1.sub.i }, where each of the chains is a chain of adjacent 1-cells along the common boundary of a pair of adjacent sub-complexes X.sub.i or along the boundary of the entire complex X.

3) K.sup.1.sub.k .fwdarw.c'.sup.1.sub.k, where each of the c'.sup.1.sub.k is a single 1-cell corresponding to a chain of 1-cells K.sup.1.sub.k. For example FIG. 3 shows a chain of 1-cells K.sup.1.sub.k labeled c.sup.1.sub.1, c.sup.1.sub.2, c.sup.1.sub.3 on the boundary of element A.sub.1, which is fused into the single 1-cell c'.sup.1.sub.i of element A'.sub.1 of the complex X'.

4) c.sup.0.sub.m .fwdarw.c'.sup.0.sub.m, where c.sup.0.sub.m is a 0-cell on the boundary of at least one of the chains K.sup.1.sub.k, as shown in FIG. 3.

The complex X' comprises the resulting cells c'.sup.2.sub.i, c'.sup.1.sub.k, c'.sup.0.sub.m and necessarily has fewer n-cells than the complex X (provided the partition P is not the maximal partition P in which element A.sub.i contains exactly one 2-cell for every i). By means of this mapping, a simpler cellular decomposition of the 2-dimensional space may be constructed and stored on storage memory SM; viewed in reverse, the original complex X is a more detailed complex of the complex X'. By choosing the partition P to be significant, e.g., along major roadways for a map, complex X' represents the geometric space at that level of significance.

By replacing 2-cells with 3-cells and extending the fusion of 1- chains to 2-chains, the principle of carriers of the present invention applies to 3-dimensional structures.

In general, and with reference to FIGS. 3C-1 and 3C-2, a carrier of a given set or topological object may be defined as the topological closed set, e.g., the smallest topological closed set, containing the given set or topological object in its interior. This means that none of the given set may have any part on the boundary of the carrier; rather, all of the given set must be contained within the carrier. More specifically, FIG. 3C-1 shows an arbitrary geometric structure as such a given set, which structure has 0-cells, 1-cells and 2-cells. FIG. 3C-2 shows the carrier for that given set, which carrier is the smallest topological closed set containing the given set and corresponds to a given sub-complex X.sub.i stored as a carrier block CB.

Thus, the carrier contains all n-cells that could be affected by any continuous process on the given set. For example, and as will be further described below, one use of carriers is to gather or organize together all data that represents geographic areas to which a continuously moving vehicle could travel from a given known position, as described in the above-mentioned co-pending applications. As the vehicle moves, carrier blocks stored in memory are accessed to display the given sets as a moving map.

As was indicated in Section I above, carriers are also mathematical tools used by mathematicians for different purposes, e.g., to analyze continuous functions.

B. Index

As will be further described, the correspondence of n-cells and chains in the mapping or fusing relates the more significant features to collections of less significant features, which constitutes the search index of the present invention used for searching the digital data base of carrier blocks CB. In other words, and as was indicated above in relation to FIG. 3B, for example, the element A".sub.1 of the partition P of level 1, which has freeways as the most significant feature, is an index or pointer to the element A'.sub.1 of the partition P of level 2, which has arterial roadways as a lesser significant feature, which itself is an index or pointer to the elements A.sub.1 -A.sub.4 of the partition P of level 3, which has local streets as the least significant feature.

It should be noted that the quad tree approach to partitioning a map M also has an hierarchical index, but the several levels are not useful topological structures.

C. Hierarchy of Carrier Blocks

As illustrated pictorially in FIG. 3 and indicated in IIA above, the carrier building process can be iterated to construct still simpler cellular decompositions:

The result is an hierarchy of 2-complexes. An arbitrary 2-cell c.sup.2.sub.i in the original complex (the most detailed such as complex X in FIG. 3) is contained in a nested hierarchy of 2-cells, one from each complex in the hierarchy of complexes. Likewise, each sub-complex X.sub.i is contained in a nested hierarchy of sub-complexes and each of these represents a topological closed set. These facts are the basis for the digital data base search algorithms disclosed below. This hierarchy applies without alteration to higher dimensional spaces.

D. Summary

In summary, FIG. 3 shows a roadmap at three scales or levels, each having corresponding groups of carrier blocks CB, (level 3) large--showing all the local streets, (level 2) intermediate--showing only major streets, e.g., arterials, and (level 1) small, showing only limited access highways, e.g., freeways. The exact correspondence between the levels is also indicated in the figure. The chain K.sup.1.sub.i of 1-cells (c.sup.1.sub.1, c.sup.1.sub.2, c.sub.1.sub.c) at level 3 corresponds to the single 1-cell c'.sup.1.sub.A at level 2. Thus, level 2 contains less information than level 3, because a chain of 1-cells is fused to a single 1-cell at level 2, and 1-cells interior to the sub-complexes X.sub.i are effectively absorbed into the 2-cell c'.sup.2.sub.i of level 2. (A further reduction in information can be made by filtering the detailed shape of the chain of 1-cells to produce a more generalized representation. This reduces the amount of data that are stored in the carrier block to represent the chain.)

Also, just as chains of 1-cells are fused into single 1-cells and their geometric representation may be further generalized in the mapping through filtering, chains of 2-cells are fused into single 2-cells and their geometric description (for example elevation contours) may be filtered to a still more generalized representation.

Single 0-cells map into single 0-cells or are absorbed within chains of 1-cells that map to single 1-cells going to the next level of generalization. The 0-cells bounding the chains of 1-cells map to 0-cells and the 0-cells interior to the chain are dropped in the mapping. Similarly, 1-chains on the boundary of the sub-complexes X.sub.i map into 1-cells in X'.sub.i, but 1-cells interior of the carriers are absorbed in the fusion of 2-cells. In this way, the number of n-cells diminishes in the mapping.

Thus, the mapping from one level to the next reduces information and consequently the next level covers a larger geographical region (in the case of maps) with substantially the same amount of data in the respective carrier blocks CB. In FIG. 3, all of the illustrated elements A.sub.1 -A.sub.4 of level 3 map into a single element A'.sub.1 of the level 2 representation. Likewise, both of the elements A'.sub.1 and A'.sub.2 of level 2 map into the single element A.sub.1 of level 1.

III. Building Carrier Blocks and Their Hierarchy

A. Introduction

In Section II, carriers, carrier blocks CB and their hierarchy were described. Ultimately, and as will be further described below, a data storage medium SM (see FIG. 3A) will store the carrier blocks CB, which may then be processed by a computer so as, for example, to display the geometric structure, e.g., the map M, at any level (such as levels 1-3 of FIG. 3) or update the representation, such as when new roadways are added, at any level. In this Section III, one embodiment of the manner in which the digital data base of carrier blocks CB, and their hierarchy, may be built will be described.

B. Building Carrier Blocks: In General: By Accretion

1. General

In general, the carrier blocks CB corresponding to the most detailed level, e.g., level 3 shown in FIG. 3, is constructed from a complex X of topological open sets of 2-cells. For example, and as previously described, the commercially available DIME map data base of a given geometrical area, which may be purchased from the U.S. Census Bureau, can be used as the complex X of input data for the method described below. This DIME map data base is pictorially illustrated in FIGS. 4A-1 and 4A-2 as having the set of topological open 2-cells c.sup.2.sub.j stored in a computer data bank DB. FIG. 4A-2 indicates the DIME data base as being stored or organized by street names (see leftmost column). Also stored in the data bank DB as part of the DIME map data base are the 0-cells and 1-cells associated with, i.e., incident to, each one of the topological open cells c.sup.2.sub.j. The DIME data base can be stored on, for example, a relatively large computer such as the VAX 11/750 manufactured by Digital Equipment Corporation, Maynard, Mass.

Accordingly, and with reference to the software flow chart of FIG. 4B, the method broadly includes using a programmed computer in the following manner:

1) Providing on a data storage medium of a computer a stored digital data base representing a topological structure having a partition P of topological open sets of n-cells (such as the above-mentioned DIME data base) (block 4B-1).

2) Accessing the topological open sets of the partition P on the data storage medium (block 4B-2).

3) Generating from the accessed topological open sets the plurality of carrier blocks CB at a given hierarchical level (block 4B-3).

4) Storing the generated carrier blocks CB as a digital data base on a storage medium (block 4B-4).

2. By Accretion

In this specific procedure, the partition P at the most detailed level, e.g., level 3 shown in FIG. 3, is constructed element-by-element A.sub.i and at the same time the sub-complexes X.sub.i are constructed. Each of the elements A.sub.i of the partition P at such level is built by accretion, until given thresholds are reached, according to the following software algorithm which will be described in relation to FIG. 4A-1 and the flow chart of FIG. 4C:

In referring to FIG. 4A-1 again, it is assumed that the complex X of the given partition P has been generated and stored. In the current example, the complex X is the DIME data base described in IIIB1 above. Accordingly, the carrier blocks CB at a given level 1-3 are built and stored, as follows:

1) Initialize or set a counter k=0 (block 4C-1) (the counter k represents the subscript i in the element A.sub.i of partition P).

2) Select an arbitrary 2-cell in the complex X of data bank DB (block 4C-2) not already included in some prior element A.sub.i in P; call it c.sup.2.sub.j (see FIG. 4A-1). This selection can be accomplished by setting a pointer to the representation (not shown) in the data bank DB of cell c.sup.2.sub.j.

3) Increment counter k and initialize a register A.sub.k and a register X.sub.k (Block 4C-3).

4) Construct the sub-complex X.sub.k by adjoining all 1- and 0-cells incident to c.sup.2.sub.j, that is, make the sub-complex X.sub.k a closed set (block 4C-4) and store in register X.sub.k.

5) Test whether there is another 2-cell c.sup.2.sub.j, (see FIG. 4A-1) in the complex X of data bank DB not already included in some prior element A.sub.i, and adjacent to a 2-cell in the sub-complex X.sub.k and satisfying any other desired constraint, (such as on the same side of a distinguished 1-cell which may be, for example, a major map feature) as other 2-cells in register X.sub.k (block 4C-5). If there is no other, go to step 9; if there is go to step 6.

6) Test whether adding the 2-cell c.sup.2.sub.j, in step 5 and its incident 1-cells and 0-cells to register X.sub.k would cause the sub-complex X.sub.k to exceed a given threshold of complexity (for example, if the corresponding carrier block CB would exceed a given size in bytes of computer memory) (Block 4C-6). If it would so exceed, go to step 9; if not, proceed to step 7.

7) Add c.sup.2.sub.j, to A.sub.k and adjoin all incident 1- and 0-cells to X.sub.k so as to keep the sub-complex X.sub.k closed (Block 4C-7).

8) Go to step 5 above (block 4C-8). Note that this would result in selecting yet another 2-cell such as 2-cell c.sup.2.sub.j" (shown in FIG. 4A-1 as the cell for step 5 - second pass), possibly resulting in yet another 2-cell and incident 0- and 1-cells being added to the sub-complex X.sub.k to keep it closed. (The loop is continued until the storage threshold of step 6 is exceeded.)

9) A.sub.k and X.sub.k are complete; thus add the contents of A.sub.k to P and store the contents of X.sub.k (Block 4C-9).

10) If there remain any 2-cells not in some A.sub.i, go to step 2; if no 2-cells then exit (Block 4C-10).

The partition P is now complete and each sub-complex X.sub.i corresponding to element A.sub.i in P has been constructed and stored as carrier blocks CB corresponding to the given level.

By replacing 2-cells with 3-cells and incorporating 2-cells into the steps for 1-cells, the above accretion method applies to 3-dimensional structures. Similarly, it may be extended to any number of dimensions.

Furthermore, for some applications other information can be attached to the 0-, 1- and 2-cells of the complex X and this information is included in the carrier blocks CB and used to compute the storage size of each carrier block CB. Examples of such information, as described in relation to FIG. 3B, may be street names, addresses, etc. appropriate for the display of a map.

The computer programs in source code listings entitled BUILDLEAF, AMOEBA, and SMTOCARR attached to this specification and described more fully below, implement the above general and more specific algorithms. Particularly, SMTOCARR corresponds to steps 4 and 7, AMOEBA corresponds to steps 5 and 6, and BUILDLEAF corresponds to steps 1-3, and 8-10 of the accretion method.

C. Building the Carrier Block Hierarchy: General: NEXT LEVEL: HIERARCHY: SUMMARY

1. General

As indicated, the software program described in Section IIIB results in a plurality of carrier blocks CB at a given level, e.g., the level 3 shown in FIG. 3. In this Section IIIC, two software algorithms called herein NEXT LEVEL and HIERARCHY, respectively, are described. NEXT LEVEL builds the level i-1 carrier blocks CB from level i carrier blocks CB, for example the level 2 from the level 3 as pictorially shown in FIG. 3, while HIERARCHY essentially iterates NEXT LEVEL to build additional more general levels of carrier blocks CB such as shown for example in level 1 of FIG. 3.

2. NEXT LEVEL

a. General

Reference will be made to the flow chart of FIG. 5A to describe generally the algorithm for producing a more generalized "next level" data base from the more detailed, preceding level in the hierarchy. The input data to this method are the plurality of carrier blocks CB representing a given level i or topological complex such as complex X from which the more generalized topological complex X' is produced. Thus, the method includes, using a programmed computer, as follows:

1) Providing the plurality of carrier blocks of data as a digital data base on a data storage medium (block 5A-1).

2) Accessing the plurality of carrier blocks on the digital data base (block 5A-2).

3) Generating from the accessed plurality of carrier blocks at least one other carrier block of data corresponding to the complex X', the other carrier block representing a topological closed set which is topologically equivalent to the data of the plurality of carrier blocks, and wherein the n-cells of the common boundary and the n-cells of the interiors are absorbed in the other carrier block (block 5A-3).

4) Storing the other carrier block on a data storage medium (block 5A-4).

With reference to FIG. 3 and FIG. 3A the above method would apply, for example, to the more detailed carrier block CB corresponding to the element A.sub.1 of the complex X which becomes a part of the more generalized carrier block CB corresponding to element A'.sub.1 of the complex X'. The 1-cells on the common border of mutually-adjacent 2-cells, and those 2-cells, of element A.sub.1 of complex X become absorbed in the element A'.sub.1 of complex X'.

b. Specific

Reference will be made to FIG. 5B and FIG. 5C to describe one embodiment of a more specific algorithm carried out by NEXT LEVEL.

The set of sub-complexes X.sub.i corresponding to the elements A.sub.i of the partition P at level 3 and produced and stored by the method described above in Section II is the input data to the specific algorithm NEXT LEVEL, as already indicated, to produce the next level of carrier blocks CB. NEXT LEVEL produces a complex X' that is topologically equivalent to X but has fewer n-cells. The 0-cells in X' correspond to some of the 0-cells in X, 1-cells to chains of 1-cells, and 2-cells to chains of 2-cells. In making reference to FIGS. 5B and 5C to explain NEXT LEVEL, the latter illustrates pictorially a subcomplex X.sub.3 corresponding to element A.sub.3 of FIG. 3. Thus, the method is as follows:

1) For each sub-complex X.sub.i, fuse (see further description below) all the contained 2-cells to form a single 2-cell c'.sup.2.sub.i (block 5B-1). This is possible because the sub-complex X.sub.i was constructed so that the contained 2-cells c.sup.2.sub.i were mutually adjacent.

2) Identify the 1-dimensional sub-complex comprising the 1-cells on the boundaries of 2-cell c.sup.2.sub.i and the 0-cells bounding those 1-cells (Block 5B-2) (see FIG. 5C-2). This is a sub-complex of the 1-skeleton of complex X. Note that an essential 0-cell is that 0-cell incident to t 1-cells, where t is not equal to 2.

3) Construct connected chains of 1-cells K.sup.1.sub.j so that each chain is bounded by essential 0-cells (block 5B-3). These are the 1-chains common to adjacent sub-complexes or on the boundary of the entire complex X.

4) Fuse each chain K.sup.1.sub.j to form a 1-cell c'.sup.1.sub.j (block 5B-4) (see FIG. 5C-3). This is possible because each chain is connected. If it is desired to also reduce the "metrical" complexity (not just the topological complexity), the 1-cell c'.sup.1.sub.j may be generalized using a straightening algorithm such as the known Douglas-Peuker algorithm.

5) For each essential 0-cell c.sup.0.sub.k, create a chain K.sup.0.sub.k comprising the single 0-cells and map this chain into 0-cell c'.sup.0.sub.m, which is just a copy of K.sup.0.sub.k (block 5B-5).

The result of executing NEXT LEVEL is that the complex X' comprising the c'.sup.0.sub.m, c'.sup.1.sub.j, and c'.sup.2.sub.i cells, together with the mapping associating the cells c'.sup.n with chains K.sup.n, is the next level in the hierarchy. This method extends also to higher dimensions.

3. HIERARCHY

The following algorithm, called HIERARCHY, merely iterates NEXT LEVEL until the reduced complex X' does not exceed a given complexity threshold. An example of such a threshold is a maximum number of bytes of computer memory required to store a carrier block CB representing the entire complex X'. With reference to FIG. 6A, the steps of the algorithm are as follows:

1. Initialize the current complex (now called Y) to be the given complex X (Block 6A-1).

2. Create and store the complex Y' using the NEXT LEVEL algorithm above (Block 6A-2).

3. If complex Y' exceeds the given complexity threshold, set Y to be Y' and go to step 2.

The result of executing HIERARCHY is that the most general level of carrier blocks CB in the HIERARCHY is built and stored, which in the example of FIG. 3 is level 1. This most general level also is termed the "root", which is used in the search algorithms described below. This method also applies to any number of dimensions.

Moreover, each level in the hierarchy is itself a useful geometric structure, as well as an index to the next level.

The step of fusing a chain of n-cells is accomplished in memory by, for example, simply creating a new cell and copying information from the chain to the new cell. For example, to fuse a chain of 1-cells, one allocates memory for a new 1-cell, records the bounding 0-cells of the new 1-cell to be the two bounding 0-cells for the chain, records the cobounding 2-cells to be the 2-cells on the left and right of the chain of 1-cells, and records the shape of the new 1-cell to be the successive shapes of the chain of 1-cells. In addition, it is often useful to store pointers from the new 1-cell to the 1-cells in the chain, as a means to retrieve detailed data or other associated data such as street names.

The computer programs in source code listings entitled BUILDANC, ANCESTORS, and PARAMOEB implement the above algorithms, as further described below.

4. Summary

In summary, and referring again to FIG. 3 as an example, the above procedures produced the sub-complexes X.sub.i of level 3 and the 0-, 1-, and 2-cells of level 2, but not the partition of level 2. The same procedure is used on the level 2 complex X' to produce the 0-, 1-, and 2-cells of level 1. In FIG. 3, the process ends here. In general, the process is iterated producing a new more generalized level until a single sub-complex that is equal to the whole complex is created. This will occur in the example programs when the data have been reduced enough.

IV. The Search Algorithms

A. Introduction

As previously indicated, a primary purpose in building the carrier blocks CB and their hierarchy is to provide easy and quick access to the relevant geometric information, for example, for display purposes. The search algorithms described below accomplish these purposes.

There are three different search algorithms used with the carrier blocks CB, called, respectively, TOP-DOWN, ACROSS and BOTTOM-UP. All three algorithms find every piece of map at the appropriate scale or level for a given rectangular area for display on a display screen, as disclosed in the above-mentioned co-pending applications of the assignee of the present invention. With no essential changes, these algorithms can be made to search for areas of any shape, not just rectangular.

The TOP-DOWN search starts at the most generalized level, i.e., level 1 in FIG. 3, and proceeds down the index (described more fully below) to succeeding lower levels. An ACROSS search starts with a given coverage at a particular level of generalization, e.g., level 3 in FIG. 3, and retrieves sub-complexes X.sub.i of the digital map data base at the same level. A BOTTOM-UP search is the simplest and proceeds from a detailed level, such as level 3 in FIG. 3, to a more generalized level.

B. TOP-DOWN Search

With reference to FIG. 7A and FIG. 7B, to determine which 0-cells, 1-cells, and 2-cells at each level of the hierarchy are within a given rectangle (also called a range) surrounding a point (see FIG. 7B) on a display screen (not shown), the search will begin at the root (by analogy of a tree) and proceed along (by analogy) the branches to the leaves. (The point p described and shown herein corresponds to a symbol DRP, i.e., "dead reckoned position", on the display screen showing the position of the vehicle relative to the position of the displayed map.) The result of the search will be a list of n-cells falling within or intersecting the given range. The algorithm includes the following steps:

1) Initialize two lists (Block 7A-1), a first list of selected cells, which will contain the results, and a second list of current carrier blocks, which is used within the algorithm.

2) Set the second list of current carrier blocks to be the root and set the current hierarchical level to that of the root (level 1 in FIG. 7B) (Block 7A-2).

3) Select from the second list of current carrier blocks the n-cells that fall within a specified range of the point p (see FIG. 7B) (Block 7A-3). Note that this step may employ well-known point-in-polygon and geometric intersection routines. Note further that any geometric range, not just rectangular, could be used by employing different but also well-known geometric routines, and that any dimension may be used.

4) If the current hierarchical level is the most detailed level (level 3 in FIG. 7B), then exit (Block 7A-4). (The output data of the algorithm is the first list of selected cells.)

5) Replace 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, the one carrier block being the carrier block explicitly associated with this 2-cell (Block 7A-5). (These carrier blocks will all be at the next level (level 2 in FIG. 7B) of the hierarchy.)

6) Decrement the current level (Block 7A-6).

7) Go to step 3 (Block 7A-7). (Note, in the example of FIG. 7B the program now goes from level 2 to level 3.)

C. ACROSS Search

Reference will be made to the flow chart of FIG. 8A and the pictorial views of FIG. 8B. The latter show the range or rectangular area surrounding the position p of, for example, a vehicle, which, as previously described may be a dead reckoned position DRP. Also shown are a plurality of carriers of a given hierarchical level and having portions within the range. In other words, if it is assumed the rectangular area represents a display screen in a vehicle, then the driver would see on the display the geographical areas corresponding to the portions of the carriers within the range, i.e., carrier blocks CB will have been accessed and retrieved by the on-board computer so as to display this information. Also, as shown in FIG. 8B-2, the change in position of the rectangular area represents the movement of the vehicle to a new position p, thereby resulting in a different map display.

Accordingly, this search is used to determine which n-cells of carrier blocks CB at a given hierarchical level are within a given range of the point p. In describing the method below, assume that prior to step 1 below, the condition illustrated in FIG. 8B-1 occurs, which shows certain carriers and, hence, corresponding carrier blocks CB, one of which is a given carrier block CB. Then, and with reference also to the flow chart of FIG. 8A and FIG. 8B-2, the method includes:

1) Initialize two lists (block 8A-1), a first list of selected cells, which will contain the results, and a second list of current carrier blocks CB, which is used within the algorithm.

2) Set the second list of current carrier blocks CB to be the given carrier block CB.

3) Select from the second list of current carrier blocks CB the n-cells that fall within a specified range of the point p (block 8A-3). Note that this step may employ well-known point-in-polygon and geometric intersection routines. Note further that any geometric range, not just rectangular, could be used by employing different but also well-known geometric routines, and that any dimension may be used.

4) If none of the n-cells selected in step 3 is on the boundary of a carrier, then exit (block 8A-4). This exit or output is represented in FIG. 8B-4.

5) For each n-cell in the first list of selected cells, if the selected n-cell of step 3 is on the boundary of a carrier and the adjacent carrier is not in the second list of current carrier blocks, add that adjacent carrier to the second list (block 8A-5). This is shown pictorially in FIG. 8B-2 which shows new or adjacent carriers being added.

6) Go to step 3 (block 8A-6). This is shown pictorially in FIG. 8B-3 as pass 2 in which yet another carrier may be found by iterating.

D. BOTTOM-UP Search

This search is used to determine which n-cells at each hierarchical level from a given level and carrier block CB to the root (e.g., level 1 in FIG. 3), fall within a given range of the point p. Accordingly, and with reference to the flow chart of FIG. 9A, the method includes:

1) Initialize two lists (block 9A-1), a first list of selected cells, which will contain the results, and a second list of current carrier blocks CB, which is used within the algorithm.

2) Set the second list of current carrier blocks to be the given carrier block CB (block 9A-2).

3) Select from the second list of current carrier blocks the n-cells that fall within a specified range of the point p (block 9A-3). Note that this step may employ well-known point-in-polygon and geometric intersection routines. Note further that any geometric range, not just rectangular, could be used by employing different but also well-known geometric routines, and that any dimension may be used.

4) If the current level is the root, then exit (block 9A-4). The output or exit of the method is the first list of selected n-cells.

5) Replace the current carrier blocks CB in the second list with the single carrier block CB at the next level.

V. One Example of the Practical Application of the Carrier Blocks and Search Algorithms

As previously indicated, the two co-pending applications of the assignee of the present invention disclose a computerized vehicle navigation system and map display that enable a driver to navigate over a given geographical area and display a moving map on the display screen at different hierarchical or "zoom" levels. The technique of the present invention can be applied to create a digital map data base using carrier topology, as described herein, and search the digital map data base to display the moving map. While the present application is believed to be complete in itself, the above-identified two co-pending applications are hereby incorporated by reference in their entirety.

More specifically, in accordance with the present invention, the digital data base of carrier blocks CB and their hierarchy can be built and stored using the relatively large computer such as the above-mentioned VAX. Then, this digital data base of carrier blocks CB can be copied using conventional techniques onto a portable data storage medium such as a compact cassette, compact disc or tape. The portable data storage medium can then be inserted in the vehicle's on-board computer, which also is programmed with the above-mentioned three search algorithms of the present invention. The search algorithms also can be stored on the portable data storage medium and down-loaded into the on-board computer memory when needed. Thereafter, the digital map data base can be searched and accessed for the display purposes, as will now be further described.

As an example, the TOP-DOWN algorithm can be used to search the digital data base when the driver has inserted, for example, a new cassette storing a new digital map data base than previously used and the vehicle is then first turned on. At this time, the on-board computer stores the current location of the vehicle, which, as described in the co-pending patent applications, is called in those applications a dead reckoned position DRP and has been referenced here as position p. This position p is then used as described in the TOP-DOWN search to search for and access one carrier block CB corresponding to the respective hierarchical levels, e.g., levels 1-3 shown in FIG. 3. As an example, at each such level 1-3, the corresponding block CB is down loaded into the on-board computer and then is available for display, as desired by the driver. That is, as described in the co-pending patent applications, the vehicle driver (or passenger) can select a given "zoom" or "scale" level to display the digital map data base at the selected level. Accordingly, by such a selection, the map portion stored in the carrier block CB corresponding to the selected level 1-3 in the present example will be displayed on the display.

Thereafter, when the vehicle is moving, the ACROSS search is used to access carrier blocks CB at the selected level 1-3 and collect the 0-, 1- and 2-cells which are in the above-mentioned range of the position p. These collected n-cells are then displayed as a moving map display as the vehicle moves over streets and across neighborhoods.

The BOTTOM-UP search is used when the vehicle is first started with the same cassette inserted in the on-board computer, as opposed to a new cassette being inserted as described above for the TOP-DOWN search. At this time, the computer also stores information about the position p of the vehicle. In a similar manner as described for the TOP-DOWN search, carrier blocks CB corresponding to the hierarchical levels 1-3 within the above-described range are searched, accessed and down loaded into the computer, thereby being available for display. The BOTTOM-UP search is thus used to retrieve more generalized map displays with respect to the current known position, starting at level 3 in the present example.

VI. Summary of Advantages of the Present Invention

All topological information of the geometric structure is stored and readily available. This means geometric neighborhoods of any type, such as adjoining neighborhoods Of streets for a map, can be easily retrieved and the consistency of the representation can be enforced. In the case of maps, for example, carrier blocks CB corresponding to the street network can be retrieved, e.g., from the above-mentioned VAX computer, and analyzed as a linear graph (for example for minimum path finding), errors in the map source data can be discovered and eliminated, and completeness of coverage can be verified. Moreover, as stored on the cassettes inserted in the on-board computer of the above-mentioned vehicle navigation system and map display, entire carrier blocks CB of data can be conveniently accessed as the vehicle moves to display a moving map.

Each sub-complex X.sub.i corresponding to an element A.sub.i of the partition P is a topological closed set whose interior is isolated from all others. This enables the updating of each carrier block CB to be accomplished without interference or contradiction to other carrier blocks CB storing adjacent sub-complexes X.sub.i. That is, when stored in the VAX computer, these carrier blocks CB can be individually retrieved and displayed for updating purposes without impacting on the information stored in other carrier blocks CB.

The areal coverage of each sub-complex X.sub.i of a partition P at a given level may vary, but the amount of detail and, hence, byte size of a carrier block CB, remains substantially constant, which is efficient for storage and retrieval. In a map, for example, a given carrier block CB might cover a few city streets in San Francisco, while another carrier block CB at the same level might cover the whole state of Wyoming, but both would have substantially the same amount of detail.

Efficient utilization of memory space can be further enhanced by employing the encoding techniques which will now be described in relation to FIG. 10. This FIG. 10 shows a given carrier corresponding to two levels such as level 3 and level 2. The n-cells on the boundary of the carriers are stored in a carrier block CB for one or the other levels, but not both. For example, for level 3, the corresponding carrier block CB does not store the n-cells on the boundary of the carrier, but only the interior n-cells. For level 2, the boundary n-cells of the carrier are stored in the corresponding carrier block CB. Thus, the boundary n-cells are stored only once, thereby saving memory space. When the data in the carrier block CB of level 3 is retrieved, the boundary n-cells can be retrieved from the carrier block CB of level 2.

Also, similar encoding can be accomplished for carrier blocks CB at a given level representing adjacent features. That is, the boundary n-cells may be stored in one or the other such carrier blocks CB but not both.

The hierarchy of successively more generalized complexes X, X', X" . . . stored as carrier blocks CB is itself a search index permitting a very efficient search, where the search key is geometrical such as XY coordinate ranges. Also, the index itself is a smaller scale abstraction of the more detailed structure. For example, the index for the element A'.sub.1 of level 2 shown in FIG. 3 is the element A".sub.1 of level 1. At the same time, the complex X" is a useful map of, for example, freeways displayed, e.g., in a "zoomed-out" display, and complex X' is a useful map of major access roads displayed in a "zoomed-in" display. Thus, no additional memory storage space is required for a separate map index as in other systems.

While the present invention has been described using carriers with respect to representations of a topological structure and with respect to a geometric structure, such as the above-mentioned DIME data base, it also may be used, for example, with respect to point sets.

VII. Computer Program Listings

Source code listings in "C" language for instructing a computer to perform the above-described algorithms are included as part of this specification in the form of copies of computer printout sheets. These source code listings may be used in connection with the VAX computer previously described or in connection with the above-mentioned vehicle on-board computer which may use an INTEL8088 microprocessor chip manufactured by Intel Corporation, Santa Clara, Calif., as is appropriate. The titles and general content of these listings are as follows:

1. CARRIER.H;2--This provides definitions of data structures and layouts for the programs.

2. STRUCT.H;2--This is a DIME representation of a complex.

3. BUILDLEAF.C;1--This calls AMOEBA.C;1.

4. AMOEBA.C;1--This builds the sub-complexes X.sub.i from the DIME file.

5. SMTOCARR.C;1--This format carrier blocks CB from the sub-complexes X.sub.i.

6. BUILDANC.C;1--This starts the process for building complexes X' . . .

7. ANCESTOR.C;1 (and Parent amoeba program)--This has the loop for building next level carrier blocks CB and interacting until build one carrier block CB.

8. FND.sub.-- PRTS.C--This implements the Bottom-Up search.

9. FND.sub.-- KIDS.C--This implements the Top-Down search.

10. FND.sub.-- SIBS.C--This implements the Across search.

All right, title and interest in copyright to the computer programs disclosed in this specification is owned by the assignee of the present invention. Accordingly, the following copyright notice is deemed to apply to each and every one of these programs.

The foregoing description of preferred embodiments of the invention has been presented for purposes of illustration and description. It is not inended to be exhaustive or to limit the invention to the precise form described, and many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the art to best utilize the invention in various embodiments and with various modification as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto. ##SPC1##

Claims

We claim:

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.sub.i of a topological complex X, the sub-complex X.sub.i having a set of n-cells, where 0.ltoreq.n.ltoreq. 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.sub.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.sub.j of another said carrier block for i.noteq.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.sub.i has an interior which is disjoint from the interior of another sub-complex X.sub.j of said complex X for i.noteq.j, and wherein said sub-complexes X.sub.i and X.sub.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.sub.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.sub.i corresponding to an element A.sub.i of a partition P at the first level, each said sub-complex X.sub.i having n-cells, where n=0, 1, 2 . . . , and the 2-cells c.sup.2.sub.i of the sub-complex X.sub.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.sub.i on a data storage medium; b) for each said sub-complex X.sub.i, fusing all the 2-cells c.sup.2.sub.i in one said sub-complex X.sub.i to form a single 2-cell c'.sup.2.sub.i ; c) identifying a 1-complex of 1-cells c.sup.1.sub.i on the boundary of the single 2-cells c'.sub.2.sub.i and the 0-cells c.sup.0.sub.i bounding those 1-cells c.sup.1.sub.i, where those 0-cells c.sup.0.sub.i incident to t 1-cells c.sup.1.sub.i are essential 0-cells c.sup.0.sub.i, where t=2; d) constructing connected chains of 1-cells c.sup.1.sub.i so that each chain c.sup.1.sub.i is bounded by the essential 0-cells c.sup.0.sub.i, where these chains of 1-cells c.sup.1.sub.i are common to adjacent sub-complexes X.sub.i or on the boundary of the entire complex X; e) fusing each chain of 1-cells c.sup.1.sub.i to form a 1-cell c'.sup.1.sub.i ; and f) for each essential 0-cell c.sup.0.sub.i, creating a chain of 0-cells c.sup.0.sub.k having a single 0-cell and mapping this chain into the 0-cell c'.sup.0.sub.m as a copy of the essential 0-cell c.sup.0.sub.i, whereby the n-cells c'.sup.2.sub.i, c'.sup.1.sub.i and c'.sup.0.sub.m constitute the topological complex X'.

10. A method, according to claim 9, wherein the step of fusing each chain of 1-cells c'.sub.i comprises reducing the geometrical complexity of the 1-cells c'.sup.1.sub.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.sub.i ={c.sup.2.sub.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.sup.2.sub.j in the complex X not already included in a prior element A.sub.i in the partition P; c) incrementing the counter k and initializing a register A.sub.k storing element A.sub.k to store only the selected 2-cell c.sup.2.sub.j of a sub-complex X.sub.k ; d) adding all 1-cells and 0-cells incident to the selected 2-cells c.sup.2.sub.j to provide a sub-complex X.sub.k being a topological closed set; e) selecting another 2-cell c.sup.2.sub.j in the complex X not already included in a prior element A.sub.i and adjacent a 2-cell c.sup.2.sub.j in the sub-complex X.sub.k ; f) testing whether adding the 2-cell c.sup.2.sub.j selected in step e) and all 1-cells and 0-cells incident thereto to the sub-complex X.sub.k would cause the sub-complex X.sub.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.sup.2.sub.j tested in step f) to register A.sub.k and adjoining this 2-cell c.sup.2.sub.j and all its incident 1-cells and 0-cells to keep the sub-complex X.sub.k a closed set; i) returning to step e); j) since element A.sub.k and sub-complex X.sub.k are complete, adding element A.sub.k to a register P storing the partition P and storing the sub-complex X.sub.k ; and k) going to step b) if there remains any 2-cell c.sup.2.sub.j in some element A.sub.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.

Patent Citations (5)

Patent	Date	Inventor
US4343037	1982-08-01	Bolton
US4360876	1982-11-01	Girault et al.
US4445186	1984-04-01	Caron et al.
US4489389	1984-12-01	Beckwith et al.
US4511975	1985-04-01	Miura et al.

Non-Patent Literature (5)

Topological Principles in Cartography, James P. Corbett, Technical Paper 48, U.S. Department of Commerce, Bureau of the Census, Dec. 1979.
"CARGuide--On-board Computer for Automobile Route Guidance," M. Sugie, O. Menzilcioglu, H.T. Kung, AFIPS Conference Proceedings, 1984 National Computer Conference.
"A Tiger for Tomorrow," Roland H. Moore, Joint Symposium for Urban Data Management Systems and the Spatially Oriented Referencing Systems Association, The Hague, Netherlands, Jun. 3, 1985.
"Two-Dimensional Closed Surface Model for Processing Geographical Information with a Computer," Mario Nakamori, Collection of Lecture Papers from the 19th National Conference, Information Processing Society of Japan, Aug. 22-24, 1978. (In Japanese, with English Translation provided.)
"Algorithm for Studying Topological Characteristics of a Complex in a Closed Surface and a Data Structure," Mario Nakamori, Collection of Lecture Papers in the National Conference of the Information Division of the Institute of Electronics and Communication Engineers, Aug. 1977. (In Japanese, with English Translation provided.)

Abstract

Description