● 摘要
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图并行栅格生成算法，通过大量实验对比，表明混合编程模型在性能上得到了提高。