维诺图 (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's_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.
来源: https://www.cnblogs.com/hchlqlz-oj-mrj/p/10771198.html