Compactly storing geodetic points

摘要

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.

主权项

1. A computer readable storage device, tangibly embodying a program of instructions executable by the computer for storing a geometry represented by a plurality of geodetic points, the program of instructions, when executing, performing the following steps:
assigning, to each of the plurality of points of the geometry, 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 an amount of storage required to store the assigned strings associated with the geometry, wherein the reducing comprises applying compression to the strings associated with the geometry that exploits at least one common prefix that is shared by at least a first one of the strings associated with the geometry and a second one of the strings associated with the geometry; and storing the compressed strings associated with the geometry; wherein the geometry comprises at least one of a line segment and a polygon; wherein a length of the strings varies based upon an amount of geographic precision to be provided by the strings; and wherein a length of bit representation in the strings of latitude differs from a length of bit representation in the strings of longitude.