Voronoi图与路径规划

创作时间:

作者:

@小白创作中心

Voronoi图与路径规划

引用

CSDN

https://blog.csdn.net/xhtchina/article/details/118876875

Voronoi图，又称泰森多边形或Dirichlet图，是一种在计算几何中广泛应用的空间划分方法。它不仅在计算机图形学中有着重要的应用，而且在自动驾驶领域中，Voronoi图也被用来生成汽车的可行驶区域。本文将详细介绍Voronoi图的几何定义、构造方法及其在路径规划中的应用。

1. 几何定义

Voronoi图，又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。

对于点集
里的种子点
，它的Voronoi区域定义为：

2. 构造方法

Voronoi图是Delaunay三角剖分的对偶图，生成它的方法有很多 [1]，比较有名的有分治算法，扫描线算法，增量法等。但利用Delaunay三角剖分生成Voronoi图的算法是最快的。

但最快的方法则是构造Delaunay三角剖分，再连接相邻三角形的外接圆圆心，即可以到Voronoi图。

Delaunay三角剖分算法：

对于给定的初始点集P，有多种三角网剖分方式，其中Delaunay三角网具有以下特征：

Delaunay三角网是唯一的；
三角网的外边界构成了点集P的凸多边形“外壳”；
没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。
如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。

Delaunay三角形网的特征又可以表达为以下特性：

在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；
在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；
形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；
不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。

Delaunay三角形产生的基本准则：任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[Delaunay 1934]。Lawson[1972] 提出了最大化最小角原则，每两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。Lawson[1977] 提出了一个局部优化过程 (LOP, local Optimization Procedure)方法。

基于散点建立数字地面模型，常采用在d维的欧几里得空间Ed中构造Delaunay三角形网的通用算法—逐点插入算法，Delaunay三角剖分算法过程如下：

遍历所有散点，求出点集的包容盒，得到作为点集凸壳的初始三角形并放入三角形链表。
将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
根据优化准则对局部新形成的三角形进行优化（如互换对角线等）。将形成的三角形放入Delaunay三角形链表。
循环执行上述第2步，直到所有散点插入完毕。

上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法不易引入地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。

为了克服基于散点构网算法的上述缺点，特别是为了提高算法效率，可以对网格中三角形的空圆特性稍加放松，亦即采用基于边的构网方法，其算法简述如下：