| 一种球面退化四叉树格网的多层次邻近搜索算法 |
| |
| 引用本文： | 赵龙飞,赵学胜,朱思坤,付瑞全.一种球面退化四叉树格网的多层次邻近搜索算法[J].武汉大学学报(信息科学版),2018,43(4):529-535. |
| |
| 作者姓名： | 赵龙飞 赵学胜 朱思坤 付瑞全 |
| |
| 作者单位： | 1.中国矿业大学(北京)地球科学与测绘工程学院, 北京, 100083 |
| |
| 基金项目： | 国家自然科学基金41171306国家自然科学基金41171304 |
| |
| 摘 要： | 格网单元的邻近搜索是聚类、索引、查询等空间操作的基础，但现有方法大都局限于单个剖分层次，无法直接满足全球多尺度数据集成查询和操作的应用需求。在球面退化四叉树格网（DQG）模型基础上，提出了一种基于多层次格网的邻近搜索算法。首先采用视点相关技术建立DQG格网的多层次模型，然后引入细分评价函数确定格网单元的邻近单元层次，设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法，最后与单层次邻近搜索算法进行了对比实验。结果表明，搜索同一区域，该算法的耗时成本约为DQG单层次搜索算法的1/3（层次为11）；将该算法用于全球地形实时可视化表达，平均刷新帧率达到60帧/s。
|
| 关 键 词： | 全球离散格网 DQG 多层次邻近搜索 地址码 地形可视化 |
| 收稿时间： | 2015-12-15 |
A Multi-level Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet |
| |
| Affiliation: | 1.College of Geoscience & Surveying Engineering, China University of Mining & Technology(Beijing), Beijing 100083, China2.National Marine Data and Information Service, Tianjin 300171, China |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《武汉大学学报(信息科学版)》浏览原始摘要信息 |
|
点击此处可从《武汉大学学报(信息科学版)》下载全文 |
|
