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  of 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 associated with at least one packet, wherein calculating the packet name is based at least partly on the data level;  
 displaying the map; and  
 caching the 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 ,  A method of displaying a map, the method comprising:
   obtaining information relating to a location;    
   calculating at least one packet name;    
   determining a data level;    
   displaying the map;    
   caching at least one packet until an amount of computer storage space is filled; and    
   determining which packets should be replaced,   
 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 ,  A method of displaying a map, the method comprising:
   obtaining information relating to a location;    
   calculating at least one packet name;    
   determining a data level;    
   displaying the map;    
   caching at least one packet until an amount of computer storage space is filled; and    
   determining which packets should be replaced,   
 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  An apparatus 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 of digital map compression, comprising:
   representing each data point of a digital map as a set of geographic coordinates comprising a tuple of an offset and a value, wherein the offset represents a corner of a given rectangle;        segmenting the digital map; and        reducing the number of data points in each segment of the digital map including calculating a new offset and value according to predefined minimum and maximum corners of a data segment.     
     
     
       24. The method of  claim 23 , wherein the offsets are represented as two byte integers. 
     
     
       25. A system for digital map compression, comprising:
   means for representing each data point of a digital map as a set of geodetic coordinates comprising a tuple of an offset and a value, wherein the offset represents a corner of a given rectangle;        means for segmenting the digital map; and        means for reducing the number of data points in each segment of the digital map including calculating a new offset and value according to predefined minimum and maximum corners of a data segment.     
     
     
       26. The system of  claim 25 , wherein the offsets are represented as two byte integers. 
     
     
       27. A system for digital map compression, comprising:
   a database configured to represent each data point of a digital map as a set of geodetic coordinates comprising a tuple of an offset and a value, wherein the offset represents a corner of a given rectangle;        a data segmentation module configured to segment the digital map; and        a data reduction module configured to reduce the number of data points in each segment of the digital map including calculating a new offset and value according to predefined minimum and maximum corners of a data segment.     
     
     
       28. The system of  claim 27 , wherein the offsets are represented as two byte integers. 
     
     
       29. A method of reducing data defining a map, the method comprising:
   selecting a point from a plurality of points defining a portion of the map;        determining a first line from the point to a first adjacent point of the plurality of points;        determining a second line from the point to a second adjacent point of the plurality of points such that the first and second lines intersect at the point;        eliminating the point in dependence on whether an angle formed between the first and second lines at the point exceeds a threshold angle.     
     
     
       30. The method of  claim 29 , wherein selecting a point comprises selecting every other adjacent point of the plurality of points. 
     
     
       31. A method of reducing data defining a map, the method comprising:
   transforming each of a plurality of points defining a portion of the map into a plurality of offsets from a selected point, wherein the portion of the map and the selected point are selected such that at least one dimension of each of the plurality of offsets is less than a predetermined value, wherein the predetermined value is selected so that each of the plurality of offsets is representable by less data than each of the corresponding points.     
     
     
       32. The method of  claim 31 , wherein the selected point is associated with an identifier of the portion. 
     
     
       33. The method of  claim 31 , wherein the portion defines a region bounded by a shape and where the first point is associated with a point of the shape. 
     
     
       34. The method of  claim 33 , wherein the selected point is associated with a predetermined corner of the shape. 
     
     
       35. The method of  claim 32 , wherein the selected point is encoded in a name of a data structure associated with the portion of the map. 
     
     
       36. The method of  claim 36 , wherein the data structure comprises a file. 
     
     
       37. The method of  claim 31 , wherein the predetermined value is less than 65536. 
     
     
       38. The method of  claim 31 , wherein the predetermined value is selected so that each of the plurality of offsets is representable as a  16  bit value. 
     
     
       39. A method of providing a map, the method comprising:
   receiving a request for information relating to a location;        determining a data level of the information;        identifying a data segment associated with the location and the data level, the data segment comprising geographic coordinates that are indicative of offsets from a coordinate; and        determining at least one identifier for a data segment indicative of the coordinate of the data segment; and        displaying the data segment based on the coordinate.     
     
     
       40. The method of  claim 39 , further comprising:
   caching the data segment based at least partly on the identifier.     
     
     
       41. The method of  claim 39 , wherein calculating the at least one identifier is based at least partly on the data level. 
     
     
       42. The method of  claim 39 , wherein the data segment is indicative of map data in a region and wherein the coordinate comprises a predetermined location in the region. 
     
     
       43. The method of  claim 39 , wherein the data segment is indicative of map data in a rectangular region and wherein the coordinate comprises at least one of an upper right, upper left, lower right, or lower left corner of the rectangular region. 
     
     
       44. The method of  claim 39 , wherein displaying the data segment based on the coordinate comprises offsetting geographic coordinates of the data segment from the coordinate.