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

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

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

徐明，曹菡，唐多余

陕西师范大学计算机科学学院，西安 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

School of Computer Science, Shaanxi Normal University, Xi’an 710119, China

Online:2015-07-01 Published:2015-06-30

摘要/Abstract

摘要： 面元加权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

徐明，曹菡，唐多余. Hadoop下面元加权Voronoi图并行算法及应用[J]. 计算机工程与应用, 2015, 51(13): 59-62.

XU Ming, CAO Han, TANG Duoyu. Generation and application of weighted Voronoi diagrams for polygons based on Hadoop[J]. Computer Engineering and Applications, 2015, 51(13): 59-62.

[1]	季长清1，2，肖鹏3，刘畅4，汪祖民2，西方2，邵寅博1，李泽宇2. 基于空间近邻查询的移动医疗呼叫算法[J]. 计算机工程与应用, 2019, 55(2): 206-212.
[2]	薛佳楣，张磊，玄子玉. Voronoi图划分实现位置数据发布隐私保护[J]. 计算机工程与应用, 2019, 55(10): 121-126.
[3]	朱杰1，鲁艺2，张辉明1. 突发威胁情况下的无人机航迹重规划[J]. 计算机工程与应用, 2018, 54(8): 255-259.
[4]	党小超1，2，马如仓1，郝占军1，2. 基于Voronoi的无线传感器网络栅栏覆盖策略[J]. 计算机工程与应用, 2018, 54(2): 91-96.
[5]	周屹1，杨泽雪1，2. 空间数据库中的线段k近邻查询研究[J]. 计算机工程与应用, 2015, 51(18): 131-134.
[6]	张丽平1，李松1，郝晓红2，郝忠孝1. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.
[7]	余婧，曹菡，靳朋飞. Voronoi图k阶邻近并行矩阵迭代算法[J]. 计算机工程与应用, 2014, 50(6): 102-105.
[8]	滑斌杰，林立忠，柴忠良. 粗糙域Voronoi图离散生成算法研究[J]. 计算机工程与应用, 2013, 49(23): 191-194.
[9]	吴博1，2，文元桥1，2，肖长诗1，2. 一种内河海事无人艇路径规划算法设计与仿真[J]. 计算机工程与应用, 2013, 49(14): 241-246.
[10]	张仪彬1，吴刚1，彭雯秀2，陈彦如3. 不同交通网络速度的Voronoi图的结晶生成[J]. 计算机工程与应用, 2012, 48(36): 181-185.
[11]	张丽平，李松，郝忠孝. 球面上的最近邻查询方法研究[J]. 计算机工程与应用, 2011, 47(5): 126-129.
[12]	冯洪奎¹，鲍劲松^1，2，金烨^1，2. 广义Voronoi图求解多机器人运动规划[J]. 计算机工程与应用, 2010, 46(22): 1-3.
[13]	兰连意¹，张有会²，杨玉平³. 一般城市Voronoi图的结晶生成[J]. 计算机工程与应用, 2010, 46(10): 216-219.
[14]	康乐. 无人机三维航迹规划方法研究[J]. 计算机工程与应用, 2009, 45(33): 236-239.
[15]	张丽平¹，李松²，刘文强³，王红¹. 强邻近对查询的新方法[J]. 计算机工程与应用, 2009, 45(27): 123-126.