Method and system for forming and using geographic data

• US 5,953,722 A
• Filed: 09/05/1997
• Issued: 09/14/1999
• Est. Priority Date: 10/25/1996
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Lampert, David S., Ashby, Richard A.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/935,809
• Time in Patent Office: 739 Days
• Field of Search: 701/200, 701/201, 701/208, 701/209, 707/100, 707/104, 707/2
• US Class Current: 1/1
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for making and using a geographic database. The geographic database represents a geographic region and is used with a navigation application program. The geographic database includes a plurality of data entities each of which represents a physical feature in the geographic region. The plurality of data entities are separated into a plurality of parcels each of which contains a grouping of data entities that represent features in the geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the features in the entire geographic region represented by all of the plurality of data entities. Each of the plurality of data entities has a data entity ID. The data entities contained in each of the plurality of parcels define an associated range of data entity ID'"'"'s associated with their respective parcel such that the range of data entity ID'"'"'s associated with each parcel does not overlap the range of data entity ID'"'"'s associated with any another of the plurality of parcels. Associated with the geographic database is a searchable kd-tree structure whose nodes represent divisions of the geographic region into the rectangles from which the parcels are formed. The kd-tree structure permits spatial searching for a parcel based upon geographic coordinates. The kd-tree also includes data at certain of its nodes that identify the ranges of data entity ID'"'"'s included in parcels formed from rectangles resulting from the divisions thereby enabling the kd-tree to be used as a binary tree for performing searches using the data entity ID'"'"'s. Navigation application program functions can search for data by utilizing the kd-tree to conduct either a spatial search using geographic coordinates or a binary search using a data entity ID.

Claims

1. A method of making a geographic database for a geographic region comprising:

separating a plurality of data entities of a first type into a plurality of parcels wherein each parcel includes a subset of said plurality of data entities of said first type, and wherein the subset of said plurality of data entities of said first type in each parcel represents features in a geographic area encompassed within a separate rectangle of a plurality of rectangles which together encompass all the features in the entire geographic region represented by said plurality of data entities of said first type; and

assigning each of the plurality of data entities of said first type a data entity ID, such that all the data entities of said first type in each parcel have entity ID'"'"'s that are either greater than or less than all the data entity ID'"'"'s in all the other parcels containing data entities of said first type,

wherein all of the rectangles encompassing features represented by data entities which are assigned data entity ID'"'"'s greater than the data entity ID'"'"'s in any one rectangle are located on the same side of either an east-west boundary of said one rectangle or a north-south boundary of said one rectangle.

2. The method of claim 1 wherein said plurality of data entities of said first type in each parcel are assigned data entity ID'"'"'s in Peano-key order.

3. The method of claim 1 wherein said plurality of data entities of said first type in each parcel are assigned data entity ID'"'"'s by order in one dimension.

4. The method of claim 1 further comprising the step of:

forming a kd-tree index of the parcels.

5. The method of claim 4 further comprising the step of:

ordering said parcels in a depth first order from the kd-tree index of the parcels.

6. The method of claim 4 further comprising the step of:

including an indication of a range of entity ID'"'"'s in each node of said kd-tree which represents a corresponding parcel which contains said range of entity ID'"'"'s.

7. The method of claim 1 further comprising the step of:

after the step of assigning each of said date entities of said first type a data entity ID, separating a plurality of data entities of a second type into a plurality of additional parcels, wherein said data entities of said second type represent said features in said geographic region and wherein each of said plurality of data entities of said second type corresponds to a respective one of said plurality of data entities of said first type, and wherein each additional parcel includes a subset of said plurality of data entities of said second type, and wherein the subset of said plurality of data entities of said second type in each additional parcel represent features in a geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities of said second type in the entire geographic region, wherein the plurality of rectangles which encompass the subsets of data entities of said second type and the plurality of rectangles which encompass the subsets of data entities of said first type coincide with each other.

8. The method of claim 7 further comprising the step of:

forming a kd-tree index of the parcels of said first type of data.

9. The method of claim 8 further comprising the step of:

ordering said parcels in a depth first order from the kd-tree index of the parcels.

10. The method of claim 1 further comprising the step of:

after the step of assigning each of said data entities of said first type a data entity ID, separating a plurality of data entities of a second type into a plurality of additional parcels, wherein said data entities of said second type represent said features in said geographic region and wherein each of said plurality of data entities of said second type corresponds to a respective one of said plurality of data entities of said first type, and wherein each additional parcel includes a subset of said plurality of data entities of said second type, and wherein the subset of said plurality of data entities of said second type in each additional parcel represent features in said geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities of said second type in the entire geographic region, and wherein any of the plurality of rectangular areas which encompasses a subset of data entities of said second type which is smaller in area than the rectangular area which encompasses corresponding data entities of the first type is formed at a division of the rectangular area encompassing the data entities of the first type so that the data entity ID'"'"'s assigned to the data entities on one side of the division are all greater than the data entity ID'"'"'s assigned to the data entities on the other side of the division.

11. The method of claim 10 further comprising the step of:

forming a kd-tree index of the parcels of said first type of data.

12. The method of claim 11 further comprising the step of ordering said parcels in a depth first order from the kd-tree index of the parcels.

13. The method of claim 7 wherein said data entities of said first type are routing data entities used by a route calculation function in a navigation application program and said data entities of said second type are cartographic data entities used by a map display function in said navigation application program.

14. A geographic database stored on a storage medium, said geographic database for use with a navigation application program and representing a geographic region, said geographic database comprising:

a plurality of data entities each of which represents a physical feature in the geographic region, wherein said plurality of data entities are separated into a plurality of parcels each of which contains data entities that represent features in a geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities in the entire geographic region;

wherein each of said plurality of data entities has a data entity ID;

wherein each of said plurality of parcels contains a disjoint range of data entity ID'"'"'s associated with data entities in their respective parcel; and

wherein each of the rectangles encompassing features represented by data entities which are assigned data entity ID'"'"'s greater than the data entity ID'"'"'s in any one rectangle are located on the same side of either an east-west boundary of said one rectangle or a north-south boundary of said at least rectangle.

15. In combination:

the geographic database of claim 14; and

a kd-tree search index whose root and internal nodes correspond to divisions of said geographic region which form said plurality of rectangles, and whose nodes which represent rectangles from which parcels are formed include data identifying the ranges of data entity ID'"'"'s included in the parcels so formed.

16. A search tree for parcels of geographic data embodied on a computer readable medium, wherein said geographic data corresponds to a geographic region wherein each parcel includes data represented by a range of entity identifications, comprising:

kd-tree structure having a root node, internal nodes, and leaf nodes, wherein each node except for said leaf nodes thereof correspond to a division in said geographic region; and

wherein each node of the kd-tree structure that represents a division in said geographic region resulting in formation of an area that encompasses features represented by data corresponding to a parcel also includes information identifying a range of data entity identifications included in the parcel.

17. The invention of claim 16 wherein the range of data entity identifications associated with each parcel does not overlap the range of data entity identifications associated with any other parcel.

18. A geographic database stored on a computer-readable medium comprising:

a plurality of data entities representing physical features in a geographic region, wherein each of said plurality of data entities represents a feature in said geographic region and each of said plurality of data entities has associated therewith attributes identifying a position of the feature represented thereby;

wherein said plurality of data entities are arranged into a plurality of parcels wherein each parcel includes a portion of said plurality of data entities and each parcel corresponds to an amount of data that can be read in a disk access of said medium;

and wherein each of said plurality of data entities has an associated entity identification, such that the data entities in each parcel define a range of data entity identifications associated with the parcel; and

wherein the range of entity identifications in each of said parcels does not overlap with the range of entity identifications in any other of said parcels.

19. A search tree for a plurality of parcels of geographic data embodied on a computer readable medium, wherein said geographic data corresponds to a geographic region wherein each parcel of said plurality of parcels includes data represented by a range of entity identifications, the search tree comprising:

kd-tree having a root nodes, internal nodes and leaf nodes, wherein each kd-tree node except for said leaf nodes thereof correspond to a division in said geographic region; and

a binary tree for said entity identifications, said binary tree having a plurality of binary tree nodes, wherein each binary tree node represents a separate range of entity identifications; and

wherein said binary tree is embedded within said kd-tree such that each binary tree node corresponds in position to the kd-tree node that represents the division that forms the parcel containing the range of entity identifications included in said parcel.

20. A method of searching for geographic data in a geographic database using a computer program, wherein the computer program performs the steps comprising of:

using a data entity ID to search nodes of a kd-tree for data indicating ranges of data entity ID'"'"'s associated with divisions represented by nodes of said kd-tree; and

obtaining data identifying a location in said geographic database at which desired geographic data are located by reference to one of said kd-tree nodes representing a division from which a parcel containing the data represented by said data entity ID was formed.

21. A geographic database structure embodied on a computer-readable medium, wherein geographic data are organized in a kd-tree searchable structure, and wherein each node of said kd-tree structure includes an entity identification indicative of a division of entities identifications so that said kd-tree can be used as a binary search tree using said entity identification divisions.

22. A method of making a geographic database for a geographic region comprising:

separating a plurality of data entities into a plurality of parcels wherein each of said data entities represents a physical feature in the geographic region and each parcel includes a subset of said plurality of data entities, and wherein the data entities in each parcel represent features in a geographic area encompassed within a separate one of a plurality of rectangles which together encompass all the plurality of data entities in the entire geographic region,

assigning each of the plurality of data entities a data entity ID, such that all the data entities in each parcel have data entity ID'"'"'s that are either greater than or less than all the data entity ID'"'"'s in all the other parcels, and wherein within each parcel, data entity ID'"'"'s are assigned so that at least one straight line division of the rectangular area encompassing the data entities in said parcel can be made which divides said data entities into two further rectangular areas which encompass data entities having data entity ID'"'"'s which do not overlap each other.

23. A method of making a geographic database for a geographic region comprising:

separating a plurality of data entities of a first type into a plurality of parcels wherein each parcel includes a subset of said plurality of data entities of said first type,

and wherein the subset of said plurality of data entities of said first type in each parcel represent features in a geographic area encompassed within a separate one of a plurality of rectangles each of which is formed by a set of rectangle boundary segments, such that all the features in the entire geographic region represented by said plurality of data entities of said first type are encompassed by said plurality of rectangles; and

assigning each of the plurality of data entities of said first type a data entity ID, such that there exists a first set of horizontal and vertical line segments such that each of said rectangle boundary segments is contained in one of a first set of horizontal and vertical line segments, and

further wherein all data entities of said first type which represent features due north of a horizontal line segment of said first set have data entity ID'"'"'s which are greater than those of any data entities of said first type which represent features due south of said horizontal line segment of said first set and all data entities of said first type which represent features due east of a vertical line segment of said first set have data entity ID'"'"'s which are greater that those of any data entities of said first type which represent features due west of said vertical line segment of said first set,

wherein a feature is due north of a horizontal line segment of the first set if the latitude of the feature is greater than the common latitude of the end points of the horizontal line segment of the first set and the longitude of the feature lies between the longitudes of the end points of the horizontal line segment of the first set,

wherein a feature is due south of a horizontal line segment of the first set if the latitude of the feature is less than the common latitude of the end points of the horizontal lines segment of the first set and the longitude of the feature lies between the longitudes of the end points of the horizontal line segment of the first set,

wherein a feature is due west of a vertical line segment of the first set if the longitude of the feature is greater than the common longitude of the end points of the vertical line segment of the first set and the latitude of the feature lies between the latitudes of the end points of the vertical line segment of the first set, and

wherein a feature is due east of a vertical line segment of the first set if the longitude of the feature is less than the common longitude of the end points of the vertical line segment of the first set and the latitude of the feature lies between the longitudes of the end points of the vertical line segment of the first set.