Parcelization of geographic data for storage and use in a navigation application

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

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Ashby, Richard A.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/924,328
• Time in Patent Office: 781 Days
• Field of Search: 707/100, 707/104, 701/200, 701/201, 701/202, 701/209, 340/990, 340/995, 340/996
• US Class Current: 1/1
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G06F 16/29 Geographical information databases
• 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/99945 Object-oriented database structure processing

Abstract

A system and method for arranging and storing a plurality of records of geographic data, wherein each record corresponds to a physical feature having a physical location in a geographic region. The method and system comprise arranging the records of geographic data into a plurality of parcels. Each parcel includes records of geographic data that represent features having physical locations encompassed within a corresponding associated rectangular area located in the geographic region. The size and location of each such rectangular area associated with a parcel is determined by a series of divisions of a bounding rectangle that encompasses all of the features represented by the plurality of records into further rectangular areas. Each division, subsequent to an initial division, is made on a rectangular area resulting from the preceding division. Each such division of a rectangular area is made at a location along the rectangular area based upon an assessment of one or more trial divisions of the rectangular area at one or more locations. A division is selected based upon a comparison of the quantities of data encompassed by the rectangular area and each of the further rectangular areas formed by the one or more trial divisions. The assessment is based upon a comparison of these quantities of data for each such trial division to a plurality of ranges of acceptable data quantities. These acceptable sizes are derived from a desired fill percentage of parcels with data.

Claims

1. A method of storing a plurality of records of geographic data on a storage medium, wherein each record represents a physical feature having a physical location in a geographic region, the method comprising the steps of

separating said plurality of records into first and second groupings of records wherein the records in said first of said groupings represent physical features having geographic locations encompassed within a first rectangular area and the records in said second of said groupings represent physical features having geographic locations encompassed within a second rectangular area,

wherein said first and said second rectangular areas are formed by a division at a position of a rectangular area that encompasses the locations of the physical features represented by the plurality of records in said first and second groupings, wherein said position of said division is determined by

ranking trial divisions of said rectangular area;

and

selecting the position of said division by evaluating said ranking of said trial divisions.

2. The method of claim 1 wherein said ranking step further comprises:

comparing sizes of trial first and second groupings of records resulting from said trial divisions of said rectangular area; and

assigning a ranking to each of said trial divisions based upon said comparing step.

3. The method of claim 2 wherein said comparing step further comprises:

comparing said sizes of said trial first and second groupings to a first plurality of ranges of sizes, and wherein said ranking assigned to each of said trial divisions is based upon said sizes of said trial first and second groupings of records having sizes within ranges of said first plurality of ranges of sizes.

4. The method of claim 3 wherein said first plurality of ranges of sizes is based upon a fill percentage of between 80 and 100 percent for a parcel formed of one of said groupings of records.

5. The method of claim 1 further comprising:

ascertaining an aspect ratio of at least one trial rectangle formed by each of said trial divisions; and

wherein said selecting step is based upon evaluating both said aspect ratio and said ranking of each of said trial divisions.

6. The method of claim 2 wherein said comparing step further comprises:

comparing said sizes of trial first and second groupings to a first plurality of ranges of sizes and a second plurality of ranges of sizes;

assigning a first rating to each of said trial divisions based upon whether the first and second groupings of records produced by the trial division have sizes within said ranges in said first plurality of ranges of sizes and assigning a second rating to each of said trial divisions based upon whether the first and second groupings of records produced by the trial division have sizes within said ranges in said second plurality of ranges of sizes; and

wherein said selecting step is further characterized as selecting the position of said division based upon a combination of said first and said second ratings for each trial division.

7. The method of claim 6 further comprising:

ascertaining an aspect ratio of at least one trial rectangle formed by each of said trial divisions; and

selecting the position of said division based upon both said aspect ratio and said combination of said first and said second ratings for each trial division.

8. The method of claim 6 wherein said first plurality of ranges of sizes is based upon a desired fill percentage between 80 and 100 percent for a parcel formed of one of said groupings of records and said second plurality of ranges of sizes is based upon a fill percentage of between 84 and 96 percent for a parcel formed of one of said groupings of records.

9. The method of claim 6 wherein said first plurality of ranges of sizes is based upon a predetermined desired fill percentage for a parcel formed of one of said groupings of records and said second plurality of ranges of sizes is based upon an accuracy factor associated with an estimation of a size of said one of said groupings when formed into a parcel.

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

forming one of said first and second groupings of records into a parcel upon evaluation of a size of said grouping not exceeding a predetermined desired maximum parcel size.

11. The method of claim 1 further comprising;

upon determining that a size of one of said first and second groupings formed by said separating step exceeds a predetermined threshold, separating said one grouping into further first and second groupings by applying the same separating step to said one grouping that had been applied to said plurality of records.

12. The method of claim 1 further comprising;

upon determining that a size of one of said first and second groupings formed by said separating step exceeds a predetermined threshold, continuing to apply said separating said one grouping and to all groupings formed therefrom until each of said groupings has a size that does not exceed a predetermined desired maximum parcel size.

13. The method of claim 1 wherein said ranking step further comprises:

comparing sizes of trial first and second groupings of records resulting from said trial divisions of said rectangular area to a first plurality of ranges of sizes; and

and wherein, if said sizes of both said first and second groupings are less than a minimum parcel size, said selecting step is further characterized as selecting a division so that one of said groupings has a size in a range within a predetermined fill percentage of a fraction of said minimum parcel size, wherein the fraction is selected from a group consisting of;

1/2, 1/4, and 1/8.

14. The method of claim 1 wherein said records represent segments of roads in geographic region.

15. The method of claim 14 wherein said records are routing data records that include information about speed of travel and turn restrictions along each of said segments.

16. The method of claim 14 wherein said records are cartographic data records that are used to display shapes of said segments of roads on a computer display.

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

forming one of said first and second groupings of records into a parcel upon evaluation of a size of said grouping not exceeding a predetermined desired maximum parcel size, wherein said parcel size represents a minimum quantity of data that can be accessed by a navigation system in a single access operation.

18. The method of claim 17 wherein said forming step further comprises the step of:

when forming said one of first and second groupings of records into a parcel, adding an amount of padding to said grouping of records so that said grouping and said padding together are equal to the predetermined desired maximum parcel size.

20. A geographic database stored on a computer readable medium where said database is formatted by the process of claim 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, or 19.

19. A method of manufacturing a geographic database for a geographic region for use by a navigation application program, wherein said geographic database is stored on a computer-readable medium and wherein said geographic database includes a plurality of records wherein each record corresponds to a physical feature having a physical location in the geographic region, the method comprising the steps of:

arranging said records of geographic data into a plurality of parcels according to a method that stores in each parcel records of geographic data that represent features having physical locations in proximity to each other and wherein the records stored in any one parcel represent features having locations encompassed within a corresponding rectangular area associated therewith and located in said geographic region;

wherein a size and location of each rectangular area associated with a parcel is determined by a series of divisions of a rectangular area encompassing all of said features represented by said plurality of records, wherein each division of said series of divisions subsequent to an initial division is made on a rectangular area from the preceding division; and

wherein each division of a rectangle area into further rectangular areas is made at a location of said rectangular area based upon an assessment of quantities of data that represent features encompassed by said rectangular area and each of said further rectangular areas, based upon a comparison of said quantities of data to a plurality of ranges of acceptable sizes derived from a desired fill percentage of parcels with data.