基于多层次QTM的球面Voronoi图生成算法

摘要：

随着格网层次的增大,基于全球离散格网的球面Voronoi图生成算法的格网数据量与Voronoi图生成时间都呈指数增长,在高层次时容易出现算法效率较低,甚至内存溢出无法执行等情况.利用球面四元三角格网的层次性,提出了一个基于多层次QTM的球面Voronoi图生成算法.首先用全球低层次QTM格网生成Voronoi图,然后对Voronoi边界格网进行再次剖分,得到下一层次的Voronoi图,重复进行,直至达到目标层次.实验结果表明,相对于单一层次的确定归属算法和扩张算法,该算法能够生成更高层次的Voronoi图,且效率较前两者分别提高了22倍和25倍(第9层).

关键词：球面Voronoi图、全球离散格网、四元三角网、多层次、邻近搜索

所属期刊栏目：40

分类号：P208(一般性问题)

资助基金：The National Natural Science Foundation of China,Nos.41171306,41171304.国家自然科学基金资助项目41171306;41171304.

在线出版日期：2015-10-23（万方平台首次上网日期，不代表论文的发表时间）

页码：1111-1115,1122