基于scipy.spatial.Voronoi的任意形状区域沃罗诺伊图实现

我们需要计算区域沃罗诺伊图（Area Voronoi Diagram）而非点沃罗诺伊图（Point Voronoi Diagram）——目标图形形状复杂，点沃罗诺伊图无法适配需求。目前的近似实现流程分为三步：

• 提取图形轮廓上的点集
• 基于这些点计算点沃罗诺伊图
• 删除由同一图形轮廓点生成的沃罗诺伊边

其中前两步用scipy.spatial.Voronoi就能轻松完成，核心问题是第三步：如何在不自行实现沃罗诺伊算法的前提下，识别并删除同一图形轮廓点生成的边。下面是具体的解决方案：

核心思路 #

1. 给轮廓点打归属标签
   为每个图形的轮廓点分配唯一的标识（比如整数ID），用一个和点集长度一致的数组存储所有点的归属标签。比如有两个图形，图形A的所有轮廓点标签为0，图形B的为1。

2. 解析Voronoi对象的边关联信息
   scipy.spatial.Voronoi生成的对象中，ridge_points属性是关键：它是一个二维数组，每一行的两个元素对应一条沃罗诺伊边的两个生成点的索引。比如ridge_points[i] = [p_idx1, p_idx2]，表示这条边由索引为p_idx1和p_idx2的两个点共同生成。

3. 过滤同一图形生成的边
   遍历所有沃罗诺伊边，检查每条边对应的两个生成点的归属标签：

   • 如果两个点的标签相同，说明这条边是同一图形的轮廓点生成的，直接标记为待删除
   • 如果标签不同，则保留这条边

代码示例 #

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

# 模拟两个图形的轮廓点集合
shape0_points = np.random.rand(20, 2) * 0.5  # 图形0的轮廓点，分布在左下方
shape1_points = np.random.rand(20, 2) * 0.5 + [0.5, 0.5]  # 图形1的轮廓点，分布在右上方

# 合并所有点并生成归属标签
all_points = np.vstack([shape0_points, shape1_points])
labels = np.array([0]*20 + [1]*20)  # 前20个点属于图形0，后20个属于图形1

# 计算点沃罗诺伊图
vor = Voronoi(all_points)

# 筛选出不同图形点生成的有效边
valid_ridge_indices = []
for idx, (p1, p2) in enumerate(vor.ridge_points):
    if labels[p1] != labels[p2]:
        valid_ridge_indices.append(idx)

# 可视化结果
plt.figure(figsize=(8, 8))
# 绘制原始轮廓点
plt.scatter(shape0_points[:, 0], shape0_points[:, 1], c='#ff4444', s=30, label='Shape 0')
plt.scatter(shape1_points[:, 0], shape1_points[:, 1], c='#4444ff', s=30, label='Shape 1')
# 绘制有效沃罗诺伊边
for ridge_idx in valid_ridge_indices:
    vertices = vor.ridge_vertices[ridge_idx]
    if -1 not in vertices:  # 排除指向无穷远的边
        plt.plot(vor.vertices[vertices, 0], vor.vertices[vertices, 1], 'k-', linewidth=1)
plt.legend()
plt.axis('equal')
plt.show()

注意事项 #

• 如果目标图形有多个，只需要扩展标签数组即可，逻辑完全通用
• 对于包含无穷远顶点的边（ridge_vertices中包含-1），可以根据需求决定是否保留——如果是封闭的区域沃罗诺伊图，通常需要剔除这类边
• 轮廓点的密度会影响近似效果，点越密集，区域沃罗诺伊图的精度越高

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