如何通过Delaunay triangulation获取Voronoi tessellation单元格连通性

Voronoi图和Delaunay三角剖分互为对偶图，二者的邻接关系直接对应：如果两个原始生成点在Delaunay三角剖分中存在公共边，那么这两个点对应的Voronoi单元格一定是连通的（共享一条Voronoi边），不需要额外计算单元格的几何相交关系，计算效率非常高。

实现步骤 #

• 基于你的原始生成点计算Delaunay三角剖分，scipy的scipy.spatial.Delaunay可以直接完成这个计算
• 遍历所有Delaunay三角面的三条边，去重后得到所有无向边，每条边的两个端点索引就是一对相邻Voronoi单元格的索引
• 整理成邻接表或者邻接矩阵，就得到了完整的连通关系

注意：你原来的代码里缺少import matplotlib.pyplot as plt的导入，运行时会报错，补充后即可正常显示Voronoi图。

完整可运行代码 #

import numpy as np
from scipy.spatial import Voronoi, voronoi_plot_2d, Delaunay
import matplotlib.pyplot as plt

# 你的原始生成逻辑
points = np.random.random((20, 2))
vor = Voronoi(points)

# 计算对应Delaunay三角剖分
tri = Delaunay(points)

# 初始化邻接集合，避免重复记录邻接关系
adj = [set() for _ in range(len(points))]
# 遍历所有Delaunay三角面的三条边
for simplex in tri.simplices:
    # 取出三角面的三个顶点索引，两两组合成边
    for i, j in [(0,1), (1,2), (2,0)]:
        p1, p2 = simplex[i], simplex[j]
        # 无向边双向记录
        adj[p1].add(p2)
        adj[p2].add(p1)

# 转换为普通列表格式，方便后续业务使用
adjacency_list = [list(s) for s in adj]

# 输出验证：打印第0个Voronoi单元格的相邻单元格索引
print("第0个Voronoi单元格的相邻单元格索引：", adjacency_list[0])

# 绘图验证
fig = voronoi_plot_2d(vor, show_vertices=False, line_colors='blue', line_width=2, line_alpha=0.6, point_size=20)
plt.title("Voronoi图及对应Delaunay三角剖分")
# 叠加Delaunay三角剖分的边，直观验证邻接关系
plt.triplot(points[:,0], points[:,1], tri.simplices, color='gray', linestyle='--', alpha=0.5)
plt.show()

结果说明 #

输出的adjacency_list索引和原始生成点points的索引一一对应，adjacency_list[i]中存储的所有值就是第i个Voronoi单元格的相邻单元格索引。

内容的提问来源于stack exchange，提问作者Natasha