一种基于点集自适应分组构建Voronoi图的并行算法

作     者：王结臣 蒲英霞 崔璨 陈刚 马劲松 Wang Jiechen;Pu Yingxia;Cui Can;Chen Gang;Ma Jinsong

作者机构：江苏省地理信息技术重点实验室江苏南京210093 南京大学地理信息科学系江苏南京210093 

出 版 物：《图学学报》 (Journal of Graphics)

年 卷 期：2012年第33卷第6期

页      面：7-13页

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家科技支撑计划资助项目(2012BAH28B02) 

主　　题：Voronoi图 并行算法 自适应分组 计算几何 

摘      要：论文提出一种基于点集自适应分组构建Voronoi图的并行算法,其基本思路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成Voronoi图,称为Voronoi子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi图,称为边界点Voronoi图;最后,针对每个边界点,提取其位于Voronoi子图和边界点Voronoi图内所对应的两个多边形,进行Voronoi多边形的合并,最终实现子网的合并。考虑到算法耗时主要在分组点集的Voronoi图生成,而各分组的算法实现不受其他分组影响,采用并行计算技术加速分组点集的Voronoi图生成。理论分析和测试表明,该算法是一个效率较高的Voronoi图生成并行算法。