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

Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram

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

A spherical Voronoi diagram of point sets,line sets and area sets can be well handled by GDG-based(GDG:Global Discrete Grid)algorithms.However,the grid data volume and the time consumed for generating spherical Voronoi diagrams increases exponentially with the growth of the GDG levels,which leads to lower efficiency at higher levels.To overcome these deficiencies,a multilevel QTM-based(QTM:Quaternary Triangular Mesh)algorithm is proposed.Firstly,a spherical Voronoi diagram is generated in a lower level.Then,the triangles that form the Voronoi boundaries are subdivided to get Voronoi diagrams at higher levels.The results show that a spherical Voronoi diagram of higher levels can be generated by this algorithm more efficently than those single-level algorithms;as it was improved about 22 and 25times at Level 9.