An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet

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.