计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (13): 59-62.

• 理论研究、研发设计 • 上一篇    下一篇

Hadoop下面元加权Voronoi图并行算法及应用

徐  明,曹  菡,唐多余   

  1. 陕西师范大学 计算机科学学院,西安 710119
  • 出版日期:2015-07-01 发布日期:2015-06-30

Generation and application of weighted Voronoi diagrams for polygons based on Hadoop

XU Ming, CAO Han, TANG Duoyu   

  1. School of Computer Science, Shaanxi Normal University, Xi’an 710119, China
  • Online:2015-07-01 Published:2015-06-30

摘要: 面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。

关键词: Voronoi图, Hadoop云平台, 面元加权Voronoi图, 城市绿地设计

Abstract: Weighted Voronoi diagram for polygons generalizes the generator points to polygons based on weighted Voronoi diagram. Since it is computation redundancy and low efficiency for large scale of data, this paper presents a parallel algorithm of weighted Voronoi diagrams for polygons, which is improved with extracting boundary points and realized on Hadoop platform. The experiment results show that the algorithm can be used to deal with large scale raster data to significantly improve the speed. It can also be applied in the urban green-belt planning of Xi’an city to provide decision-making basis for green space design.

Key words: Voronoi Diagrams(VD), Hadoop platform, weighted Voronoi diagrams for polygons, urban green-belt design