vc0186 构造Voronoi图

摘要：voronoi图是仅次于凸壳的一个重要的几何结构。这是由于voronoi图在求解点集或其他儿何对象与yt离有关的问题时起重要作用。这些问题包括，谁距离谁最近，谁距离谁最远，等等。早在1850年DirMhlM及1908年voronoi在其论文中都讨论过Voronoi图的慨念。

对于VORONOI图的构造有很多的算法，比如半平面交，增量构造算法，分治法，减量算法等。本文对探讨了voronoi图的各种构造算法，以及DELAUNAY三角剖分，重点是构造voronoi图构造算法的改进和优化，利用并行的方式提高运算速度。算法的实现是在VC++6.0开发环境下实现。

关键字：voronoi图   Delaunay三角剖分 联机增量算法 并行算法

1.1引言

Voronoi图是俄国数学家G．Voronoi[Voronoil908]在研究邻近问题时提出来的，是关于空问邻近关系的一种基础数据结构。在不同的领域，Voronoi图有时被称为Thiessen多边形、Dirichrit网格、或Wigner--Seitz区域等。平面上一个点集P的Voronoi图是对平面的一个划分，每个分区表示一些点的轨迹，这些点到P的一个元素比到其它元素更近。平面多边形的Voronoi图也是对平面的一种划分．每个分区从属于多边形的一条边，分区内的点到该边比到其它边距离近。

在Voronoi图中，被用来划分空间的各个基本图形元素一般被称为对象。最基本的Voronoi图是以平面点集P为对象的Voronoi图，Voronoi图的定义可以推广到二维或三维，也可以推广到二阶或高阶(以两个站点或多个站点为一组划分邻近区域)，也可以进一步推广到对象包括线段或多边形的广义Voronoi图另外，关于移动点的Voronoi图、带权的Voronoi图、以及曲面上的Voronoi图也被人们所研究，并且有着具体的应用背景。

1.2 选题的相关发展

1.2.1 Voronoi图的发展历史      

Voronoi图是关于空间邻近关系的一种基础数据结构。在Voronoi图中，被用来划分空间的各个基本图形元素一般被称为元素。最基本的Voronoi图是以平面点集P为元素的Voronoi图，它将平面划分成凸多边形形状的Voronoi区域，P中的每个元素pi对应一个这样的区域Vi，使得vi内的任何点距离pi比距离其他元素近。Voronoi图的定义可以推广N--维或三维甚至是高维，也可以推广到二阶或高阶(以两个元素或多个元素为一组划分邻近区域)。

Voronoi图的意义在不同的科学领域被发现和重视，已有l00来年的历史。随着计算机技术的发展，80年代是Voronoi图研究与应用的高潮随后，许多人对Voronoi图进行了综述或总结。Aurenhanmlmer于1991年发表了～篇包括20多篇参考文献的综述m，详细总结了Voronoi图的历史、定义、性质、算法、扩展和应用。Fortun于1992年侧重对Voronoi图的算法进行了比较和分析。

Voronoi图最早是由俄国数学家Voronoi于1908年提出．关于平面点集的Voronoi图的研究比较广泛，但是关于平面多边形的Voronoi图的研究却不是很多，特别是对某些极其复杂的平面多边形能求出完全正确的Voronoi图的算法非常少，作者在对平面多边形的Voronoi图研究的基础上提出了一种新的Voronoi图的求解算法．已有的平面多边形的Voronoi图的求解算法研究最多的有分治构造法．此种算法虽然速度快，其算法效率可达到0(，zln行)，但是其成功率往往很低，因为在根据二叉树求解时由于误差的原因，若某一步求解相邻叶子结点时产生错误，则这个错误就会一直传播下去，并不断放大扩散，进而影响到与后续的二叉树结点求解．所以这种算法在实际的求Voronoi图中并不实用．而且上述算法需要对区域中的环单独拿出来计算各自的Voronoi图，然后进行合并计算，这也会引起误差的积累[1叫]．本文提出了Voronoi算法，可一次计算区域中的所有环的Voronoi图，且每个Voronoi的子结点相独立，互不影响，避免了误差累积．

VORONOI作为一种重要的计算机图形学技术，在数控加工、机器人的运动规划和曲面生成等许多领域有广阔的应用前景。研究了由直线和圆弧组成的平面多连通域VORONOI图的生成算法，提出了平面闭包的搜索算法与闭包的归一化方法。

随着Voronoi图的定义和算法被广泛传播，Voronoi图的应用领域也在不断扩展。目前，Voronoi图的主要应用领域有：几何形体重构、图像处理与模式识别、物理化学分子生物学、机器人运动规划、机械制造及装饰图案设计等。根据不同的图形元素可将Voronoi图分为三种主要形式，即平面点集的Voronoi图、平面曲线多边形的Voronoi图和空间多面体的Vomnoi图。这些不同形式的Voronoi图分别将平面和空间根据距离的远近关系进行了一定的划分。每个子区域分别从属于一个图形元素，并且分区内的点到该图形元素的欧几里德距离比到其他图形元素的欧几里德距离近。最基本的Voronoi图是以平面点集P为元素的Voronoi图，它将平面划分成凸多边形形状的Voronoi区域，P中的每个元素对应一个这样的区域Ⅵ，使得Ⅵ内的任何点到Pi的欧几里德距离比到其他元素的欧几里德距离近。同理，平面内曲面多边形的Voronoi图是对有限区域的这样一个划分：区域Ⅵ内的点到相应边界轮廓元素I的欧几里德距离比到其他轮廓元素段的欧几里德距离近。