Patent ID: 8856184

Claim:
A computer implemented method for encoding and retrieving maximum resolution data for a geographic location from an existing quadtree used in a geographic information system, where the quadtree comprises one or more levels, nodes and leaves, wherein at least some of the nodes and leaves containing elevation data, comprising: selecting, by one or more processors, a level of the quadtree as an index level; encoding, by one or more processors, each node of the index level with an index, wherein for a particular index level node, the index contains entries defining the level of a node associated with the particular index level node that contains maximum resolution data for a set of leaf descendants associated with the particular index level node; determining, by one or more processors, a maximum resolution level within the quadtree for a geographic location by, searching the index level of the quadtree to find an index level node corresponding to the geographic location, and interpreting the index of the index level node corresponding to the geographic location to determine the maximum resolution level of the quadtree that corresponds to the geographic location, locating, by one or more processors, a particular node at the maximum resolution level of the quadtree that corresponds to the geographic location, wherein the particular node corresponds to the geographic location; and retrieving, by one or more processors, maximum resolution data for the geographic location from the particular node.