Compactly storing geodetic points

Abstract

Mechanisms are provided for the compact storage of geographical geometries as a collection of points, where individual points are encoded as binary/ternary strings (with the property that points closer to each other share a longer binary/ternary prefix) and the geometry is encoded by compressing the binary/ternary representation of common-prefix points. Mechanisms are also provided for the representation of a geometry using a ternary string that allows efficient storage of arbitrary shapes (e.g., long line segments, oblong polygons) as opposed to binary representations that are more efficient when the geometries are square or nearly square shaped.

What is claimed is: 
     
         1 . A method for storing a geometry represented by a plurality of geodetic points, the method comprising:
 assigning by a processor, to each of the points, a respective string, wherein each string has characters that are selected from the group of binary characters and ternary characters, and wherein each string has a prefix portion and a non-prefix portion;   reducing, by the processor, an amount of storage required to store the assigned strings, wherein the reducing comprises applying compression to the strings that exploits at least one common prefix that is shared by at least a first one of the strings and second one of the strings; and   storing, by the processor, the compressed strings.   
     
     
         2 . The method of  claim 1 , wherein all of the characters of each string are binary characters. 
     
     
         3 . The method of  claim 1 , wherein all of the characters of each string are ternary characters. 
     
     
         4 . The method of  claim 1 , wherein at least one of the strings has at least one binary character and at least one ternary character. 
     
     
         5 . The method of  claim 1 , wherein a length of the strings varies based upon an amount of precision to be provided by the strings. 
     
     
         6 . The method of  claim 1 , wherein each string comprises latitude information and longitude information. 
     
     
         7 . The method of  claim 1 , wherein the compression comprises one of: (a) LZW encoding; and (b) Huffman Coding.