초록 ▼

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

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.

대표청구항 ▼

[ We claim:] [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 geogra

[ We claim:] [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; andwherein 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.