Caleb's Space

Appearance

「计算几何」Fortune 算法生成维诺图（Voronoi Diagram）

Published at:

问题背景 ​

给定下面这个问题

假如你在城市里想找最近的邮局，怎么做最快？

这是一个经典的最近邻查询问题。几何化地说，给定平面上一组点，我们希望构造一个结构，能在查询时快速返回“离我最近的那个点”。这就是所谓的 Post Office Problem。然而，暴力搜索每次都遍历所有点，效率太低。我们需要一种预处理 + 快速查询的结构。

维诺图（Voronoi Diagram） ​

定义 ​

  • 设 为平面上的 个站点。
  • 对于每个站点 ，其 Voronoi 单元（cell）定义为：
  • Voronoi 图 是由所有 Voronoi 单元 对平面进行划分所得到的平面细分。

一些观察 ​

  1. 共线退化
    若所有站点共线，则 退化为 条平行直线（或平行带）。

  2. 凸性
    由半平面交集可得：

    其中 是以 为端点的垂直平分线所界定、包含 的开半平面。因此每个 Voronoi 单元都是凸的。

  3. 边与顶点

    • Voronoi 边缘由相邻站点对的垂直平分线的段或半线组成，任一点落在边上时到两个站点距离相等。
    • Voronoi 顶点是同时与至少三个站点等距的点，即空圆（圆心不含其他站点）的圆心。若站点处于一般位置（无四点共圆），则每个顶点恰由三个单元相交而成。

  4. 无界单元与凸包
    仅当站点是凸包 的顶点时，其对应的 Voronoi 单元才是无界的；其余单元均为有界多边形。

  5. 组合复杂度
    对于 ， 最多包含 条边和 个顶点，这一上界可由平面图的欧拉公式推得。

Fortune 算法 ​

核心思想 ​

Fortune 算法利用自上而下的平面扫描线（sweep line）思路，以 时间高效构造 Voronoi 图。扫描线算法的思想可以参考上一篇博客 「计算几何」扫描线算法与应用--线段交点问题。

如果观察 Voronoi 图的定义，当扫描线 从上向下移动到某个位置 时，任意点 的最近站点可能是已扫描的站点，也可能是尚未扫描到的站点。但只要 到已扫描站点 的距离 不大于它到扫描线的距离 ，即

那么 无论如何都比任何未扫描的站点更接近 ，其所属的 Voronoi 区域已经可以确定。满足该不等式的点集恰好是以 为准线的开口向下抛物线内部 。对所有已扫描站点分别得到这样的抛物线，抛物线的上包络即构成了“海滩线”（Beach Line），将平面分为“已定区”（海滩线以上）和“待定区”（海滩线以下）；由于其形状酷似海岸线，故得名海滩线 。如下图所示，扫描线在当前位置时，海滩线（橙色曲线）之上区域的 Voronoi 归属已锁定，之下区域则需继续扫描新站点才能确定。

算法流程 ​

事件列表如下：

  1. 站点事件（Site Event）
    当 扫描到新站点 时，插入一个新的抛物线弧，将原有弧分裂为三段，生成新的断点并开始追踪对应 Voronoi 边
  2. 圆事件（Circle Event）
    当三个相邻抛物线弧对应的站点共圆，最低点处触发圆事件。该事件导致中间弧消失，其消失位置即为一个 Voronoi 顶点 。

需要借助的数据结构如下：

  • 事件队列 ：按事件的 坐标排序，存储所有站点事件与待处理圆事件。
  • 状态结构 ：叶结点存储抛物线弧、内部结点存储断点；采用平衡二叉树，实现 的插入、删除和邻居查找。
  • DCEL（Doubly‐Connected Edge List）：记录正在构造的 Voronoi 边和顶点，每个断点关联一条半边，事件发生时更新边表。关于 DCEL 可以参考这一篇文章「计算几何」使用双向链接边表 DCEL 表示平面划分。

因此，可以给出下面的代码伪代码：

VoronoiDiagram(P):

  1. 将所有站点按 y 坐标插入事件队列
  2. 初始化空状态结构 和空 DCEL
  3. while 非空 do:
    • 从 中取出一个事件 e
    • if e 是站点事件 :
      • HandleSiteEvent()
    • else:
      • HandleCircleEvent()

HandleSiteEvent()

  1. 在 中查找垂直于 的弧 。若 曾登记圆事件，则将其移出 。
  2. 将 分裂成三段，新段属于 的抛物线插入中间，更新两侧断点并在 DCEL 中创建对应半边。
  3. 检测左右相邻三弧是否共圆，若是则将新圆事件加入 并建立指针。

HandleCircleEvent()

  1. 从 中删除对应弧 ，更新相邻断点位置。
  2. 移除所有与 相关的圆事件。
  3. 将圆心加入 DCEL 作为顶点，创建两条新半边并链接。
  4. 检测新相邻三弧是否生成圆事件，若是则插入 并建指针 。

复杂度分析 ​

时间：共处理 次站点事件和 次圆事件，每次事件在 和 上做 操作，总耗时 。

空间： 均需 空间，总空间 。

参考资料 ​

M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed. Berlin, Germany: Springer, 2008, ISBN 978-3-540-77973-5.