沃罗诺伊图（Voronoi）

沃罗诺伊图（Voronoi）

- 三月 18, 2025

Voronoi图（又称泰森多边形、狄利克雷镶嵌）是一种基于空间划分的几何结构，由乌克兰数学家格奥尔吉·沃罗诺伊于20世纪初系统研究并命名。它将空间划分为多个区域，每个区域内的任意一点到该区域对应“种子点”的距离均小于到其他所有种子点的距离

1

10

40

。以下是详细介绍：

一、核心定义与特性

基本构成
- 种子点（Site）：空间中预先给定的一组离散点，作为划分区域的生成元。
- Voronoi单元（Cell）：每个种子点对应一个凸多边形区域，区域内所有点到该种子点的距离最短
  1
  
  51
  。
- Voronoi边（Edge）：相邻两个种子点的垂直平分线，边界上的点到这两个种子点的距离相等
  10
  
  17
  。
关键特性
- 空圆性：每个Voronoi单元的边界顶点是三个或更多种子点的外接圆圆心，且该圆内部不包含其他种子点
  1
  
  34
  。
- 对偶性：Voronoi图与Delaunay三角剖分互为对偶图。Delaunay三角网的边连接相邻种子点，而Voronoi图的边是Delaunay三角形外心的连线
  17
  
  45
  。
- 线性复杂度：平面上的Voronoi图顶点数不超过 $2 n - 5$ ，边数不超过 $3 n - 6$ （ $n$ 为种子点数）
  34
  。

二、生成方法与步骤

Voronoi图的生成通常基于Delaunay三角剖分，步骤如下：

构建Delaunay三角网
- 通过Bowyer-Watson算法等，将种子点连接为三角形网络，确保每个三角形的外接圆内不含其他种子点（空圆性）
  17
  
  45
  。
- 特性：避免生成过小的锐角，最大化三角形的最小角，保证网格质量
  1
  
  34
  。
计算外接圆圆心
- 对每个Delaunay三角形计算其外接圆圆心，这些圆心将成为Voronoi图的顶点
  17
  
  45
  。
连接相邻外心
- 遍历三角形链表，将相邻三角形的外心连接形成Voronoi边。边界区域的Voronoi边延伸为射线或垂直线
  1
  
  45
  。
处理边界
- 对于无相邻三角形的边，生成中垂线射线，确保所有区域闭合
  17
  
  45
  。

三、应用领域

Voronoi图因其空间划分的高效性和自然性，在多个领域广泛应用：

自然科学
- 地理学：划分气象站点的影响区域（如降雨量分布）
  1
  
  10
  。
- 生物学：模拟细胞结构、动物皮毛斑纹（如长颈鹿斑点）的形成
  10
  
  34
  。
工程与计算机科学
- 机器人路径规划：避开障碍物并找到最短路径
  17
  
  34
  。
- 计算机图形学：生成三维地形模型（如北京水立方的外立面设计）
  10
  
  25
  。
- 机器学习：作为k近邻算法（k-NN）的决策边界基础
  10
  
  34
  。
艺术与建筑
- 陶瓷裂纹设计：宋代官窑的冰裂纹模仿Voronoi图案
  10
  。
- 程序化生成：游戏地图和艺术图案的随机化生成
  10
  
  25
  。

四、算法复杂度与优化

时间复杂度
- Delaunay三角剖分的复杂度为 $O (n^{2})$ ，生成Voronoi图的整体复杂度与之相同
  17
  
  45
  。
- 构造下界为 $O (n \log n)$ ，可通过快速排序问题规约证明
  34
  。
优化技术
- 扫线算法：通过优先队列和事件调度提高效率
  17
  。
- 劳埃德松弛算法：迭代调整种子点位置，使Voronoi单元趋向均匀分布
  10
  
  34
  。

五、扩展与变体

高维Voronoi图
- 三维空间的Voronoi图用于材料科学（如晶体结构分析）和医学建模（如器官分割）
  25
  
  51
  。
有界Voronoi图
- 结合多面体边界约束，适用于有限空间内的路径规划（如室内导航）
  25
  。

总结

Voronoi图通过数学规则将空间划分为“势力范围”，兼具美学与实用性。其核心思想——最近邻划分——在自然界和人造系统中反复出现，成为连接几何、算法与应用的桥梁。如需代码实现，可参考基于Matlab或C#的Delaunay三角剖分工具

25

45

。

评论