Voronoi图栅格算法研究
摘要
Voronoi图是计算几何中的一个重要研究内容,它在气象、地质、地理信息系统、城市规划、分子化学、生态学、图像处理、计算机图形学、虚拟现实、CAD、碰撞检测和机器人路径规划等领域得到广泛应用,也是解决Delaunay三角化、骨架计算、凸包计算以及最小树生成等计算几何问题的有效工具。
因此构建Voronoi图显得尤为重要,Voronoi图的生成方法主要分为矢量生成方法和栅格生成方法两大类。矢量方法的研究较早,方法众多,其中最为典型的方法主要有：增量法、分治法与间接法。矢量方法的优势是生成的Voronoi图精度高；存在的问题为对生长元有要求,只能是点和半线,若是线和面需要将其分解破坏完整性,并且存储结构比较复杂。由于矢量方法存在的问题,人们开始研究栅格生成算法。栅格方法是对生长元没有限制,但生成的Voronoi图精度低、耗时长。栅格方法典型的有两种：基于传统距离变换Voronoi图栅格方法和基于活动像素主动扩张Voronoi图栅格方法。
在实际应用中,通常需要以实际地图数据作为Voronoi图的生长元。地图数据有两大特点：1、数据量大。2、通常包含点、线、面各类目标,及由点、线、面组合而成的复合目标等复杂空间实体,因此用矢量方法难以生成实际地图的Voronoi图。与矢量方法相比,栅格方法能较好地处理复杂空间实体,但要考虑算法效率和精度问题。本文通过调节栅格大小,细分格网保证Voronoi图的精度。同时考虑到地图数据本身的数据量就较大,随着栅格大小逐步细化,数据量会进一步增大,效率会更低。为了提高算法的效率,本文将并行处理技术应用于Voronoi栅格生成算法,提出两种Voronoi图并行栅格生成算法,一种是基于活动像素主动生长的,另一种是基于改进归属法的,同时配合细分格网,可以较好保证生成的Voronoi图的高精度和高效率。
本文所做工作总结如下：
(1)本文首先提出了基于MPI的并行栅格Voronoi图生成算法,以活动像素主动生长做为生成Voronoi图的基础,提出了基于MPI的行式、列式、和棋盘式3种不同数据分割方法的并行Voronoi图栅格生成算法,并对3种不同数据分割方法进行了效率和扩展性分析。通过多组对比实验,表明该并行算法和细分格网结合可以在保证精度的前提下有效地提高算法的效率,但适用于集群机效果不明显。
(2)鉴于集群机的普遍存在,而最初的串行算法适用于集群机效果不好,因此我们对原串行算法实现进行改进,并在该改进算法的基础上提出了新的基于MPI并行算法。通过多组实验对比,表明该并行算法有效的提高了算法的效率并且适用于集群机。又由于现在商品化的集群系统大多是多核处理机集群,混合编程模型更适合,所以又提出了基于MPI+OpenMP的并行算法,大量实验表明混合编程模型在性能上得到了提高。
(3)在王新生提出的一种新型栅格方法的基础上,提出了一种新的判断空白栅格归属的栅格方法——改进归属法,通过大量实验证明：(a)该算法的效率高低不是单纯的由空白栅格个数决定,还需要考虑到空间目标的数量、分布、形状;(b)该算法与传统栅格算法相比性能更高。
(4)在改进归属法的基础上的首先提出了基于MPI的改进归属法的Voronoi图并行栅格生成算法,通过多组实验证明：该并行算法和细分格网结合可以在保证精度的前提下有效地提高算法的效率,并适合于集群机。接着又提出了基于OpenMP+MPI的改进归属法的Voronoi图并行栅格生成算法,通过大量实验对比,表明混合编程模型在性能上得到了提高。
Voronoi diagram is an important research in computational geometry content, in meteorology, geology, geographic information systems, urban planning, chemistry, ecology, image processing, computer graphics, virtual reality, CAD, collision detection and robot path planning and other fields Widely used, but also solve the Delaunay triangulation, skeleton computation, convex hull computation, and computational geometry minimum spanning tree problem of generating such an effective tool.
Therefore, it is particularly important to construct Voronoi diagram, Voronoi diagram generation method consists of raster and vector generation method. Vector Method earlier, many methods, the most typical methods are:incremental method, divided method and indirect method. Vector method has the advantage of the Voronoi diagram generated high precision; a problem as on the growth element is required, only a point and a half lines, if the line and face the need to undermine the integrity of its decomposition, and the storage structure is more complex. The problem with the vector, people began to study the raster generation algorithm. Element grid is no limit on the growth, but the resulting Voronoi diagram low accuracy, time-consuming. There are two typical raster methods:Voronoi diagram based on the traditional distance transform grid method and the expansion initiative based on the active pixel grid method for Voronoi diagram.
In practice, usually the actual map data as the growth Voronoi diagram element. Map data has two main characteristics:1 amount of data.2 usually contains points, lines, types of goals, and from points, lines, a combination of complex spatial entities complex object, it is difficult to generate the actual vector method using the map Voronoi diagram. Compared with vector, raster method can handle complex spatial entities, but to consider the algorithm efficiency and accuracy issues. By adjusting the grid size, grid subdivision to ensure the accuracy of Voronoi diagram. Map data itself, taking into account the amount of data to larger grid size gradually refined with the amount of data will further increase efficiency will be lower. To improve the efficiency of the algorithm, this paper applies parallel processing technology Voronoi grid generation algorithm, Voronoi diagram proposed two parallel grid generation algorithm, an initiative based on the growth of active pixels, and the other is based on the attribution method improved, At the same time with the sub-grid that can better guarantee that the generated Voronoi diagram of high precision and high efficiency. This paper summarized the work done by the following:
(1) This paper proposes a parallel MPI-based raster Voronoi diagram generation algorithm to generate active pixels active growth as the basis of Voronoi diagram is proposed based on MPI's line of type, column type, and the chessboard 3 different methods of data partitioning in parallel Voronoi diagram grid generation algorithm, and 3 different methods of data partitioning efficiency and scalability analysis. Through multiple sets of comparative experiments, show that the parallel algorithm and the combination of sub-grid accuracy can be guaranteed under the premise of effectively improve the efficiency of the algorithm, but the efficiency for the cluster machines is not obvious.
(2) Given the prevalence of the cluster machines, and since the original serial algorithm for cluster machines not good, so we improve the original serial algorithm and improved algorithm based on the proposed new parallel algorithm based on MPI. Through several experiments, it is shown that the parallel algorithm can improve the efficiency of the algorithm and apply the cluster machines. Also, because now most of the commercialization of multi-core processor cluster system clusters, hybrid programming model is more suitable for the model, it is also proposed based on MPI+OpenMP parallel algorithm, a large number of experiments show that the hybrid programming model has been improved in performance.
(3) Presented in Wang Xinsheng a new approach based on the grid, a new blank grid to determine ownership of the raster method-Improved attribution method, by a large number of experiments show that:(a) inefficiency of the algorithm is not Simply the number of decisions by the blank grid, also need to take into account the number of spatial objects, distribution, shape; (b) algorithm has higher performance than the traditional grid method.
(4) First proposed on the basis of MPI-based improved attribution method Voronoi diagram parallel raster algorithm, proved by several experiments:the parallel algorithm and sub-grid that ensure the accuracy can be combined in order to improve the efficiency of the algorithm, and for the cluster machines. Then made on the basis of OpenMP+MPI improved attribution method Voronoi diagram parallel raster algorithm, by comparing a large number of experiments, show that the hybrid programming model has been improved in performance.
因此构建Voronoi图显得尤为重要,Voronoi图的生成方法主要分为矢量生成方法和栅格生成方法两大类。矢量方法的研究较早,方法众多,其中最为典型的方法主要有：增量法、分治法与间接法。矢量方法的优势是生成的Voronoi图精度高；存在的问题为对生长元有要求,只能是点和半线,若是线和面需要将其分解破坏完整性,并且存储结构比较复杂。由于矢量方法存在的问题,人们开始研究栅格生成算法。栅格方法是对生长元没有限制,但生成的Voronoi图精度低、耗时长。栅格方法典型的有两种：基于传统距离变换Voronoi图栅格方法和基于活动像素主动扩张Voronoi图栅格方法。
在实际应用中,通常需要以实际地图数据作为Voronoi图的生长元。地图数据有两大特点：1、数据量大。2、通常包含点、线、面各类目标,及由点、线、面组合而成的复合目标等复杂空间实体,因此用矢量方法难以生成实际地图的Voronoi图。与矢量方法相比,栅格方法能较好地处理复杂空间实体,但要考虑算法效率和精度问题。本文通过调节栅格大小,细分格网保证Voronoi图的精度。同时考虑到地图数据本身的数据量就较大,随着栅格大小逐步细化,数据量会进一步增大,效率会更低。为了提高算法的效率,本文将并行处理技术应用于Voronoi栅格生成算法,提出两种Voronoi图并行栅格生成算法,一种是基于活动像素主动生长的,另一种是基于改进归属法的,同时配合细分格网,可以较好保证生成的Voronoi图的高精度和高效率。
本文所做工作总结如下：
(1)本文首先提出了基于MPI的并行栅格Voronoi图生成算法,以活动像素主动生长做为生成Voronoi图的基础,提出了基于MPI的行式、列式、和棋盘式3种不同数据分割方法的并行Voronoi图栅格生成算法,并对3种不同数据分割方法进行了效率和扩展性分析。通过多组对比实验,表明该并行算法和细分格网结合可以在保证精度的前提下有效地提高算法的效率,但适用于集群机效果不明显。
(2)鉴于集群机的普遍存在,而最初的串行算法适用于集群机效果不好,因此我们对原串行算法实现进行改进,并在该改进算法的基础上提出了新的基于MPI并行算法。通过多组实验对比,表明该并行算法有效的提高了算法的效率并且适用于集群机。又由于现在商品化的集群系统大多是多核处理机集群,混合编程模型更适合,所以又提出了基于MPI+OpenMP的并行算法,大量实验表明混合编程模型在性能上得到了提高。
(3)在王新生提出的一种新型栅格方法的基础上,提出了一种新的判断空白栅格归属的栅格方法——改进归属法,通过大量实验证明：(a)该算法的效率高低不是单纯的由空白栅格个数决定,还需要考虑到空间目标的数量、分布、形状;(b)该算法与传统栅格算法相比性能更高。
(4)在改进归属法的基础上的首先提出了基于MPI的改进归属法的Voronoi图并行栅格生成算法,通过多组实验证明：该并行算法和细分格网结合可以在保证精度的前提下有效地提高算法的效率,并适合于集群机。接着又提出了基于OpenMP+MPI的改进归属法的Voronoi图并行栅格生成算法,通过大量实验对比,表明混合编程模型在性能上得到了提高。
Voronoi diagram is an important research in computational geometry content, in meteorology, geology, geographic information systems, urban planning, chemistry, ecology, image processing, computer graphics, virtual reality, CAD, collision detection and robot path planning and other fields Widely used, but also solve the Delaunay triangulation, skeleton computation, convex hull computation, and computational geometry minimum spanning tree problem of generating such an effective tool.
Therefore, it is particularly important to construct Voronoi diagram, Voronoi diagram generation method consists of raster and vector generation method. Vector Method earlier, many methods, the most typical methods are:incremental method, divided method and indirect method. Vector method has the advantage of the Voronoi diagram generated high precision; a problem as on the growth element is required, only a point and a half lines, if the line and face the need to undermine the integrity of its decomposition, and the storage structure is more complex. The problem with the vector, people began to study the raster generation algorithm. Element grid is no limit on the growth, but the resulting Voronoi diagram low accuracy, time-consuming. There are two typical raster methods:Voronoi diagram based on the traditional distance transform grid method and the expansion initiative based on the active pixel grid method for Voronoi diagram.
In practice, usually the actual map data as the growth Voronoi diagram element. Map data has two main characteristics:1 amount of data.2 usually contains points, lines, types of goals, and from points, lines, a combination of complex spatial entities complex object, it is difficult to generate the actual vector method using the map Voronoi diagram. Compared with vector, raster method can handle complex spatial entities, but to consider the algorithm efficiency and accuracy issues. By adjusting the grid size, grid subdivision to ensure the accuracy of Voronoi diagram. Map data itself, taking into account the amount of data to larger grid size gradually refined with the amount of data will further increase efficiency will be lower. To improve the efficiency of the algorithm, this paper applies parallel processing technology Voronoi grid generation algorithm, Voronoi diagram proposed two parallel grid generation algorithm, an initiative based on the growth of active pixels, and the other is based on the attribution method improved, At the same time with the sub-grid that can better guarantee that the generated Voronoi diagram of high precision and high efficiency. This paper summarized the work done by the following:
(1) This paper proposes a parallel MPI-based raster Voronoi diagram generation algorithm to generate active pixels active growth as the basis of Voronoi diagram is proposed based on MPI's line of type, column type, and the chessboard 3 different methods of data partitioning in parallel Voronoi diagram grid generation algorithm, and 3 different methods of data partitioning efficiency and scalability analysis. Through multiple sets of comparative experiments, show that the parallel algorithm and the combination of sub-grid accuracy can be guaranteed under the premise of effectively improve the efficiency of the algorithm, but the efficiency for the cluster machines is not obvious.
(2) Given the prevalence of the cluster machines, and since the original serial algorithm for cluster machines not good, so we improve the original serial algorithm and improved algorithm based on the proposed new parallel algorithm based on MPI. Through several experiments, it is shown that the parallel algorithm can improve the efficiency of the algorithm and apply the cluster machines. Also, because now most of the commercialization of multi-core processor cluster system clusters, hybrid programming model is more suitable for the model, it is also proposed based on MPI+OpenMP parallel algorithm, a large number of experiments show that the hybrid programming model has been improved in performance.
(3) Presented in Wang Xinsheng a new approach based on the grid, a new blank grid to determine ownership of the raster method-Improved attribution method, by a large number of experiments show that:(a) inefficiency of the algorithm is not Simply the number of decisions by the blank grid, also need to take into account the number of spatial objects, distribution, shape; (b) algorithm has higher performance than the traditional grid method.
(4) First proposed on the basis of MPI-based improved attribution method Voronoi diagram parallel raster algorithm, proved by several experiments:the parallel algorithm and sub-grid that ensure the accuracy can be combined in order to improve the efficiency of the algorithm, and for the cluster machines. Then made on the basis of OpenMP+MPI improved attribution method Voronoi diagram parallel raster algorithm, by comparing a large number of experiments, show that the hybrid programming model has been improved in performance.
引文
[1]刘玉珍.关于障碍Voronoi图的研究[D].哈尔滨理工大学,2008：7-8.
[2]S.Fortune, A sweepline algorithm for Voronoi diagrams, http://www.diku.dk/students/duff/Fortune/.1986.
[3]李成名,陈军.面条目标Voronoi图生成的动态距离变化策略[J].遥感信息.2000,23(2)：132-136.
[4]Okabe B.Boots A.Spaital Tessellations:Concepts and Appilcaitons of Voronoi Diagrams[M], NewYork:Wiley,1992.
[5]王新生,付福英等.Voronoi图的扩展、生成及其应用于界定城市空间影响范围[J].华中师范大学学报：自然科学版.2002.36(1)：107-111.
[6]王新生,郭庆胜.一种用于界定经济客体空间影响范围的方法-Voronoi图[J].地理研究,2000.19(3)：3 11-815.
[7]Okabe A, Boots B. Nearest neighbor-hood operations with generalized Voronoi diagram[J]. International Journal of Geographical Information Systems, 1994,8(1):43-71.
[8]Okabe A, Boots B, Sugihara K, et al. Spatial tessel-lations:concepts and applications of Voronoi diagrams (second edition)[M]. New York:John Wiley and Sons,2000.
[9]李淑艳.基于多核CPU的平面Voronoi图并行生成算法研究[D].陕西：陕西师范大学,2010.
[10]Nirav Patel. Voronoi Diagrams Robust and Efficient implementation, Master's Thesis Defense Department of Computer Science[M].Binghamton University, 2005.
[11]Li Jin, Donguk Kim, Lisen Mu. A sweepline algorithm for Euclidean Voronoi diagram of circles [J]. Computer-Aided Design,2006,38:260-272.
[12]Sugihara K. and Iri. M. Construction of the Voronoi diagram for'one million' generators in single-precision arithmetic[C]. Proc. IEEE, Sept.1992,80(9): 1471-1484.
[13]Held M V. An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments [J]. Computational Geometry,2001, 18(1):95-123.
[14]李成名,陈军.Voronoi图生成的栅格算法[J].武汉测绘科技大学学报,1998,23(3)：208-210.
[15]Borgefors G. Distance Transformations in digital Images. Computer Vision. Graphics and Image Processing,1986 (34):344-371.
[16]Li Chengming, Chen Jun. Raster methods of the generation of Voronoi diagrams for spatial entities [J]. International Journal of Geographical Information Science,1999,13:209-225.
[17]赵仁亮.基于Voronoi图的空间关系计算研究[D].中南大学,2002.
[18]赵哗,张有会.关于一般图形Voronoi图的离散构造法的研究[J].计算机应用与软件.2004(6),76-78.
[19]王新生,刘纪远.一种新的构建Voronoi图的栅格方法[J].中国矿业大学学报,2003,32(3)：293-296.
[20]王新生,刘纪远.基于GIS的任意发生元Voronoi图逼近方法[J].地理科学进展,2004,Vol.23,No.4：97-102.
[21]王惠春.基于SMP集群的MPI+OpenMP混合并行编程模型研究与应用[D].湖南：湘潭大学,2008.
[22]Michael J.Quinn著,陈文光,武永卫等译.MPI与OpenMP并行程序设计[M].清华大学出版社,2004.
[23]陈军Voronoi动态空间数据模型[M].北京：测绘出版社,2002.
[24]Thiessen,A.h.,Precipitation averages for Large Areas[J].Monthly Weather Review,1911 Vol.39:1082-1084.
[25]Brassel,K.and Reif,D.Procedure to generate Thiessen polygon [J]. Geographical Analysis,1979 Vol.11(3):289-303,.
[26]周海燕,空间数据挖掘的研究[D].解放军信息工程大学,2003.
[27]Yang W.P. Managing spatial objects with VMO-tree. In Proc.7th Int. Sym. On spatial data handing. Delft,Taylor&Francis,1996 711-726.
[28]Aurenhammer. Voronoi diagrams-A survey of a fundamental geometric data structure[J]. ACM Computing Surveys,1991(23):345-405.
[29]伊君翰,朱传琪.基于多核的并行编程模型[D].复旦大学.2008.
[30]陈永健,王鼎兴.OpenMP编译与优化技术研究[D].清华大学.2004.
[31]李成名.基于Voronoi图的空间关系描述、表达与推断[D].武汉测绘科技大学.1998
[32]沈雪峰.多CPU系统的中断机制[D].电子科技大学.2009
[33]都志辉.高性能计算之并行编程技术—MPI并行程序设计[M].清华大学.2001
[34]Kokichi Sugihara,VORONOI2:a fortran program for constructing the voronoi diagram,Geographic Systems,1994(1):347-349
[35]赵仁亮.基于Voronoi图的GIS空间关系计算[M].测绘出版社.2006
[36]张有会.关于一般图形Voronoi图的近似构造法的研究[J].数值计算与计算机应用,2002.9(3)：216-225.
[37]ZHAO Renliang, CHEN Jun, Li Zhilin, Gold C.M.,2002,Hierarchical Computation for multiscale Voronoi diagrams based on the mathematical morphology[C]. Lecture Notes in Computer Science 2331, Springer,1004-1013.
[2]S.Fortune, A sweepline algorithm for Voronoi diagrams, http://www.diku.dk/students/duff/Fortune/.1986.
[3]李成名,陈军.面条目标Voronoi图生成的动态距离变化策略[J].遥感信息.2000,23(2)：132-136.
[4]Okabe B.Boots A.Spaital Tessellations:Concepts and Appilcaitons of Voronoi Diagrams[M], NewYork:Wiley,1992.
[5]王新生,付福英等.Voronoi图的扩展、生成及其应用于界定城市空间影响范围[J].华中师范大学学报：自然科学版.2002.36(1)：107-111.
[6]王新生,郭庆胜.一种用于界定经济客体空间影响范围的方法-Voronoi图[J].地理研究,2000.19(3)：3 11-815.
[7]Okabe A, Boots B. Nearest neighbor-hood operations with generalized Voronoi diagram[J]. International Journal of Geographical Information Systems, 1994,8(1):43-71.
[8]Okabe A, Boots B, Sugihara K, et al. Spatial tessel-lations:concepts and applications of Voronoi diagrams (second edition)[M]. New York:John Wiley and Sons,2000.
[9]李淑艳.基于多核CPU的平面Voronoi图并行生成算法研究[D].陕西：陕西师范大学,2010.
[10]Nirav Patel. Voronoi Diagrams Robust and Efficient implementation, Master's Thesis Defense Department of Computer Science[M].Binghamton University, 2005.
[11]Li Jin, Donguk Kim, Lisen Mu. A sweepline algorithm for Euclidean Voronoi diagram of circles [J]. Computer-Aided Design,2006,38:260-272.
[12]Sugihara K. and Iri. M. Construction of the Voronoi diagram for'one million' generators in single-precision arithmetic[C]. Proc. IEEE, Sept.1992,80(9): 1471-1484.
[13]Held M V. An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments [J]. Computational Geometry,2001, 18(1):95-123.
[14]李成名,陈军.Voronoi图生成的栅格算法[J].武汉测绘科技大学学报,1998,23(3)：208-210.
[15]Borgefors G. Distance Transformations in digital Images. Computer Vision. Graphics and Image Processing,1986 (34):344-371.
[16]Li Chengming, Chen Jun. Raster methods of the generation of Voronoi diagrams for spatial entities [J]. International Journal of Geographical Information Science,1999,13:209-225.
[17]赵仁亮.基于Voronoi图的空间关系计算研究[D].中南大学,2002.
[18]赵哗,张有会.关于一般图形Voronoi图的离散构造法的研究[J].计算机应用与软件.2004(6),76-78.
[19]王新生,刘纪远.一种新的构建Voronoi图的栅格方法[J].中国矿业大学学报,2003,32(3)：293-296.
[20]王新生,刘纪远.基于GIS的任意发生元Voronoi图逼近方法[J].地理科学进展,2004,Vol.23,No.4：97-102.
[21]王惠春.基于SMP集群的MPI+OpenMP混合并行编程模型研究与应用[D].湖南：湘潭大学,2008.
[22]Michael J.Quinn著,陈文光,武永卫等译.MPI与OpenMP并行程序设计[M].清华大学出版社,2004.
[23]陈军Voronoi动态空间数据模型[M].北京：测绘出版社,2002.
[24]Thiessen,A.h.,Precipitation averages for Large Areas[J].Monthly Weather Review,1911 Vol.39:1082-1084.
[25]Brassel,K.and Reif,D.Procedure to generate Thiessen polygon [J]. Geographical Analysis,1979 Vol.11(3):289-303,.
[26]周海燕,空间数据挖掘的研究[D].解放军信息工程大学,2003.
[27]Yang W.P. Managing spatial objects with VMO-tree. In Proc.7th Int. Sym. On spatial data handing. Delft,Taylor&Francis,1996 711-726.
[28]Aurenhammer. Voronoi diagrams-A survey of a fundamental geometric data structure[J]. ACM Computing Surveys,1991(23):345-405.
[29]伊君翰,朱传琪.基于多核的并行编程模型[D].复旦大学.2008.
[30]陈永健,王鼎兴.OpenMP编译与优化技术研究[D].清华大学.2004.
[31]李成名.基于Voronoi图的空间关系描述、表达与推断[D].武汉测绘科技大学.1998
[32]沈雪峰.多CPU系统的中断机制[D].电子科技大学.2009
[33]都志辉.高性能计算之并行编程技术—MPI并行程序设计[M].清华大学.2001
[34]Kokichi Sugihara,VORONOI2:a fortran program for constructing the voronoi diagram,Geographic Systems,1994(1):347-349
[35]赵仁亮.基于Voronoi图的GIS空间关系计算[M].测绘出版社.2006
[36]张有会.关于一般图形Voronoi图的近似构造法的研究[J].数值计算与计算机应用,2002.9(3)：216-225.
[37]ZHAO Renliang, CHEN Jun, Li Zhilin, Gold C.M.,2002,Hierarchical Computation for multiscale Voronoi diagrams based on the mathematical morphology[C]. Lecture Notes in Computer Science 2331, Springer,1004-1013.