Method for organizing map data

• US 6,782,319 B1
• Filed: 11/26/2002
• Issued: 08/24/2004
• Est. Priority Date: 11/26/2002
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: McDonough, William G.
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US10/304,229
• Time in Patent Office: 637 Days
• Field of Search: 701/200, 701/203, 340/990, 340/995.1, 707/102, 707/104.1
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of organizing map data on a physical storage medium is disclosed. The map data represents geographic features located in a geographic region. The method identifies at least one dense area in the geographic region. The map data representing the geographic features within the dense area have a data size exceeding a predetermined maximum size for a predetermined sized geographic area of the region. The method subdivides the map data representing the geographic features within the dense area into parcels so that the portion of map data contained in the parcel is close to a predetermined parcel size. The method subdivides the map data less the map data representing the dense area into parcels so that the portion of map data contained in the parcel is close to the predetermined parcel size. Additionally, the method locates the map data in each parcel together on the physical storage medium.

Claims

1. A method of organizing map data on a physical storage medium, wherein the map data represent geographic features located in a geographic region, the method comprising:

identifying at least one dense area in the geographic region, the map data representing the geographic features within said dense area having a data size exceeding a predetermined maximum size for a predetermined sized geographic area of the region;

subdividing the map data representing the geographic features within the dense area into parcels so that the portion of map data contained in each parcel is close to a predetermined parcel size;

subdividing the map data less the map data representing the dense area into parcels so that the portion of map data contained in each parcel is close to the predetermined parcel size; and

locating the map data in each parcel together on the physical storage medium.

2. The method of claim 1 wherein the dense area is a metropolitan area.

3. The method of claim 1 wherein the portion of map data contained in each parcel exceeds a predetermined minimum parcel size and is less than a predetermined maximum parcel size.

4. The method of claim 1 wherein the parcels have a rectangular shape.

5. The method of claim 4 wherein each parcel has an aspect ratio less than a predetermined maximum value.

6. The method of claim 1 wherein the dense area is located within a geographic area encompassed by one of the parcels and the map data representing the geographic features within the dense area are excluded from the portion of map data contained in said parcel.

7. The method of claim 1 further including organizing the map data representing the region into a grid of tiles, each of the tiles encompassing a geographic area defined by grid boundary lines.

8. The method of claim 7 wherein the subdividing the map data less the dense area into parcels is performed along the grid boundary lines.

9. The method of claim 7 wherein the tiles have a fixed size.

10. The method of claim 1 wherein said step of identify the dense areas comprises:

organizing the map data into a grid of tiles;

for each tile, calculating a metric value estimating an amount of map data within the tile; and

identifying each tile having the metric value greater than a maximum metric value as said dense area.

11. The method of claim 1 wherein the step of subdividing the dense areas into parcels comprises organizing the map data representing the geographic features within the dense areas into a grid of subtiles, each of the subtiles encompassing a geographic area defined by grid boundary lines, wherein the subdividing the dense areas into parcels is performed along the grid boundary lines.

12. The method of claim 1 wherein the step of subdividing the dense areas into parcels comprises the steps of:

organizing the map data representing the geographic features within the dense area into a plurality of separate rows, wherein each row has a size that corresponds to a multiple of a first dimension in a first coordinate direction and that extends across the region of the dense area in an perpendicular coordinate direction; and

separating the map data contained in each row into separate parcels.

13. The method of claim 12 wherein the first dimension corresponds to a maximum change of coordinate direction that can be displayed on a display screen of a navigation system.

14. The method of claim 1 wherein the physical storage medium is a CD-ROM disk.

15. The method of claim 1 wherein the physical storage medium is a DVD-ROM disk.

16. The method of claim 1 wherein the physical storage medium is a hard disk.

17. A map database product formed according to the method of claim 1.

18. A navigation system having map data organized according to the method of claim 1.

19. A method of storing map data on a physical storage medium, the map data represent geographic features located in a region, the method comprising:

organizing the map data into a grid of tiles;

for each tile, calculating a metric value estimating an amount of data contained within the tile;

identifying at least one dense tile having a metric value exceeding a predetermining maximum metric value;

forming a plurality of small area parcels from the map data contained within the dense tile, the portion of map data contained in the small area parcel is approximately equal to a predetermined parcel size; and

forming a plurality of large area parcels from the map data less the map data contained within the dense tiles, the portion of map data contained in the large area parcel is approximately equal to the predetermined parcel size.

20. The method of claim 19 wherein the tiles have a rectangular shape.

21. The method of claim 19 wherein the tiles have a fixed size.

22. The method of claim 19 wherein the large area parcels comprise at least one tile.

23. The method of claim 19 wherein the large area parcels comprise a rectangular grouping of the tiles.

24. The method of claim 19 wherein the dense tile is located within a geographic area encompassed by one of the large area parcels and the map data contained within the dense tile is excluded from the portion of map data contained in said large area parcel.

25. The method of claim 19 wherein the step of forming the small area parcels comprises organizing the map data of the dense tile into a grid of subtiles, each of the subtiles encompassing a geographic area defined by subtile grid boundary lines, wherein the subdividing the dense tile into parcels is performed along the subtile grid boundary lines.

26. The method of claim 25 wherein the small area parcels comprise a rectangular grouping of the subtiles.

27. The method of claim 19 wherein the step of forming the small area parcels comprises the steps of:

organizing the map data within the dense tile into a plurality of separate rows, wherein each row has a size that corresponds to a multiple of a first dimension in a first coordinate direction and that extends across the region of the dense tile in an perpendicular coordinate direction; and

separating the map data contained in each row into separate small area parcels.