基于投影的球面退化四叉树格网路径搜索算法及其效率测试

An algorithm of searching degenerate quadtree grid cells along a path

为了克服现有的全球离散格网邻近搜索算法只能搜索格网单元周围邻近单元而无法按照指定路径方向进行搜索的局限,提出了一种基于投影的球面退化四叉树格网的路径搜索算法.该算法是从起始格网单元开始,根据球心中心投影法、空间有向线段方向法及格网邻近搜索算法搜索在指定路径上的格网单元,直到搜索到目的格网单元.最后,对该算法进行了验证和效率测试.试验结果表明,该算法能准确搜索出指定路径所经过的格网,且搜索速率基本稳定在60 000/s多个格网,该算法是可行的,效率是可以接受的.

Nowadays,most-grid-cell searching algorithms are limited to finding neighbor cells only,cannot search cells along a path.In order to overcome this deficiency,an algorithm of searching spherical Degenerate Quadtree Grid cells along a path is presented in this paper in details.The principle of this algorithm is searching grid cells along a path according to gnomonic projection,the direction of two intersecting directed line segments and cell adjacent searching algorithm.In the end,an experiment has been done.The experiment results illustrate that the searching results of this algorithm matching well with the path,and the searching rate basically stable at 60,000 cells per second,the efficiency is comparative to that of adjacent searching.It could be used in global scale data operations.