三维Voronoi图的动态实现和研究.docx

三维Voronoi图的动态实现与研究曹锐创石奇偲黄棱潇摘要在计算几何中，离散点构造Voronoi图是一个非常基础且应用广泛的问题。N个离散点按照最邻近原则划分区域，每个点与它的最近邻区域相关联。本实验重点研究Voronoi图的三维情况，运用分块的方法动态实现了单一Voronoi细胞和三维Voronoi图的构造。同时，本实验对均匀分布的随机点产生的性质进行了一系列研究和分析。关键字：三维Voronoi图，单一Voronoi细胞，分块，均匀分布引言在二维（平面）情况下，Voronoi图是由一组连接两邻近点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面。每个离散点则各自拥有一个细胞区域，区域内部的点到相对应的离散点距离最近。在高维情况下，连接两邻近点直线的垂直平分不再是直线，形成Voronoi图的细胞则会从平面上的多边形转变为高维的多面体。Voronoi图的平面情况和三维情况的区别不光体现在细胞的构成上。平面情况下，由于可以应用欧拉公式，我们能知道构成Voronoi图的顶点和边数和离散点数为相同数量级。但涉及到三维情况：首先，每个细胞区域构成多了面的概念；其次，构成细胞的顶点数和边数在数量级上也有了质变，可以达到离散点数数量级的平方。这为构造三维Vonoroi图带来了困难，导致了时间复杂度和空间复杂度的增加。三维Voronoi图主要有Quickhull[11]和分块动态实现[12]两种算法，但它们的时间复杂性最差情况下都可以达到。实验中，我们首先动态实现了单一Voronoi细胞的构造。事实上，在许多物理应用中，人们更关注的仅是几个单一Voronoi细胞，而不是整个Voronoi图的构造。运用单一Voronoi细胞的构造，结合分块方法，我们动态的构造三维Vonoroi图。尽管在最差情况下，时间复杂性可以达到，但如果考虑离散点是随机均匀分布的，实验结果显示平均复杂度随着离散点数的增加线性增长。相关工作自从1907年GeorgyVoronoi提出了Voronoi图的概念[1]后，Voronoi图这种几何结构就被广泛的应用到了各个领域，比如形状建模[2]、运动规划[3]、科学可视化[4]、碰撞侦测[5]、几何学[6]以及化学[7]。针对三维情况的N个离散点，每个点的Voronoi细胞是一个三维的多面体。三维Voronoi图有许多变种问题被人考虑过。如果不给区域限制，那么离散点构成的凸包边界上的离散点的细胞区域是无界的。但在许多应用中，我们考虑的是对某个封闭的区域进行划分，构造Voronoi图。这就涉及到了封闭区域的形状性质——一个很关键的问题，区域是否是凸的。有许多篇文章[8]对区域问题进行了分析。另一个被广泛考虑的问题是离散点的分布情况，这在一定程度上影响了算法的时间复杂度和空间复杂度。一个熟知的结论是如果离散点是独立均匀分布于空间中的，那么有平均复杂度仅为O(n)的算法能构造出三维Voronoi图。更复杂的，若考虑离散点符合某种条件的高斯分布，则也能在一定程度上降低算法复杂度。[9][10]两篇文章针对不同条件的高斯分布进行了分析和算法设计。算法概述算法部分的代码是用C++实现的，主要围着两个大类展开。Voronoicell类包含了如何构造一个单一Voronoi细胞。该类包含初始化、构造和输出功能，用Voronoi细胞（三维多面体）的顶点以及它们连成的边来表示该Voronoi细胞。另一个大类是container类，主要解决了三维Voronoi图的构造和表示。该类能调用Voronoicell类，并在这基础上包含一系列计算Voronoi图的函数。为完善Voronoi图的构造以及每个细胞邻居的计算，我们需要另外两个类，分别是voronoicell_neighbor和container_poly。单一Voronoi细胞单一Voronoi细胞是三维的一个凸多面体，主要用voronoicell类实现，用一系列相邻的顶点表示。该类包含一系列函数，能计算和输出对应某一中心点的单一Voronoi细胞。我们使用正方体作为该Voronoi细胞的初始架构。算法是动态的，每次新加入一个离散点相当于引入了一张切平面。主要分成四个步骤：1）判断切平面是否与目前的Voronoi细胞相交；2）如果相交，找出原来Voronoi细胞上某条与切平面相交的边（特殊情况下，可能是点）；3）由该边出发，有方向性的找出原Voronoi细胞的面，重构Voronoi细胞的边和顶点结构；4）删去原Voronoi细胞多余的边和顶点。单一Voronoi细胞主要由如下形式表示：p：public变量，记录Voronoi细胞上的顶点个数pts[]：记录Voronoi细胞上顶点的坐标nu[]：记录Voronoi细胞上顶点的度数ed[][]：记录边，针对第i个顶点，