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

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
72Forward
Citations 
0
Petitions 
1
Assignment
First 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 subcomplex X.sub.i of a topological complex X, the subcomplex X.sub.i having a set of ncells, 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.
1 Assignment
0 Petitions
Accused Products
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.
77 Citations
View as Search Results
Transportation routing  
Patent #
US 7,908,080 B2
Filed 12/31/2004

Current Assignee
Google LLC

Sponsoring Entity
Google Inc.

GPSgenerated traffic information  
Patent #
US 7,880,642 B2
Filed 06/10/2009

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

System and method of wireless downloads of map and geographic based data to portable computing devices  
Patent #
US 8,014,945 B2
Filed 08/18/2009

Current Assignee
Tierravision Incorporated

Sponsoring Entity
Tierravision Incorporated

System and method for contiguous images from polygons  
Patent #
US 7,737,998 B1
Filed 09/18/2007

Current Assignee
ATT Intellectual Property II LP

Sponsoring Entity
ATT Intellectual Property II LP

SYSTEM AND METHOD OF WIRELESS DOWNLOADS OF MAP AND GEOGRAPHIC BASED DATA TO PORTABLE COMPUTING DEVICES  
Patent #
US 20100075643A1
Filed 08/18/2009

Current Assignee
Tierravision Incorporated

Sponsoring Entity
Tierravision Incorporated

Method of organizing and compressing spatial data  
Patent #
RE41983E1
Filed 08/25/2008

Current Assignee
Tierravision Incorporated

Sponsoring Entity
Tierravision Incorporated

System and method for predicting travel time for a travel route  
Patent #
US 7,508,321 B2
Filed 08/15/2006

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

GPSgenerated traffic information  
Patent #
US 7,557,730 B2
Filed 05/21/2007

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

APPARATUS, METHOD, AND COMPUTER PROGRAM PRODUCT FOR CHARACTERIZING USERDEFINED AREAS  
Patent #
US 20090265452A1
Filed 06/30/2009

Current Assignee
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasil, DeTuno Joe

Sponsoring Entity
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasil, DeTuno Joe

APPARATUS, METHOD, AND COMPUTER PROGRAM PRODUCT FOR CHARACTERIZING USERDEFINED AREAS  
Patent #
US 20090265323A1
Filed 06/30/2009

Current Assignee
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasil, DeTuno Joe

Sponsoring Entity
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasil, DeTuno Joe

APPARATUS, METHOD, AND COMPUTER PROGRAM PRODUCT FOR CHARACTERIZING USERDEFINED AREAS  
Patent #
US 20090265285A1
Filed 06/30/2009

Current Assignee
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasll, DeTuno Joe

Sponsoring Entity
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasll, DeTuno Joe

APPARATUS, METHOD, AND COMPUTER PROGRAM PRODUCT FOR CHARACTERIZING USERDEFINED AREAS  
Patent #
US 20090271718A1
Filed 06/30/2009

Current Assignee
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasil, DeTuno Joe

Sponsoring Entity
Woodworth Ashley, Meyer Robert Allan, Balaishis David M., Dennison Jack, Nadzakov Vasil, DeTuno Joe

APPARATUS, METHOD, AND COMPUTER PROGRAM PRODUCT FOR CHARACTERIZING USERDEFINED AREAS  
Patent #
US 20090254841A1
Filed 11/11/2008

Current Assignee
MOVE SALES INC.

Sponsoring Entity
MOVE SALES INC.

Traffic routing based on segment travel time  
Patent #
US 7,375,649 B2
Filed 08/24/2006

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

TopologyBased Method of Partition, Analysis, and Simplification of Dynamical Images and its Applications  
Patent #
US 20070036434A1
Filed 08/01/2006

Current Assignee
Saveliev Peter

Sponsoring Entity
Saveliev Peter

System and method for use and storage of geographic data on physical media  
Patent #
US 7,197,500 B1
Filed 10/22/2001

Current Assignee
HERE Global B.V.

Sponsoring Entity
Navteq North America LLC

Parcelized geographic data medium with internal spatial indices and method and system for use and formation thereof  
Patent #
US 7,266,560 B2
Filed 01/30/1998

Current Assignee
HERE Global B.V.

Sponsoring Entity
Navteq North America LLC

System and method for contiguous images from polygons  
Patent #
US 7,286,144 B2
Filed 10/13/2004

Current Assignee
ATT Inc.

Sponsoring Entity
ATT Inc.

System and method of wireless downloads of map and geographic based data to portable computing devices  
Patent #
US 20060058951A1
Filed 09/07/2005

Current Assignee
Alfred M. Wallner, Cooper Clive W.R.

Sponsoring Entity
Alfred M. Wallner, Cooper Clive W.R.

Method for generating contiguous cartograms  
Patent #
US 6,853,386 B1
Filed 02/21/2003

Current Assignee
ATT Inc.

Sponsoring Entity
ATT Inc.

System and method for contiguous images from polygons  
Patent #
US 20050062763A1
Filed 10/13/2004

Current Assignee
ATT Inc.

Sponsoring Entity
ATT Inc.

Method and system of vectorial cartography  
Patent #
US 6,873,943 B2
Filed 12/19/2001

Current Assignee
VISTEON SOFTWARE TECHNOLOGIES

Sponsoring Entity
VISTEON SOFTWARE TECHNOLOGIES

Digital altimetric map drawing method and device  
Patent #
US 20050104884A1
Filed 04/21/2003

Current Assignee
DGS COMPUTER

Sponsoring Entity
DGS COMPUTER

Method for determining the intersection of polygons used to represent geographic features  
Patent #
US 6,917,877 B2
Filed 08/14/2001

Current Assignee
HERE Global B.V.

Sponsoring Entity
Navteq North America LLC

Control system for tracking and targeting multiple autonomous objects  
Patent #
US 20040006424A1
Filed 06/30/2003

Current Assignee
Tarbox Brian, Joyce Glenn J.

Sponsoring Entity
Tarbox Brian, Joyce Glenn J.

PARCELIZED GEOGRAPHIC DATA MEDIUM WITH INTERNAL SPATIAL INDICES AND METHOD AND SYSTEM FOR USE AND FORMATION THEREOF  
Patent #
US 20040205517A1
Filed 01/30/1998

Current Assignee
HERE Global B.V.

Sponsoring Entity
HERE Global B.V.

Method and system of vectorial cartography  
Patent #
US 20030040893A1
Filed 12/19/2001

Current Assignee
VISTEON SOFTWARE TECHNOLOGIES

Sponsoring Entity
VISTEON SOFTWARE TECHNOLOGIES

Method for constructing polygons used to represent geographic features  
Patent #
US 20030132932A1
Filed 09/17/2001

Current Assignee
HERE Holding Corporation

Sponsoring Entity


Interface layer for navigation system  
Patent #
US 6,370,539 B1
Filed 10/23/2000

Current Assignee
HERE Global B.V.

Sponsoring Entity
Navigation Technologies Corporation

Interface layer for navigation system  
Patent #
US 6,173,277 B1
Filed 09/07/1999

Current Assignee
HERE Global B.V.

Sponsoring Entity
Navigation Technologies Corporation

System and method for use and storage of geographic data on physical media  
Patent #
US 6,308,177 B1
Filed 07/28/1999

Current Assignee
HERE Global B.V.

Sponsoring Entity
Israni Vijaya S., Ashby Richard A., Nyczak Gregory M., Smith Nicholas E.

System and method for use and storage of geographic data on physical media  
Patent #
US 5,968,109 A
Filed 10/25/1996

Current Assignee
HERE Global B.V.

Sponsoring Entity
NAVIGATION TECHNOLOGIES CORPORATION

GPSgenerated traffic information  
Patent #
US 8,358,222 B2
Filed 12/13/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method for choosing a traffic route  
Patent #
US 8,531,312 B2
Filed 07/30/2012

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Generating visual information associated with traffic  
Patent #
US 8,564,455 B2
Filed 07/30/2012

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Transportation routing  
Patent #
US 8,606,514 B2
Filed 04/23/2013

Current Assignee
Google LLC

Sponsoring Entity
Google Inc.

Controlling a threedimensional virtual broadcast presentation  
Patent #
US 8,619,072 B2
Filed 03/04/2009

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System and method of wireless downloads of map and geographic based data to portable computing devices  
Patent #
US 8,649,968 B2
Filed 05/04/2012

Current Assignee
Tierravision Incorporated

Sponsoring Entity
Tierravision Incorporated

System and method for delivering departure notifications  
Patent #
US 8,660,780 B2
Filed 12/09/2011

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Crowd sourced traffic reporting  
Patent #
US 8,718,910 B2
Filed 11/14/2011

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System for providing traffic data and driving efficiency data  
Patent #
US 8,725,396 B2
Filed 05/18/2012

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Estimating time travel distributions on signalized arterials  
Patent #
US 8,781,718 B2
Filed 01/28/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

GPS generated traffic information  
Patent #
US 8,786,464 B2
Filed 01/22/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Image Matching System Using Topologically Equivalent Correspondences  
Patent #
US 20140226868A1
Filed 04/14/2014

Current Assignee
A9.com Incorporated

Sponsoring Entity
A9.com Incorporated

Transportation routing  
Patent #
US 8,798,917 B2
Filed 08/09/2013

Current Assignee
Google LLC

Sponsoring Entity
Google Inc.

Image matching system using topologically equivalent correspondences  
Patent #
US 8,867,866 B2
Filed 04/14/2014

Current Assignee
A9.com Incorporated

Sponsoring Entity
A9.com Incorporated

Method for choosing a traffic route  
Patent #
US 8,958,988 B2
Filed 09/10/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Touch screen based interaction with traffic data  
Patent #
US 8,982,116 B2
Filed 08/20/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Gesture based interaction with traffic data  
Patent #
US 9,046,924 B2
Filed 09/14/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method for predicting a travel time for a traffic route  
Patent #
US 9,070,291 B2
Filed 09/17/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Generating visual information associated with traffic  
Patent #
US 9,082,303 B2
Filed 09/17/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System and method for delivering departure notifications  
Patent #
US 9,127,959 B2
Filed 01/14/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System and method of wireless downloads of map and geographic based data to portable computing devices  
Patent #
US 9,137,633 B2
Filed 02/10/2014

Current Assignee
Tierravision Incorporated

Sponsoring Entity
Tierravision Incorporated

Estimating time travel distributions on signalized arterials  
Patent #
US 9,293,039 B2
Filed 07/03/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method and system for generating and storing data objects for multiresolution geometry in a three dimensional model  
Patent #
US 9,311,748 B2
Filed 02/20/2013

Current Assignee
Google LLC

Sponsoring Entity
Google Inc.

Information aggregation for recognized locations  
Patent #
US 9,342,930 B1
Filed 01/25/2013

Current Assignee
A9.com Incorporated

Sponsoring Entity
A9.com Incorporated

GPS generated traffic information  
Patent #
US 9,368,029 B2
Filed 07/09/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System for providing traffic data and driving efficiency data  
Patent #
US 9,390,620 B2
Filed 05/12/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method for predicting a travel time for a traffic route  
Patent #
US 9,401,088 B2
Filed 04/21/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

Controlling a threedimensional virtual broadcast presentation  
Patent #
US 9,448,690 B2
Filed 12/09/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

Method for choosing a traffic route  
Patent #
US 9,489,842 B2
Filed 02/17/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

System for providing traffic data and driving efficiency data  
Patent #
US 9,547,984 B2
Filed 07/11/2016

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

GPS generated traffic information  
Patent #
US 9,602,977 B2
Filed 06/13/2016

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

Generating visual information associated with traffic  
Patent #
US 9,640,073 B2
Filed 07/08/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

System and method for delivering departure notifications  
Patent #
US 9,644,982 B2
Filed 09/04/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Transportation routing  
Patent #
US 9,709,415 B2
Filed 06/25/2014

Current Assignee
Google LLC

Sponsoring Entity
Google LLC

Transportation routing  
Patent #
US 9,778,055 B2
Filed 01/31/2017

Current Assignee
Google LLC

Sponsoring Entity
Google LLC

Transportation routing  
Patent #
US 9,945,686 B2
Filed 01/31/2017

Current Assignee
Google LLC

Sponsoring Entity
Google LLC

Estimating time travel distributions on signalized arterials  
Patent #
US 10,223,909 B2
Filed 10/18/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

System and method of wireless downloads of map and geographic based data to portable computing devices  
Patent #
US 10,244,361 B1
Filed 02/27/2017

Current Assignee
Tierravision Incorporated

Sponsoring Entity
Tierravision Incorporated

Controlling a threedimensional virtual broadcast presentation  
Patent #
US 10,289,264 B2
Filed 09/20/2016

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Identity management and device enrollment in a cloud service  
Patent #
US 10,444,743 B2
Filed 11/13/2018

Current Assignee
General Electric Company

Sponsoring Entity
General Electric Company

Numerical control machine tool  
Patent #
US 4,511,975 A
Filed 05/21/1982

Current Assignee
Fujitsu Fanuc Limited

Sponsoring Entity
Fujitsu Fanuc Limited

Underwater mapping apparatus and method  
Patent #
US 4,445,186 A
Filed 07/02/1980

Current Assignee
KeyBank National Association

Sponsoring Entity
EGG Inc.

Real time video perspective digital map display  
Patent #
US 4,489,389 A
Filed 10/02/1981

Current Assignee
Harris Corporation

Sponsoring Entity
Harris Corporation

Visual display systems of the computer generated image type  
Patent #
US 4,343,037 A
Filed 06/13/1980

Current Assignee
Redifon Simulation Limited

Sponsoring Entity
Redifon Simulation Limited

Cartographic indicator system  
Patent #
US 4,360,876 A
Filed 07/02/1980

Current Assignee
ThomsonCSF

Sponsoring Entity
ThomsonCSF

20 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 subcomplex X.sub.i of a topological complex X, the subcomplex X.sub.i having a set of ncells, 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.
 a) a data storage medium; and
 2. Apparatus, according to claim 1, wherein the areal coverage of the features of one portion of the topological structure provided by one said subcomplex 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 subcomplex 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 subcomplex X.sub.i has an interior which is disjoint from the interior of another subcomplex X.sub.j of said complex X for i.noteq.j, and wherein said subcomplexes 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 subcomplex 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 subcomplex X.sub.i corresponding to an element A.sub.i of a partition P at the first level, each said subcomplex X.sub.i having ncells, where n=0, 1, 2 . . . , and the 2cells c.sup.2.sub.i of the subcomplex 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 subcomplex X.sub.i on a data storage medium;
b) for each said subcomplex X.sub.i, fusing all the 2cells c.sup.2.sub.i in one said subcomplex X.sub.i to form a single 2cell c'.sup.2.sub.i ;
c) identifying a 1complex of 1cells c.sup.1.sub.i on the boundary of the single 2cells c'.sub.2.sub.i and the 0cells c.sup.0.sub.i bounding those 1cells c.sup.1.sub.i, where those 0cells c.sup.0.sub.i incident to t 1cells c.sup.1.sub.i are essential 0cells c.sup.0.sub.i, where t=2;
d) constructing connected chains of 1cells c.sup.1.sub.i so that each chain c.sup.1.sub.i is bounded by the essential 0cells c.sup.0.sub.i, where these chains of 1cells c.sup.1.sub.i are common to adjacent subcomplexes X.sub.i or on the boundary of the entire complex X;
e) fusing each chain of 1cells c.sup.1.sub.i to form a 1cell c'.sup.1.sub.i ; and
f) for each essential 0cell c.sup.0.sub.i, creating a chain of 0cells c.sup.0.sub.k having a single 0cell and mapping this chain into the 0cell c'.sup.0.sub.m as a copy of the essential 0cell c.sup.0.sub.i, whereby the ncells c'.sup.2.sub.i, c'.sup.1.sub.i and c'.sup.0.sub.m constitute the topological complex X'.  View Dependent Claims (10, 11, 12, 13)
 a) providing each said subcomplex X.sub.i on a data storage medium;
 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 ncells 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 2cell 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 2cell c.sup.2.sub.j of a subcomplex X.sub.k ;
d) adding all 1cells and 0cells incident to the selected 2cells c.sup.2.sub.j to provide a subcomplex X.sub.k being a topological closed set;
e) selecting another 2cell c.sup.2.sub.j in the complex X not already included in a prior element A.sub.i and adjacent a 2cell c.sup.2.sub.j in the subcomplex X.sub.k ;
f) testing whether adding the 2cell c.sup.2.sub.j selected in step e) and all 1cells and 0cells incident thereto to the subcomplex X.sub.k would cause the subcomplex 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 2cell c.sup.2.sub.j tested in step f) to register A.sub.k and adjoining this 2cell c.sup.2.sub.j and all its incident 1cells and 0cells to keep the subcomplex X.sub.k a closed set;
i) returning to step e);
j) since element A.sub.k and subcomplex X.sub.k are complete, adding element A.sub.k to a register P storing the partition P and storing the subcomplex X.sub.k ; and
k) going to step b) if there remains any 2cell c.sup.2.sub.j in some element A.sub.i.
 a) initializing a counter k;
 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 ncells, 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 0cells, 1cells and 2cells 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 2cell 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).
 a) initializing a first list of selected cells and a second list of current carrier blocks;
 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 ncells, comprising the steps of:
 a) initializing a first list of selected ncells 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 ncells that fall within a given range of a point;
d) exiting if no ncells selected in step c) is on a boundary of a carrier corresponding to the carrier block to output the first list of selected ncells;
e) for each ncell in the first list, if the selected ncell 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).
 a) initializing a first list of selected ncells and a second list of current carrier blocks;
 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 ncells, 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 ncells 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.
 a) initializing a first list of selected cells and a second list of current carrier blocks;
 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.
 a) a data storage medium; and
 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.
 a) a data storage medium; and
1 Specification
This application is a Continuation of Ser. No. 08/599,446, filed Jan. 19, 1996, now abandoned, which is a Continuation of Ser. No. 07/455,827, filed Dec. 15, 1989, now abandoned, which is a Continuation of Ser. No. 07/319,810, filed Mar. 6, 1989, now abandoned, which is Continuation of Ser. No. 07/140,881, filed Jan. 6, 1988, now abandoned, which is a continuation of Ser. No. 06/759,036, filed Jul. 25, 1985, now abandoned.
BACKGROUND OF THE INVENTION1. 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 copending 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 onboard 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 equalsized 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 equalsized cells, it still suffers from the abovedescribed 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" "ncells". 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 INVENTIONIn 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 ncells, and wherein said plurality of carrier blocks include data representing mutuallyadjacent boundaries as ncells and interiors thereof as ncells, 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 ncells of said common boundary and said ncells 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 abovedescribed 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 ncells, where n=0, 1, 2 . . . The three different search algorithms are called, respectively, TOPDOWN, ACROSS and BOTTOMUP. For example, in a structure where n=2, TOPDOWN 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 0cells, 1cells, and 2cells 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 2cell 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 DRAWINGSFIG. 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 2cells 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. 3C1 and 3C2 illustrate pictorially a given arbitrary geometric structure and a carrier for the geometric structure, respectively.
FIGS. 4A1 and 4A2 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 subcomplex 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 "topdown" 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 "bottomup" 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 INVENTIONThe 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 2dimensional geometric structures, such as maps, but, the principles apply to 3dimensional and higherdimensional 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 2dimensional geometric structures in combinatorial topology are 0cells, 1cells, and 2cells. In general, an ncell is a connected, ndimensional geometric object. Thus, as shown in FIG. 1, a 0cell is a point, a 1cell is an open line segment of any shape not intersecting itself or any other ncell, and a 2cell is an "open" disc stretched and formed to any shape not intersecting itself or any other ncell. The term "open" has a certain topological meaning. That is, a 2cell is open if its boundary of 0cells and 1cells is not included and would be closed if its boundary were included. For purposes of describing the present invention, the 2cell 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 0cells labeled 14, respectively, five 1cells labeled af, respectively, and three 2cells (open discs) referenced NM (New Mexico), OK (Oklahoma) and TX (Texas).
A given ncell 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 2dimensional complex X or "2complex" is a collection of 0, 1, and 2cells formed according to the following set of three recursive rules:
1) A 0dimensional complex or "0complex" is a collection of 0cells.
2) A 1dimensional complex or "1complex" includes a 0complex (also known as the 0skeleton), together with a set of 1cells satisfying the conditions that (a) each 1cell is bounded in the 0complex, and each 0cell of the complex is on the boundary of some 1cell of the 1complex. Thus, for example, the 1cell labeled d in FIG. 1 is bounded by the 0complex of 0cells labeled 2 and 4 and each such 0cell is on the boundary of this 1cell.
3) A 2complex includes a 1complex (also known as a 1skeleton), together with a collection of 2cells satisfying the conditions that (a) each 2cell is bounded in the 1complex and each 1cell of the complex is on the boundary of some 2cell of the 2complex. Thus, for example, the 2cell labeled OK (Oklahoma) is bounded in the 1cells labeled b, d and f, and each such 1cell is on the boundary of the 2cell labeled OK.
Thus, the 2complex is similar to a jigsaw puzzle whose pieces are the abovedescribed fundamental topological objects, i.e., ncells, where n is the dimension. Similar definitions can be made for complexes of any dimension, such as a 3dimensional complex which would have 0, 1, 2, and 3cells. A practical example of a 2complex is a DIME data base representing, for example, a street map of a city, as will be described below in relation to FIGS. 4A1 and 4A2.
A 2dimensional complex may be embedded in a 3dimensional space. For example, a map sheet is a 2dimensional and a complex representing it is 2dimensional, 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 "subcomplex" is a subset of the 0, 1, and 2cells that satisfies the conditions for a complex. Thus, the 1skeleton of a 2complex is an example of a subcomplex. Also, the closure of a set of 2cells, which is a set of 2cells, the 1cells bounding any of the 2cells, and the 0cells bounding any of those 1cells, is a subcomplex. For example, with reference to FIG. 1, a closed set would include the 2cell TX, the 1cells c, e, f and the 0cells 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. 3C1 and 3C2.
A linear combination of ncells of the same dimension is called a "chain" and is denoted by:
K.sup.n =.SIGMA.c.sup.n.sub.i
FIGS. 2A and 2B illustrate the topological principle of fusion. As illustrated in FIG. 2A, a pair of 1cells, c.sup.1.sub.i and c.sup.1.sub.j, may be "fused" to form a single 1cell c'.sup.1.sub.i if the pair of cells share a common 0cell, i.e., if they are adjacent. FIG. 2A shows the common 0cell c.sup.0.sub.2. Likewise, as shown in FIG. 2B, a pair of adjacent 2cells c.sup.2.sub.i and c.sup.2.sub.j may be fused to form a chain or single 2cell 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 1cells can be fused into a single 1cell, and chains of adjacent 2cells can be fused to create a single larger 2cell, both by iterating pairwise fusion of the adjacent ncells 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 1cell or 2cell, respectively.
In summary, the fusion operation converts a given complex X into another topologically equivalent complex X':
Fuse: X.fwdarw.X'
As will be described more fully below in relation to FIG. 3, while the original unfused ncells and the fused chain of ncells 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 ncells, such as the unfused 2cells shown in FIG. 2B, represent the geometric region in finer detail than the fused ncell, i.e., the 2cell 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 ncells 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 13. While only three such levels 13 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 ncells fused to create a complex X' of level 2 which, in turn, may have some of its ncells fused to create a complex X" of level 1.
Accordingly, consider a partition P (at a given level) of the set of 2cells c.sup.2.sub.j :
P={A.sub.1, A.sub.2, . . . A.sub.i }, where A.sub.i is an element of the partition P, and
A.sub.i ={c.sup.2.sub.j }, such that the 2cells c.sup.2.sub.j are mutually adjacent.
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 2cells 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 13, in accordance with the present invention a subcomplex X.sub.i is constructed having the 2cells c.sup.2.sub.j in A.sub.i, all 1cells c.sup.1.sub.j incident to those 2cells c.sup.2.sub.j, and all 0cells c.sup.0.sub.j incident to the 1cells c.sup.1.sub.j. The subcomplex 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 13 covers the entire complex X.
Furthermore, the interior of subcomplex X.sub.i is disjoint from the interior of subcomplex 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 subcomplexes X.sub.i and X.sub.j have a chain of 1cells K.sup.1.sub.k on their common boundary. That is, the same chain of 1cells K.sup.1.sub.k occurs in both subcomplexes X.sub.i and X.sub.j. For example, the subcomplex X.sub.1 corresponding to element A.sub.1 and the subcomplex 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 subcomplex X.sub.i, in accordance with the present invention, is said to "carry" a subset of the 0, 1, and 2cells 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 13. Each carrier block CB has a block of digital data representing the corresponding subcomplex X.sub.i at the given level.
Thus, as shown in FIG. 3B, the stored data of a given carrier block CB are 0cells (as XY coordinate data), and 1cells and 2cells (shape information such as DIME encodes 1cells and 2cells). 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 subcomplex X.sub.1 of level 3 of complex X will have a pointer to the subcomplex 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 2cells c.sup.2.sub.j may be constructed, and to avoid proliferation of notation, the chain is denoted by A.sub.i as well:
A.sub.i =.SIGMA.c.sup.2.sub.j.
Because the 2cells c.sup.2.sub.j of an element A.sub.i are mutually adjacent, this chain can be fused together to form a single 2cell c'.sup.2.sub.i. Thus, for example, and as will be further described below, the chain of 2cells c.sup.2.sub.j of each respective element A.sub.1 A.sub.4, is fused into a respective single 2cell 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 2cells, and as will be further described below, ncells 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 2cells is fused into one 2cell, 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 subcomplex X.sub.i .fwdarw. a set of chains of 1cells {K.sup.1.sub.i }, where each of the chains is a chain of adjacent 1cells along the common boundary of a pair of adjacent subcomplexes 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 1cell corresponding to a chain of 1cells K.sup.1.sub.k. For example FIG. 3 shows a chain of 1cells 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 1cell 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 0cell 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 ncells than the complex X (provided the partition P is not the maximal partition P in which element A.sub.i contains exactly one 2cell for every i). By means of this mapping, a simpler cellular decomposition of the 2dimensional 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 2cells with 3cells and extending the fusion of 1 chains to 2chains, the principle of carriers of the present invention applies to 3dimensional structures.
In general, and with reference to FIGS. 3C1 and 3C2, 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. 3C1 shows an arbitrary geometric structure as such a given set, which structure has 0cells, 1cells and 2cells. FIG. 3C2 shows the carrier for that given set, which carrier is the smallest topological closed set containing the given set and corresponds to a given subcomplex X.sub.i stored as a carrier block CB.
Thus, the carrier contains all ncells 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 abovementioned copending 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 ncells 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:
X'.fwdarw.X"
X".fwdarw.X"'
The result is an hierarchy of 2complexes. An arbitrary 2cell 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 2cells, one from each complex in the hierarchy of complexes. Likewise, each subcomplex X.sub.i is contained in a nested hierarchy of subcomplexes 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) largeshowing all the local streets, (level 2) intermediateshowing 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 1cells (c.sup.1.sub.1, c.sup.1.sub.2, c.sub.1.sub.c) at level 3 corresponds to the single 1cell c'.sup.1.sub.A at level 2. Thus, level 2 contains less information than level 3, because a chain of 1cells is fused to a single 1cell at level 2, and 1cells interior to the subcomplexes X.sub.i are effectively absorbed into the 2cell 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 1cells 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 1cells are fused into single 1cells and their geometric representation may be further generalized in the mapping through filtering, chains of 2cells are fused into single 2cells and their geometric description (for example elevation contours) may be filtered to a still more generalized representation.
Single 0cells map into single 0cells or are absorbed within chains of 1cells that map to single 1cells going to the next level of generalization. The 0cells bounding the chains of 1cells map to 0cells and the 0cells interior to the chain are dropped in the mapping. Similarly, 1chains on the boundary of the subcomplexes X.sub.i map into 1cells in X'.sub.i, but 1cells interior of the carriers are absorbed in the fusion of 2cells. In this way, the number of ncells 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 13 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 2cells. 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. 4A1 and 4A2 as having the set of topological open 2cells c.sup.2.sub.j stored in a computer data bank DB. FIG. 4A2 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 0cells and 1cells 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 ncells (such as the abovementioned DIME data base) (block 4B1).
2) Accessing the topological open sets of the partition P on the data storage medium (block 4B2).
3) Generating from the accessed topological open sets the plurality of carrier blocks CB at a given hierarchical level (block 4B3).
4) Storing the generated carrier blocks CB as a digital data base on a storage medium (block 4B4).
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 elementbyelement A.sub.i and at the same time the subcomplexes 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. 4A1 and the flow chart of FIG. 4C:
In referring to FIG. 4A1 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 13 are built and stored, as follows:
1) Initialize or set a counter k=0 (block 4C1) (the counter k represents the subscript i in the element A.sub.i of partition P).
2) Select an arbitrary 2cell in the complex X of data bank DB (block 4C2) not already included in some prior element A.sub.i in P; call it c.sup.2.sub.j (see FIG. 4A1). 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 4C3).
4) Construct the subcomplex X.sub.k by adjoining all 1 and 0cells incident to c.sup.2.sub.j, that is, make the subcomplex X.sub.k a closed set (block 4C4) and store in register X.sub.k.
5) Test whether there is another 2cell c.sup.2.sub.j, (see FIG. 4A1) in the complex X of data bank DB not already included in some prior element A.sub.i, and adjacent to a 2cell in the subcomplex X.sub.k and satisfying any other desired constraint, (such as on the same side of a distinguished 1cell which may be, for example, a major map feature) as other 2cells in register X.sub.k (block 4C5). If there is no other, go to step 9; if there is go to step 6.
6) Test whether adding the 2cell c.sup.2.sub.j, in step 5 and its incident 1cells and 0cells to register X.sub.k would cause the subcomplex 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 4C6). 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 0cells to X.sub.k so as to keep the subcomplex X.sub.k closed (Block 4C7).
8) Go to step 5 above (block 4C8). Note that this would result in selecting yet another 2cell such as 2cell c.sup.2.sub.j" (shown in FIG. 4A1 as the cell for step 5  second pass), possibly resulting in yet another 2cell and incident 0 and 1cells being added to the subcomplex 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 4C9).
10) If there remain any 2cells not in some A.sub.i, go to step 2; if no 2cells then exit (Block 4C10).
The partition P is now complete and each subcomplex 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 2cells with 3cells and incorporating 2cells into the steps for 1cells, the above accretion method applies to 3dimensional 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 2cells 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 13, and 810 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 i1 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 5A1).
2) Accessing the plurality of carrier blocks on the digital data base (block 5A2).
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 ncells of the common boundary and the ncells of the interiors are absorbed in the other carrier block (block 5A3).
4) Storing the other carrier block on a data storage medium (block 5A4).
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 1cells on the common border of mutuallyadjacent 2cells, and those 2cells, 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 subcomplexes 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 ncells. The 0cells in X' correspond to some of the 0cells in X, 1cells to chains of 1cells, and 2cells to chains of 2cells. 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 subcomplex X.sub.i, fuse (see further description below) all the contained 2cells to form a single 2cell c'.sup.2.sub.i (block 5B1). This is possible because the subcomplex X.sub.i was constructed so that the contained 2cells c.sup.2.sub.i were mutually adjacent.
2) Identify the 1dimensional subcomplex comprising the 1cells on the boundaries of 2cell c.sup.2.sub.i and the 0cells bounding those 1cells (Block 5B2) (see FIG. 5C2). This is a subcomplex of the 1skeleton of complex X. Note that an essential 0cell is that 0cell incident to t 1cells, where t is not equal to 2.
3) Construct connected chains of 1cells K.sup.1.sub.j so that each chain is bounded by essential 0cells (block 5B3). These are the 1chains common to adjacent subcomplexes or on the boundary of the entire complex X.
4) Fuse each chain K.sup.1.sub.j to form a 1cell c'.sup.1.sub.j (block 5B4) (see FIG. 5C3). This is possible because each chain is connected. If it is desired to also reduce the "metrical" complexity (not just the topological complexity), the 1cell c'.sup.1.sub.j may be generalized using a straightening algorithm such as the known DouglasPeuker algorithm.
5) For each essential 0cell c.sup.0.sub.k, create a chain K.sup.0.sub.k comprising the single 0cells and map this chain into 0cell c'.sup.0.sub.m, which is just a copy of K.sup.0.sub.k (block 5B5).
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 6A1).
2. Create and store the complex Y' using the NEXT LEVEL algorithm above (Block 6A2).
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 ncells 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 1cells, one allocates memory for a new 1cell, records the bounding 0cells of the new 1cell to be the two bounding 0cells for the chain, records the cobounding 2cells to be the 2cells on the left and right of the chain of 1cells, and records the shape of the new 1cell to be the successive shapes of the chain of 1cells. In addition, it is often useful to store pointers from the new 1cell to the 1cells 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 subcomplexes X.sub.i of level 3 and the 0, 1, and 2cells 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 2cells 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 subcomplex 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, TOPDOWN, ACROSS and BOTTOMUP. 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 abovementioned copending 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 TOPDOWN 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 subcomplexes X.sub.i of the digital map data base at the same level. A BOTTOMUP search is the simplest and proceeds from a detailed level, such as level 3 in FIG. 3, to a more generalized level.
B. TOPDOWN Search
With reference to FIG. 7A and FIG. 7B, to determine which 0cells, 1cells, and 2cells 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 ncells falling within or intersecting the given range. The algorithm includes the following steps:
1) Initialize two lists (Block 7A1), 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 7A2).
3) Select from the second list of current carrier blocks the ncells that fall within a specified range of the point p (see FIG. 7B) (Block 7A3). Note that this step may employ wellknown pointinpolygon and geometric intersection routines. Note further that any geometric range, not just rectangular, could be used by employing different but also wellknown 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 7A4). (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 2cell at the current level in the first list of selected cells, the one carrier block being the carrier block explicitly associated with this 2cell (Block 7A5). (These carrier blocks will all be at the next level (level 2 in FIG. 7B) of the hierarchy.)
6) Decrement the current level (Block 7A6).
7) Go to step 3 (Block 7A7). (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 onboard computer so as to display this information. Also, as shown in FIG. 8B2, 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 ncells 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. 8B1 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. 8B2, the method includes:
1) Initialize two lists (block 8A1), 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 ncells that fall within a specified range of the point p (block 8A3). Note that this step may employ wellknown pointinpolygon and geometric intersection routines. Note further that any geometric range, not just rectangular, could be used by employing different but also wellknown geometric routines, and that any dimension may be used.
4) If none of the ncells selected in step 3 is on the boundary of a carrier, then exit (block 8A4). This exit or output is represented in FIG. 8B4.
5) For each ncell in the first list of selected cells, if the selected ncell 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 8A5). This is shown pictorially in FIG. 8B2 which shows new or adjacent carriers being added.
6) Go to step 3 (block 8A6). This is shown pictorially in FIG. 8B3 as pass 2 in which yet another carrier may be found by iterating.
D. BOTTOMUP Search
This search is used to determine which ncells 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 9A1), 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 9A2).
3) Select from the second list of current carrier blocks the ncells that fall within a specified range of the point p (block 9A3). Note that this step may employ wellknown pointinpolygon and geometric intersection routines. Note further that any geometric range, not just rectangular, could be used by employing different but also wellknown geometric routines, and that any dimension may be used.
4) If the current level is the root, then exit (block 9A4). The output or exit of the method is the first list of selected ncells.
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 copending 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 aboveidentified two copending 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 abovementioned 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 onboard computer, which also is programmed with the abovementioned three search algorithms of the present invention. The search algorithms also can be stored on the portable data storage medium and downloaded into the onboard 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 TOPDOWN 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 onboard computer stores the current location of the vehicle, which, as described in the copending 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 TOPDOWN search to search for and access one carrier block CB corresponding to the respective hierarchical levels, e.g., levels 13 shown in FIG. 3. As an example, at each such level 13, the corresponding block CB is down loaded into the onboard computer and then is available for display, as desired by the driver. That is, as described in the copending 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 13 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 13 and collect the 0, 1 and 2cells which are in the abovementioned range of the position p. These collected ncells are then displayed as a moving map display as the vehicle moves over streets and across neighborhoods.
The BOTTOMUP search is used when the vehicle is first started with the same cassette inserted in the onboard computer, as opposed to a new cassette being inserted as described above for the TOPDOWN search. At this time, the computer also stores information about the position p of the vehicle. In a similar manner as described for the TOPDOWN search, carrier blocks CB corresponding to the hierarchical levels 13 within the abovedescribed range are searched, accessed and down loaded into the computer, thereby being available for display. The BOTTOMUP 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 abovementioned 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 onboard computer of the abovementioned 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 subcomplex 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 subcomplexes 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 subcomplex 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 ncells 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 ncells on the boundary of the carrier, but only the interior ncells. For level 2, the boundary ncells of the carrier are stored in the corresponding carrier block CB. Thus, the boundary ncells are stored only once, thereby saving memory space. When the data in the carrier block CB of level 3 is retrieved, the boundary ncells 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 ncells 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 "zoomedout" display, and complex X' is a useful map of major access roads displayed in a "zoomedin" 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 abovementioned 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 abovedescribed 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 abovementioned vehicle onboard 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;2This provides definitions of data structures and layouts for the programs.
2. STRUCT.H;2This is a DIME representation of a complex.
3. BUILDLEAF.C;1This calls AMOEBA.C;1.
4. AMOEBA.C;1This builds the subcomplexes X.sub.i from the DIME file.
5. SMTOCARR.C;1This format carrier blocks CB from the subcomplexes X.sub.i.
6. BUILDANC.C;1This 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.CThis implements the BottomUp search.
9. FND.sub. KIDS.CThis implements the TopDown search.
10. FND.sub. SIBS.CThis 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.
Copyright 1985 Etak, Inc.
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##