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 an 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 area; determining from the database, using a computer processor, a level of the node containing the elevation of the area based on data contained in the index node; locating within the database, using a computer processor, the node containing the elevation of the area based on the determined level of the node; and interpolating the elevation of the point based on the elevation of the area contained in the located node.