doclist 阅读(190) 评论(0)

维诺图(Voronoi Diagram),简单来说,是一种平面区域的划分方式。假设平面上有 n 个点:P1 ~ Pn,那么对应维诺图则划分成 n 个区域:S1 ~ Sn,并且 Si 内所有点到 Pi 的距离小于等于到其他任意点的距离。维诺图还经常和德洛内三角(Delaunay 三角网)扯上关系,德洛内三角是一系列相连不重叠的三角形集合,特点有两个:1、任意三角形的外接圆不包含面内其他三角形顶点,2、相邻两个三角形构成的凸四边形,交换对角线,六个内角的最小角不会增大。如下图,实线构成德洛内三角,虚线构成维诺图,德洛内三角每一个三角形的顶点便是维诺图的初始点集。

理论上,两种图形可以互相转化。1、生成维诺图后,连接有公共边的初始点集,便可构成德洛内三角。2、生成德洛内三角后,针对每一个三角形边,生成垂直平分线,并将垂直平分线的端点设置为三角形边所在外接圆的圆心即可(内部三角形边的垂直平分线为线段,边界三角形边的垂直平分线为射线)。

下面先推荐几篇我看过写得比较好的学习资料,可以用于参考。(吐槽:这几篇是我从海量博客中筛选出来的,网上能搜出一堆相关博客,可真正有内容的却没有几篇)

1、http://www.cnblogs.com/zhiyishou/p/4430017.html 讲解如何生成Delaunay三角网的博客。这篇文章是讲解地比较细,比较全,比较容易理解的,不过同样有很多坑,阅读时不要遗漏了博客评论区,那里指出了很多坑点。最坑的一点,即使你排除万难,写出了和作者一模一样的代码,仍然有很多BUG,比如点数少的情况下有可能没有任何生成,比如最终生成的德洛内三角不是凸包等。当然,文章确实好,值得一看,用来理解德洛内三角是很有帮助的。

2、https://en.wikipedia.org/wiki/Fortune%27s_algorithm 讲解如何生成维诺图的维基百科,有个gif 图可以帮助理解,中间那段英文的算法描述写得很好,读下来大致就有了生成维诺图的思路(英文不好的可以百度翻译一下)。下面还附了个伪代码,不过这伪代码我是完全看不懂了,百度翻译也不管用了。文章末尾还附加了几个算法源码,不过不推荐阅读,代码可读性太差了,反正我是啃不下来,后面会推荐一个写得比较清楚的源码。

3、https://www.cnblogs.com/Seiyagoo/p/3339886.html 讲解如何生成维诺图的博客,内容比较少,不过比较清晰,附加的伪代码也比较容易理解,建议有了大致思路后根据这篇博客来完善代码。

4、https://www.cs.hmc.edu/~mbrubeck/voronoi.html 提供源码的博客,其他很多博客都只是简单介绍方法,而像codeproject 或Wikipedia 上的源码可读性太差(不是我吐槽,是真的太差,完全看不懂),而这篇博客提供的代码很适合用来学习,定义清晰明了,虽然代码效率达不到logn,但这仅仅是存放海岸线的数据结构差异,其余内容与平面扫描法一致,可以参照该源码去解读推荐的第三篇博客。不过该源码也有些BUG,有一些特殊情况会返回不正确的维诺图。

下面就介绍通过平面扫描法来生成维诺图,首先介绍平面扫描法的几个基础定义:

1、扫描线:扫描线将从 y = 0 一直扫描到 y = maxY,扫描完成后,维诺图也将生成完毕。(上图的黑色线)

2、海岸线:由多段抛物线组成,抛物线的焦点是初始点集,准线为扫描线。(上图的蓝色线)

3、站点事件:扫描线扫描到了某个初始点。

4、圆事件:扫描线扫描到了某个圆(三个站点共圆)的最低点。

算法思路:

我们需要维护一条扫描线和一条海岸线,这两条线都随着程序的运行,通过整个平面。扫描线是一条直线,我们可以假定它是水平的,在平面上从上到下地移动。在算法运行期间,扫描线上方的初始点已经被纳入Voronoi图,而扫描线下方的点暂未考虑。海滩线不是一条直线,而是一条复杂的多段曲线,位于扫描线的上方,它将已经确定的区域和未确定的区域分割开,即不管后续还有多少个点,海岸线上方的维诺图都已经是确定的了。对于扫描线上方的初始点,我们可以定义距离该点和扫描线等距的点的曲线(即以该点为焦点,以扫描线为准线的抛物线),海岸线就是这些抛物线并集的边界。随着扫描线的推进,海岸线中相邻抛物线交点(相交的点)将勾勒出维诺图的边。海岸线也随着扫描线的推进而推进,始终保持其上的点到焦点的距离和到扫描线的距离相等。

该算法使用了排序二叉树来维护海岸线,使用优先队列来维护可能引起海岸线变化的事件。这些事件包括新增抛物线到海岸线(扫描过一个初始点,称之为站点事件)和从海岸线中删除某一条抛物线(这条抛物线缩小成一个点时,即海岸线中相邻的三个抛物线焦点生成的圆与扫描线相切,称之为圆事件)。每一个事件可以用发生该事件时的扫描线 y 坐标来确定优先级。然后,我们要做的就是反复从优先队列中取出事件,进行处理,可能会影响到海岸线结构,可能会新增圆事件。

所以,该算法的重点便是如何处理站点事件和圆事件。首先看站点事件,当扫描线遇到 P4 时,过 P4 做扫描线的垂线,垂线和海岸线相交点到 P4 和 P2 距离相等,当扫描线越过 P4 时,将生成一条以 P4 为焦点,扫描线为准线的抛物线,该抛物线和 P2 对应的海岸线相交于两点,这两点会随着扫描线的移动而分离,事实上,这两点将勾勒出同一条维诺图边(可以确定该边上点到 P4 和 P2 距离相等)。P4 抛物线与 P2 抛物线交于两点,会将 P2 抛物线分割成两段抛物线,命名为S1、S2,假设 P4 下方没有新的站点,随着扫描线继续移动,P4 对应抛物线将越变越宽,可能会将原先 S1、S2 挤兑没,即 S1 可能由一段抛物线缩小成一个点,而 P1 抛物线和 S1 的交点,与 P4 抛物线和 S1 的交点重合,这便产生了一个圆事件,即缩小成的那一点到 P1、P2、P4 距离相等。当然程序不可能做到一点一点的移动扫描线,所以生成圆事件,是在遇到 P4 的一瞬间决定的,即遇到 P4 时,判断 P1、P2、P4 是否共圆。接着我们来看圆事件,当发生了圆事件后,就说明有某一段抛物线缩小成一个点,所以我们就需要将该段抛物线删除,并生成已经确定下来的维诺图边。 

维诺图的目标是找出所有站点对应区域的边,而边是随着扫描线移动,由相邻抛物线交点勾勒出来的,所以我们把边记在弧上,一条弧左右各有一个交点,所以我们每条弧记两条边S0、S1。当发生站点事件时,先找到其正上方的弧,然后这条弧中间部分将被新的抛物线取代,即由一段弧变成两个交点Inter1、Inter2 和 三段弧Arc1、Arc2、Arc3,其中Arc2 是新增的弧,Arc1、Arc3 是原弧分裂出来的,所以Arc1 的S0 继承自原弧的S0,Arc3 的S1 继承自原弧的S1,Arc1 的S1 与 Arc2 的S0 将指向根据左交点创建的一条新边,Arc2 的S1 和Arc3 的S0 将指向根据右交点创建的一条新边。当发生圆事件时,弧Arc 消失,所以 Arc 的S0、S1 将完成构造,即S0、S1 的终点设置在圆事件的圆心,而 Arc 消失后,其前置弧和后置弧相交在一起,所以前置弧的S1 和后置弧的S0 将指向根据圆心创建的一条新边。当所有事件处理完毕后,我们需要假设一条扫描线,使剩余的所有相邻弧交点位于维诺图边界外,计算此时这些交点的位置,完成剩余的维诺图边。

数据结构:

1、我们需要按 y 顺序遍历站点和圆事件,所以引入优先队列这个数据结构(Y 越小越靠前,Y 相同则 X 越小越靠前)。

2、我们需要快速获取某点正上方的抛物线,所以引入排序二叉树,排序二叉树每一个叶子结点代表一段抛物线,每一个内部结点代表相邻抛物线的交点,排序依据就是交点的 x 坐标,从而可以用logn 的时间,快速获取某点正上方的抛物线。(排序二叉树可能会退化成链表,真正使用的时候可以考虑是否可以替换成平衡二叉树)

3、我们需要快速检查相邻的三段抛物线对应焦点是否共圆,所以引入双向链表,用于管理排序二叉树的叶子结点,即每个叶子结点记录上一片叶子和下一片叶子指针。

源码链接:伪代码可以看上面的第三篇博客,或者直接阅读下面的源代码,注释应该是比较全了。该源码仅用于交流学习,内部有挺多细节没有考虑最优的算法。

https://github.com/hchlqlz/VoronoiDiagram

欢迎大家指出源码 BUG。