Voronoi图（三）：构造Voronoi图
1. 平面扫描策略的困境
对于Voronoi的构造，我们究竟使用什么策略比较合适呢？针对这个问题，大家可以结合之前我们讲解的算法策略来分析一下呢。如果你之前看过笔者所著的其他计算几何算法详解，你应该对下面这些算法策略感到无比亲切：
- 平面扫描策略（Plane Sweep），比如几何求交，三角拆分；
- 随机增量策略（Randomized Incremental Algorithm），比如点定位；
其中，平面扫描策略是我们介绍最多的算法，那么我们是否能应用平面扫描策略来解决Voronoi图的构造问题，以达到简化问题的目的呢？为了回答这个问题，我们先来看看之前平面扫描策略的一个比较重要的特性：
扫描线将平面分割成两个部分：1）固定部分；2）待处理部分；也就是说，待处理部分不会对已固定部分产生任何的影响。
这个例子很明确的告诉我们，如果还沿用之前的策略，无疑需要对算法状态进行回退，从而使算法逻辑异常复杂。现在原先的平面扫描策略遇到不小的困境。这也是为什么Voronoi构造的平面扫描算法的发现时间，相对其他算法较晚的原因，比如分治，原因也很简单，只要有人想要用平面扫描策略构造Voronoi图就会遇到“回退困境”。
那这是否意味着平面扫描策略对于构造Voronoi图来说，是个死胡同呢？很幸运地是，基于Fortune的平面扫描策略很好地规避了“回退困境（Trackback dilemma）”，使平面扫描策略也能在构造Voronoi图上大显身手，而且大家后续也能看到这个比较特殊得平面扫描策略非常的优雅，为什么这么说呢？如果说之前的算法都是把几何图形计算出来，那么基于Fortune的平面扫描算法是将Voronoi图”描绘“出来的，如同画家的画笔一样，一笔一笔地将Voronoi图勾勒出来。接下来，我们就来看看这个神奇的算法吧！
2. 另一个Voronoi图
为了规避”回退困境“，Fortune的策略是将原来的Voronoi图转换成另一种等价的拓扑结构。这个结构中，原本由直线组成的Voronoi Edge将会变成曲线。下图展示了由曲线组成的Voronoi图1：
通过这种”以曲代直“的方法，我们就能有效避免”回退困境“，但是在实际计算中，我们不会去真正计算经过变换后的Voronoi图，而是通过抛物线来”描绘“出Voronoi Edge和Vertex，是不是觉得非常神奇？我特地从邓老师的教学视频中，截取了一个Forutne算法的演示动画1，大家可以看看这个示例，从感官上体会一下抛物线的作用，以及整个算法大致的思路，最重要的是去感受一下这个算法的神奇之处，也是我们之前提到的：
如果说之前的算法都是把几何图形计算出来，那么基于Fortune的平面扫描算法是将Voronoi图”描绘“出来的，如同画家的画笔一样，一笔一笔地将Voronoi图勾勒出来
基于Fortune算法的Voronoi图示例
至于这个算法究竟是如何运用抛物线来计算Voronoi图的，我们就把这个问题留到下一节吧~
上一节：Voronoi图（二）：基本概念和性质
下一节：Voronoi图（四）：抛物线的妙用
系列汇总：塞尔达和计算几何 | Voronoi图详解文章汇总（含代码）
3. 参考资料
- Computational Geometry: Algorithms and Applications
- 计算几何 ⎯⎯ 算法与应用, 邓俊辉译，清华大学出版社
- 计算几何 | Computational Geometry
4. 免责声明
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/228145.html原文链接：https://javaforall.net
![linux定时执行sql文件[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
