球面退化四叉树格网单元的邻近搜索算法  

An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet

作　　者：赵学胜[1] 崔马军[1] 李昂[1] 张美娟[1] 

机构地区：[1]中国矿业大学(北京)测绘与土地科学系,北京市学院路丁11号100083

出　　处：《武汉大学学报（信息科学版）》2009年第4期479-482,共4页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金资助项目(40471108;40771169)

摘　　要：为了克服传统经纬度格网与全球四元三角网(quaternary triangular mesh,QTM)存在的不足,提出了一种球面退化四叉树格网(degenerate quadtree grid,DQG)的剖分方法及相应的格网编码方案,分析了不同位置格网的邻近特征,给出了一套详细的DQG单元邻近搜索算法,并进行了相关实验与对比分析。结果表明,该算法的搜索速度比传统QTM格网的Bartholdi搜索算法和分解搜索算法分别提高了约100倍和30倍。Adjacent search is the basis of spatial operations, such as spatial aggregation, index, query, and dynamic dilatation, and has become one of the key problems in the global discrete grids researches. In order to overcome some deficiencies in adjacent search based on the traditional latitude/longitude grid or quaternary triangular mesh （QTMs）, a new partition method, called degenerate quadtree grid, and the corresponding grid code scheme are presented in this paper. Firstly, the adjacent characteristics of DQGs in different positions are analyzed. Then, an adjacent searching algorithm of DQGs is given in details. Finally, the experimental analysis is developed and the results demonstrate that the efficiency of adjacent search in this algorithm has been improved by 100 times and 30 times respectively relative to those of traditional Bartholdi algorithm and decomposing algorithm.

关 键 词：全球离散格网 DQG 邻近搜索 地址码 

分 类 号：P208[天文地球—地图制图学与地理信息工程]