Method for organizing and compressing spatial data

Abstract

A method for organizing and compressing spatial data to enable fast, incremental downloads of spatial data over a network. The method comprises multiple steps for segmenting and reducing spatial data, and introduces a location-relevant naming system for storing and accessing the data. Applications installed on remote devices are able to efficiently compute data file names based solely on location information, download the data over a network and cache the data on the device.

1. A method for organizing spatial data comprising the steps of:
 a) parsing the spatial data into a plurality of packets;   b) segmenting the packets;   c) reducing a size of the packets by eliminating at least one data point from at least one display element by applying an angle comparison between an adjacent display element, wherein the at least one data point is eliminated if an angle between the at least one display element and the adjacent display element is about 180°; and   d) generating a name for each of the packets.   
     
     
       2. The method of  claim 1 , wherein the spatial data comprises topographic information comprising a plurality of elements containing geodetic coordinates. 
     
     
       3. The method of  claim 1 , wherein the step of parsing the spatial data comprises:
 selecting at least one entity within the data, the entity selected from a group consisting of: a road, a railway, an airport, a river, a lake, a shore line, a park, an entity comprising a geometric shape, and an entity comprising a substantially rectangular shape.   
     
     
       4. The method of  claim 1 , wherein the step of parsing the spatial data comprises:
 generating a substantially rectangular element comprising about 1° longitude and about ½° latitude.   
     
     
       5. The method of  claim 1 , wherein the step of parsing the spatial data comprises: separating a topographic element from an attribute element;
 wherein the topographic element comprises elements expressed using a geodetic coordinate system; and   the attribute element is related to the topographic element.   
     
     
       6. The method of  claim 1 , wherein the step of segmenting the packets comprises:
 dividing the packets into at least one element, the element selected from a group consisting of: an 8×8 grid, a 64×64 grid, a substantially rectangular grid comprising about 1° longitude and about ½° latitude, and a substantially rectangular grid comprising about ⅛° longitude and about 1/16° latitude.   
     
     
       7. The method of  claim 1 , wherein the step of reducing the size of the segmented packets comprises:
 eliminating elements selected from a group consisting of: a polygon, a lake, a geographic area, a topographic element and an attribute element.   
     
     
       8. The method of  claim 1 , wherein the step of reducing the size of the segmented packets comprises:
 eliminating a plurality of data points from a topographic element.   
     
     
       9. The method of  claim 1 , wherein the step of reducing the size of the segmented packets comprises:
 transforming a geodetic coordinate from a real number to an integer number, wherein the integer number ranges from about 0 to about 65535.   
     
     
       10. The method of  claim 1 , wherein the step of reducing the size of the segmented packets comprises:
 eliminating a plurality of data points from at least one topographic element by applying an angle comparison between an adjacent topographic element line, wherein at least one data point is eliminated if an angle between the at least one topographic element and the adjacent topographic element line is about 180°.   
     
     
       11. The method of  claim 1 , wherein the step of generating the name for each of the packets comprises the step of generating a location-relevant naming system. 
     
     
       12. The method of  claim 1 , wherein the step of generating the name for each of the packets comprises the step of generating a location-relevant naming system, wherein the packet name comprises location information representing an offset from an earth origin. 
     
     
       13. The method of  claim 12 , wherein the earth origin is selected from a group consisting of: a North Pole, and a location other than the North Pole. 
     
     
       14. The method of  claim 1 , further including the step of: repeating any one of steps a, b, c and d to process an entire spatial database. 
     
     
       15. A method for displaying a map, the method comprising the steps of:
 obtaining information relating to a location;   calculating at least one packet name;   determining a data level;   displaying the map; and   caching at least one packet until an amount of computer storage space is filled, and   determining which packets should be replaced.   
     
     
       16. The method of  claim 15 , wherein the step of calculating the at least one packet name comprises:
 computing the at least one data packet name using a geodetic coordinate.   
     
     
       17. The method of  claim 15 , wherein the step of calculating the at least one packet name comprises:
 calculating a request location; and   using the request location to calculate the at least one packet name.   
     
     
       18. The method of  claim 15 , wherein the step of calculating the at least one packet name comprises:
 computing four adjacent data packet names;   fetching the packets from a server; and   combining an information contained in the packets to generate a map.   
     
     
       19. The method of  claim 15 , wherein the step of determining the data level comprises:
 determining a resolution level selected from a group consisting of: an address, a city, a zip code and a building floor plan.   
     
     
       20. The method of  claim 15 , further including the step of:
 caching at least one data packet until an amount of computer storage space is filled, and   determining which packets should be replaced.   
     
     
       21. The method of  claim 15 , further including the step of:
 checking a local cache before requesting a data packet from a remote device.   
     
     
       22. A method for organizing spatial data comprising the steps of:
 a) means for parsing the spatial data into a plurality of packets;   b) means for segmenting the packets;   c) means for reducing a size of the packets by eliminating at least one data point from at least one display element by applying an angle comparison between an adjacent display element, wherein the at least one data point is eliminated if an angle between the at least one display element and the adjacent display element is about 180°; and   d) means for generating a name for each of the packets.   
     
     
       23. A method to reduce data in a digital map, comprising:
 suppressing selected geographic features; and   reducing resolution of remaining geographic features,   wherein the reducing comprises eliminating data points, provided that an angle between two lines connecting a data point to its adjacent data points does not exceed a predetermined angle.   
     
     
       24. The method of claim 23, wherein the selected geographic features include secondary roads. 
     
     
       25. The method of claim 23, wherein the remaining geographic features include primary roads. 
     
     
       26. The method of claim 23, wherein the elimination of data points does not significantly change the overall shape of a remaining geographic feature. 
     
     
       27. A system for reducing data in a digital map, comprising:
 means for suppressing selected geographic features; and   means for reducing resolution of remaining geographic features, wherein the reducing comprises eliminating data points, provided that an angle between two lines connecting a data point to its adjacent data points does not exceed a predetermined angle.   
     
     
       28. The system of claim 27, wherein the selected geographic features include secondary roads. 
     
     
       29. The system of claim 27, wherein the remaining geographic features include primary roads. 
     
     
       30. The system of claim 27, wherein the elimination of data points does not significantly change the overall shape of a remaining geographic feature. 
     
     
       31. A non-transitory computer readable storage medium having stored thereon instructions that when executed by a computer processor perform a method of reducing data in a digital map, the method comprising:
 suppressing selected geographic features; and   reducing resolution of remaining geographic features, wherein the reducing comprises eliminating a data points, provided that an angle between two lines connecting the data point to its adjacent data points does not exceed a predetermined angle.   
     
     
       32. The non-transitory computer readable storage medium of claim 31, wherein the selected geographic features include secondary roads. 
     
     
       33. The non-transitory computer readable storage medium of claim 31, wherein the remaining geographic features include primary roads. 
     
     
       34. The non-transitory computer readable storage medium of claim 31, wherein the elimination of the data points does not significantly change the overall shape of the remaining geographic features. 
     
     
       35. The method of claim 23, wherein the predetermined angle is greater than 180 degrees. 
     
     
       36. The system of claim 27, wherein the predetermined angle is greater than 180 degrees. 
     
     
       37. The non-transitory computer readable storage medium of claim 31, wherein the predetermined angle is greater than 180 degrees. 
     
     
       38. A method for reducing data in a digital map, the method comprising:
 suppressing selected geographic features; and   reducing resolution of remaining geographic features by eliminating at least one data point between two adjacent data points only if an angle formed between a first line and a second line does not exceed a predetermined angle, the first line extending through the at least one data point and one adjacent data point of the adjacent data points and the second line extending through the at least one data point and another adjacent data point of the adjacent data points.   
     
     
       39. The method of claim 38, wherein the reducing comprises eliminating a plurality of selected data points where, for each of the plurality of selected data points, an angle between a first line extending through the selected data point and a first adjacent data point and a second line extending through the selected data point and a second adjacent data point does not exceed the predetermined angle. 
     
     
       40. The method of claim 39, wherein the selected geographic features include secondary roads. 
     
     
       41. The method of claim 39, wherein the remaining geographic features include primary roads. 
     
     
       42. The method of claim 39, wherein the elimination of the at least one data point does not significantly change the overall shape of the remaining geographic features. 
     
     
       43. A system for reducing data in a digital map, the system comprising:
 means for suppressing selected geographic features; and   means for reducing resolution of remaining geographic features by eliminating at least one data point between two adjacent data points only if an angle formed between a first line and a second line does not exceed a predetermined angle, the first line extending through the at least one data point and one of the adjacent data points and the second line extending through the at least one data point and another adjacent data point.   
     
     
       44. The system of claim 43, wherein the means for reducing comprises means for eliminating a plurality of selected data points where, for each of the plurality of selected data points, an angle between a first line extending through the selected data point and a first adjacent data point and a second line extending through the selected data point and a second adjacent data point does not exceed the predetermined angle. 
     
     
       45. The system of claim 43, wherein the selected geographic features include secondary roads. 
     
     
       46. The system of claim 43, wherein the remaining geographic features include primary roads. 
     
     
       47. The system of claim 43, wherein the elimination of the at least on data point does not significantly change the overall shape of a remaining geographic feature. 
     
     
       48. A non-transitory computer readable storage medium that stores instructions that, when executed by a machine, cause the machine to reduce data in a digital map, the instructions causing the machine to perform steps comprising:
 suppressing selected geographic features; and   reducing resolution of remaining geographic features by eliminating at least one data point between two adjacent data points only if an angle formed between a first line and a second line does not exceed a predetermined angle, the first line extending through the at least one data point and one of the adjacent data points and the second line extending through the at least one data point and another adjacent data point.   
     
     
       49. The non-transitory computer readable storage medium of claim 48, wherein the reducing comprises eliminating a plurality of selected data points where, for each of the plurality of selected data points, an angle between a first line extending through the selected data point and a first adjacent data point and a second line extending through the selected data point and a second adjacent data point does not exceed the predetermined angle. 
     
     
       50. The non-transitory computer readable storage medium of claim 48, wherein the selected geographic features include secondary roads. 
     
     
       51. The non-transitory computer readable storage medium of claim 48, wherein the remaining geographic features include primary roads. 
     
     
       52. The non-transitory computer readable storage medium of claim 48, wherein the elimination of the at least one data point does not significantly change the overall shape of the remaining geographic features.