Voronoi 图简介 | Baeldung中文网

1. 引言

在本教程中，我们将介绍 Voronoi 图（Voronoi Diagram）。这是一种在自然界中常见、在科学和工程中也具有广泛应用的数学结构，以俄罗斯数学家 Georgy Voronoi 的名字命名。它也被称为 Voronoi 镶嵌（tessellation）、Voronoi 分解（decomposition）或 Voronoi 分区（partition）。

无论使用哪种称呼，Voronoi 图的视觉特征都非常鲜明，很容易就能识别出来。我们将先通过图形建立直观认识，然后深入其背后的数学原理。

2. 定义

下图展示了在一个二维平面上随机分布的 40 个橙色点，以及它们对应的 Voronoi 图。图中由边界划分出的区域称为 Voronoi 单元（Voronoi Cells）：

plotcrop

可以看到，大多数橙色点都位于各自单元的中心位置。但每个单元的边界是根据周围点之间的距离来划分的，黑色线条表示的空间划分是精确的。

更进一步地说，如果我们在某个单元内部加入一个新点，那么这个点离该单元对应的原始点最近。也就是说，周围点越少，这个单元的面积就越大。

用数学语言来表达，可以写成如下形式：

对于给定的一组有限点集合 $ {p_1, p_2, \dots, p_n} $，其中每个点 $ p_k $ 都对应一个 Voronoi 单元 $ R_k $，该单元由平面上所有到 $ p_k $ 的距离小于或等于到其他任何点的距离的点组成。

3. 计算方法

现在我们已经了解了 Voronoi 图的定义，接下来探讨如何计算它。

有很多种算法可以完成这个任务，但最直观的一种方法是：先计算 Delaunay 三角剖分（Delaunay Triangulation），再通过它推导出 Voronoi 图。

3.1 Delaunay 三角剖分是什么？

Delaunay 三角剖分是基于原始点集构建的一组三角形，满足一个关键条件：

任意一个三角形的外接圆中不包含其他三角形的顶点。

举个例子，下图显示了 10 个黑点构成的 Delaunay 三角剖分结构。绿色点表示每个三角形外接圆的圆心：

Screenshot-from-2021-11-09-19-52-30

这些圆心信息对后续生成 Voronoi 图非常关键。

3.2 Voronoi 图与 Delaunay 三角剖分的关系

下图展示了 40 个点的 Voronoi 图（左）与对应的 Delaunay 三角剖分（右）对比：

plot

通过对比可以发现，每个 Delaunay 三角形的外接圆圆心，恰好对应 Voronoi 图中的一个顶点。而 Voronoi 图的边，就是相邻三角形之间圆心连线的结果。

因此，如果我们已经有了 Delaunay 三角剖分的结果，只需要连接相邻三角形的外心，就能得到 Voronoi 图的边。

3.3 如何计算 Delaunay 三角剖分？

一个常用的方法是使用 Bowyer-Watson 算法。该算法通过逐步插入点的方式构建 Delaunay 三角剖分。

算法流程如下：

✅ 算法步骤概述：

创建一个包围所有点的“超级三角形”，加入三角形列表。
对每个点进行插入操作：
- 遍历所有三角形，找出其外接圆包含当前点的那些三角形。
- 删除这些三角形，形成一个“空腔”。
- 收集空腔边界的边。
- 去除重复的边（即被两个三角形共享的边）。
- 利用这些边和当前点形成新的三角形。
最后移除包含超级三角形顶点的三角形。

✅ 伪代码实现：

algorithm BowyerWatson(pointList):
    // INPUT
    //    pointList = 一组需要三角剖分的点
    // OUTPUT
    //    返回包含 Delaunay 三角剖分结果的三角形列表

    创建一个包围所有点的超级三角形
    将超级三角形加入三角形列表

    for point in pointList:
        edgeList = 空集合

        for triangle in triangleList:
            if point 在 triangle 的外接圆内:
                标记 triangle 为无效
                将 triangle 的边加入 edgeList

        从 triangleList 中移除所有无效三角形

        for edge in edgeList:
            if edge 被其他三角形共享:
                从 edgeList 中移除 edge

        for edge in edgeList:
            用 edge 和 point 构建新三角形
            加入 triangleList

    从 triangleList 中移除包含超级三角形顶点的三角形

    return triangleList

⚠️ 性能说明：

该算法的复杂度为 $ O(n^2) $，因为每次插入新点时都要遍历所有三角形。但通过优化数据结构（如使用邻接表或哈希表），可以进一步提升性能。

4. 总结

本文通过图形化方式介绍了 Voronoi 图 及其与 Delaunay 三角剖分 的紧密关系。我们解释了如何通过 Delaunay 三角剖分来间接生成 Voronoi 图，并介绍了实现 Delaunay 三角剖分的常用算法 —— Bowyer-Watson 算法。

Voronoi 图在计算机图形学、地图生成、路径规划、模式识别等领域都有广泛应用。掌握其原理和实现方式，对解决实际问题非常有帮助。

Persistence

REST

Security