编辑“︁Voronoi图”︁（章节）

== 构建方法 ==

Voronoi图可以通过多种算法构建，包括：

1. '''增量法'''（Fortune算法）：一种高效的扫描线算法，时间复杂度为 <math>O(n \log n)</math>。
2. '''分治法'''：将点集递归划分为子集，合并子Voronoi图。
3. '''Delaunay三角剖分转换法'''：利用Delaunay三角剖分的对偶性生成Voronoi图。

=== Fortune算法示例 ===
以下是一个简化的Python实现（使用 `scipy.spatial` 库）：

<syntaxhighlight lang="python">
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt

# 输入：一组二维点
points = [[0, 0], [1, 2], [2, 1], [3, 3], [4, 0]]

# 计算Voronoi图
vor = Voronoi(points)

# 绘制结果
fig = voronoi_plot_2d(vor)
plt.plot(points[:, 0], points[:, 1], 'ko')  # 绘制站点
plt.show()
</syntaxhighlight>

'''输出说明'''：代码生成一个Voronoi图，其中黑色圆点为输入站点，多边形为对应的Voronoi区域。