A Multi-level Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet

The model of Global Discrete Grid is the base of Digital Earth and Spatial Information Grid. Adjacent search of grid cell is the basis of spatial operations, such as aggregation, index, and query, and has become one of the key problems in the global discrete grids researches. However, most existing methods are limited to single-level, cannot directly meet the application requirements of the global multi-scale data integration query and operation. A multi-level adjacent searching algorithm is proposed based on spherical DQG(degenerate quadtree grid) model in this paper. Firstly, the partition principle and encoding rules of the degenerate quadtree grid on sphere were analyzed, the multi-level DQG-based grid model is established by using view-dependent technique. Then, the segmentation evaluation function is introduced to determine the adjacent cell level of grid unit. A dynamic and multi-level adjacent searching algorithm is designed and implemented as level difference between adjacent grids is not more than 1. Finally, the contrast experiment with the single-level algorithm and the multi-level algorithm is done. The results show that the time consume of this algorithm is only about 1/3 to that of the DQG-based single-level algorithm (level 11) when searching for the same area, and the average frame refresh rate reaches 60 frames/s when this algorithm is used to real-time visualization of the global terrain. The new method not only eliminates the grids cracks between the same level or the different levels completely, but avoids the phenomenons of T connection and steep as well. In the end, the conclusions and future works are presented.