引用本文: 赵龙飞, 赵学胜, 朱思坤, 付瑞全. 一种球面退化四叉树格网的多层次邻近搜索算法[J]. 武汉大学学报 ( 信息科学版), 2018, 43(4): 529-535.
ZHAO Longfei, ZHAO Xuesheng, ZHU Sikun, FU Ruiquan. A Multi-level Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 529-535.
 Citation: ZHAO Longfei, ZHAO Xuesheng, ZHU Sikun, FU Ruiquan. A Multi-level Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 529-535.

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

• 摘要: 格网单元的邻近搜索是聚类、索引、查询等空间操作的基础，但现有方法大都局限于单个剖分层次，无法直接满足全球多尺度数据集成查询和操作的应用需求。在球面退化四叉树格网（DQG）模型基础上，提出了一种基于多层次格网的邻近搜索算法。首先采用视点相关技术建立DQG格网的多层次模型，然后引入细分评价函数确定格网单元的邻近单元层次，设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法，最后与单层次邻近搜索算法进行了对比实验。结果表明，搜索同一区域，该算法的耗时成本约为DQG单层次搜索算法的1/3（层次为11）；将该算法用于全球地形实时可视化表达，平均刷新帧率达到60帧/s。

Abstract: 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.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈