Method for organizing map data

• US 20050027445A1
• Filed: 07/27/2004
• Published: 02/03/2005
• Est. Priority Date: 11/26/2002
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: William G. Mcdonough
• Inventors: McDonough, William G.
• Granted Patent: US 7,058,504 B2
• Time in Patent Office: Days
• 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-28. -28. (canceled)

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

identifying at least one dense area in the geographic region, the data representing the geographic features within said dense area having a data size larger than a predetermined size for a predetermined sized area;

forming at least one small area parcel from the data representing the geographic features within said dense area, and

forming at least one large area parcel from the data representing the geographic features located in the geographic region less the data representing the dense area.

30. The method of claim 29 wherein the dense area is a metropolitan area.

31. The method of claim 29 wherein the dense area has boundaries corresponding to metropolitan area boundaries.

32. The method of claim 29 wherein the dense area has boundaries following a plurality of road segments within the geographic region.

33. The method of claim 29 wherein a portion of map data contained in each small area parcel and in each large area parcel is approximately equal to a predetermined parcel size.

34. The method of claim 29 wherein a portion of map data contained in each small area parcel and in each large area parcel is less than a predetermined parcel size.

35. The method of claim 29 wherein each of the small area parcels and large area parcels has rectangular shaped boundaries.

36. The method of claim 35 wherein each of the small area parcels and large area parcels has an aspect ratio less than a predetermined value.

37. The method of claim 29 wherein said step of identifying the dense area comprising:

organizing the region 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.

38. The method of claim 29 further comprising locating the data in each small area parcel and large area parcel on the physical storage medium.

39. A map database product formed according to the method of claim 29.

40. A navigation system having map data organized according to the method of claim 29.

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

organizing the region into a grid of tiles;

identifying at least one dense tile having an estimated map data size larger than a predetermined size;

forming a plurality of small area parcels from the map data contained within the dense tile; and

forming a plurality of large area parcels from the map data less the map data contained within the dense tiles.

42. The method of claim 41 wherein the tiles have a rectangular shape.

43. The method of claim 41 wherein the tiles have a fixed size.

44. The method of claim 41 wherein the large area parcels comprise at least one tile.

45. The method of claim 41 wherein the large area parcels comprise a rectangular grouping of the tiles.

46. The method of claim 41 wherein a data size of each small area parcel and each large area parcel is approximately equal to a predetermined parcel size.

47. The method of claim 41 wherein a data size of each small area parcel and each large area parcel is less than a predetermined parcel size.

48. A map database comprising:

map data that represent geographic features located in a region;

the map data are organized into a plurality of large area parcels and a plurality of small area parcels;

each of the small area parcels formed from dense areas in the region, the data representing the geographic features within said dense area having a data size larger than a predetermined size for a predetermined sized area;

each of the large area parcels formed from the data representing the geographic features located in the region less the data representing the dense area.