Methods and systems for encoding the maximum resolution data level for a quadtree

摘要

A method and system for searching for data covered by nodes in a quadtree are disclosed. Nodes at a selected level of the quadtree are encoded with an index. The index nodes store data related to the level of descendants and ancestors of each index node. To search for data covered by a particular desired node, the index node ancestor or descendant of the desired node is determined. Based on the data in the index node, the desired node can be located without a full traversal of the quadtree. The quadtree nodes store elevation data for points on the Earth.

主权项

1. A computer implemented method of determining the elevation of a point, where the elevation of a first area containing the point is stored in a database in the form of an indexed quadtree, the method comprising:
determining from the database, using a computer processor, an index node that is an ancestor of a node containing the elevation of the first area at a maximum resolution available for the first area within the indexed quadtree; determining from the database, using a computer processor, a level of the node containing the elevation of the first area at the maximum resolution available for the first area based on data that is contained in the index node, wherein
(i) the data contained in the index node includes an index having at least E elements, E being greater than a total number of child nodes stemming directly from the index node,(ii) each of the E elements specifies a level of the indexed quadtree at which elevation information for a respective area is stored at a maximum resolution available for the respective area within the indexed quadtree, and(iii) one of the E elements specifies the level of the node containing the elevation of the first area at the maximum resolution; locating within the database, using a computer processor, the node containing the elevation of the first area at the maximum resolution based on the determined level of the node; interpolating the elevation of the point based on the elevation of the first area at the maximum resolution available for the first area contained in the located node; and providing the interpolated elevation of the point, or another elevation calculated based on the interpolated elevation of the point, for presentation to a user.