维诺图（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。
