文章目录1 .问题描述1.1定义1.2应用2 .算法分析与设计2.1Voronoi图绘制方法与步骤2.2Delaunaytin网的生成2.3数据结构设计2.4算法复杂度分析3 .实验结果参考文献
1 .问题说明1.1定义
也称为Voronoi图的hsdmt多边形或Dirichlet图，由连接相邻两点的直线的垂直平分线组成的一系列连续多边形。
Voronoi地图具有以下特征：
)1)每个v多边形都有一个生成源
)从各v多边形内点到该生成源的距离比到其他生成源的距离短；
(3)从多边形的边界上的点到生成该边界的生成源的距离相等；
)4)邻接图形的Voronoi多角形边界线以原邻接边界线为子集。
1.2在计算几何学科中应用的重要地位，以点集划分的区域到点距离最近的特点，广泛应用于地理学、气象学、结晶学、航天、核物理学、机器人等领域。 障碍物点集中时，避开障碍寻找最佳路径。
2 .算法分析和设计Voronoi图具有按距离划分邻区的普遍特性，应用范围广泛。 生成v地图的方法很多，常见的有有分治法、扫描线算法和Delaunay三角剖分算法。
2.1绘制Voronoi图的方法和步骤本次实验采用了Delaunay三角剖分算法。 主要是在生成Voronoi图时，老师要建立其对偶元Delaunay三角网，找出三角网各三角形外接圆的中心，最后连接相邻三角形外接圆的中心，形成以各三角形顶点为生成源的多边形网。 如下图所示。
构建Voronoi图算法的关键是将离散数据点恰当地连接到三角网上，即建立Delaunay三角网。
要创建Voronoi地图，请执行以下操作：
(1)离散点自动构建，即构建Delaunaytin。 对于离散点和形成的三角形的编号，记录各三角形由哪3个离散点构成。
(2)计算每个三角形的外接圆的中心，并记录下来。
)3)循环三角形链表，寻找与现在三角形pTri的三边和边共有的邻接三角形TriA，TriB，TriC。
(4)找到后，将找到的三角形的外心连接到pTri的外心，并保存在wino边缘链接列表中。 如果找不到，请查找最外侧的垂线并将其保存在维诺边链接列表中。
)扫描结束后，发现了所有的韦诺纳边，根据边绘制韦诺纳图。
2.2Delaunaytin的生成创建Voronoi图的关键是Delaunaytin的生成。 Delaunaytin的特性：
)圆度，任一三角形的外接圆内部不包含其他点。
)最接近)在最接近的三点形成三角形，且各线段(三角形的边)不相交。
(3)唯一性：无论从区域的何处构建，最终都将获得一致的结果。
)4)最优性：如果可以调换任意两个相邻三角形构成的凸四边形的对角线，则两个三角形的6个内角中最小的角度不会变大。
(5)按升序排列三角网中每个三角形的最小角时，Delaunay三角网的排列得到的数值最大。
(6)地域性)添加、删除、移动某个顶点时，只对相邻三角形产生影响。
(7)具有凸多边形的外壳：三角网最外层的边界形成凸多边形的外壳。
Delaunay剖分是三角剖分的标准，实现它有多种算法。 这次采用Bowyer-Watson算法，算法的基本步骤如下。
)1)制作一个包含所有散点的超级三角形，放入三角形链表。
)2)依次插入点集内的散点，找出三角形链表中含有外接圆
要完成在Delaunay三角形链表中插入点，请插入点的三角形，删除该点的公共边(称为受影响三角形)，然后连接插入点和受影响三角形的所有顶点。
)3)根据优化准则对局部新形成的三角形进行优化。 把形成的三角形放入Delaunay三角形链表。
)4)重复上述步骤2，直到所有散点插入完成。
重要的步骤2如下图所示。
第三步局部优化的指导原则是：
1 .优化新形成的三角形，将有共同边的两个三角形合成一个多边形。
2 .按最大空圆标准进行检查，确认第四个顶点是否在三角形外接圆内。
3 .如果有，请修改对角线并交换对角线。 也就是说，完成局部优化过程的处理。
局部优化进程(lop )的处理过程如下图所示。
2.3数据结构设计本程序的实现是用C#面向对象语言实现的，因此数据结构的设计采用类的形式，具体如下。
//public class site { public doublex，y； public Site () public site (double y，double y ) ) { this.x=x； this.y=y； }//边public class Edge{ public Site a，b； publicedge(sitea，Site b ) ) { this.a=a； this.b=b；
}}// 三角形 public class DelaunayTriangle { Voronoi voronoi = new Voronoi(); public Site site1, site2, site3;//三角形三点 public Site centerPoint;//外界圆圆心 public double radius;//外接圆半径 public List<DelaunayTriangle> adjoinTriangle;//邻接三角形 public DelaunayTriangle(Site site1,Site site2,Site site3) { centerPoint = new Site(); this.site1 = site1; this.site2 = site2; this.site3 = site3; //构造外接圆圆心以及半径 voronoi.circle_center(centerPoint, site1, site2,site3,ref radius); } } 2.4 算法复杂度分析时间复杂度：
Delaunay三角网的生成的时间复杂度：
步骤一：构造一个超级三角形，O（1）；
步骤二：产找影响的三角形，构造新的三角形， O （ 1 + 2 + … + n ） = O ( n 2 ) O（1+2+…+n）=O(n^2) O（1+2+…+n）=O(n2)
步骤三：对新形成的三角形进行优化局部优化：O(n)。
因此，整体时间复杂度是： O ( 1 ) + O ( n 2 ) + O ( n ) = O ( n 2 ) O(1)+O(n^2)+O(n)=O(n^2) O(1)+O(n2)+O(n)=O(n2)。
从Delaunay三角网生成Voronoi图的时间复杂度：
步骤一：构造构建Delaunay三角网， O ( n 2 ) O(n^2) O(n2)；
步骤二：计算三角形外接圆圆心，O(n)；
步骤三：寻找三角形三边相邻三角形：3O(n)；
步骤四：找到的维诺边存入链表中，画出维诺图：O(n)。
因此，整体时间复杂度是 O ( n 2 ) + O ( n ) + 3 O ( n ) + O ( n ) = O ( n 2 ) O(n2)+ O(n)+ 3O(n)+ O(n)=O(n^2) O(n2)+O(n)+3O(n)+O(n)=O(n2)。
随机生成点：
生成Delaunay三角形网：
生成Voronoi图：
生成Voronoi图的可执行程序和源码工程文件见here。
下面附上相关函数cjdzt（详细代码见源码工程文件）。
//根据点集构造Delaunay三角形网public void setDelaunayTriangle(List<DelaunayTriangle> allTriangle, List<Site> sites);//根据Delaunay三角形网构造Voronoi图的边public List<Edge> returnVoronoiEdgesFromDelaunayTriangles(List<DelaunayTriangle> allTriangle, List<Edge> voronoiRayEdgeList);//根据三角形链表返回三角形所有的边public List<Edge> returnEdgesofTriangleList(List<DelaunayTriangle> allTriangle);//对新形成的三角形进行局部优化public List<DelaunayTriangle> LOP(List<DelaunayTriangle> newTriList); //判断边是否属于三角形public bool isEdgeOnTriangle(DelaunayTriangle triangel,Edge edge);//判断点是否属于三角形public bool isPointOnTriangle(DelaunayTriangle triangle, Site site);//将点与受影响的三角形三点连接，形成新的三个三角形添加到三角形链中public void addNewDelaunayTriangle(List<DelaunayTriangle> allTriangles,DelaunayTriangle influenedTri,Site point);//找出受影响的三角形的公共边public List<Edge> findCommonEdges(List<DelaunayTriangle> influenedTriangles);//找出两个三角形的公共边public Edge findCommonEdge(DelaunayTriangle chgTri1, DelaunayTriangle chgTri2);//判断插入点是否在三角形边上public Site[] isOnEdges(DelaunayTriangle triangle,Site site); //判断点是否在三角形外接圆的内部public bool isInCircle(DelaunayTriangle triangle, Site site) ;//求三角形的外接圆心public void circle_center(Site center, Site sites0, Site sites1, Site sites2, ref double radius) ;//求两点之间距离public double distance2Point(Site p,Site p2);PS：由于时间和水平有限，博文难免有不足甚至错误之处，仅供参考，欢迎批评指正。
参考文献百度百科.Voronoi