限制SciPy Voronoi迭代边界，防止点溢出指定区域

问题核心是SciPy的Voronoi生成的是无边界的无限区域，边界点对应的Voronoi区域包含无限远的顶点，直接取顶点均值会导致点扩散到目标区域外。要在[-0.5,0.5]矩形内实现Lloyd迭代，必须裁剪每个Voronoi区域到目标边界内，再计算裁剪后区域的质心作为下一轮的点位置。

解决方案步骤 #

• 定义目标边界为轴对齐矩形[-0.5, 0.5] × [-0.5, 0.5]
• 将每个Voronoi区域转换为多边形，与目标边界求交集得到有限区域
• 计算裁剪后多边形的质心，作为迭代后的点位置
• 重复迭代直到点分布稳定

修改后的代码 #

需要用到shapely库处理多边形操作，先安装：pip install shapely

import numpy as np
from scipy.spatial import Voronoi, voronoi_plot_2d
from shapely.geometry import Polygon
import matplotlib.pyplot as plt

if __name__ == '__main__':
    # 初始点：[-0.5,0.5]内随机生成100个点
    points = np.random.rand(100, 2) - 0.5
    # 定义目标边界多边形
    boundary = Polygon([(-0.5, -0.5), (-0.5, 0.5), (0.5, 0.5), (0.5, -0.5)])

    for i in range(60):
        voronoi = Voronoi(points)
        new_points = []
        
        for reg_idx in voronoi.point_region:
            region = voronoi.regions[reg_idx]
            # 处理包含无限顶点的区域
            if -1 in region:
                finite_vertices = [voronoi.vertices[v] for v in region if v != -1]
                if not finite_vertices:
                    new_points.append(points[len(new_points)])
                    continue
                vor_poly = Polygon(finite_vertices)
                clipped_poly = vor_poly.intersection(boundary)
            else:
                # 处理有限区域，同时裁剪防止微小溢出
                vor_poly = Polygon([voronoi.vertices[v] for v in region])
                clipped_poly = vor_poly.intersection(boundary)
            
            # 计算裁剪后区域的质心
            if not clipped_poly.is_empty:
                centroid = clipped_poly.centroid.coords[0]
                new_points.append(centroid)
            else:
                new_points.append(points[len(new_points)])
        
        points = np.array(new_points)

    # 绘制结果，限制显示范围
    fig = voronoi_plot_2d(Voronoi(points), show_vertices=False, line_colors='orange', 
                          line_width=2, line_alpha=0.6, point_size=20)
    plt.xlim(-0.55, 0.55)
    plt.ylim(-0.55, 0.55)
    plt.show()

关键细节说明 #

• 多边形裁剪：用shapely的intersection方法自动处理Voronoi区域和边界的交集，无论原区域是有限还是无限，都能得到符合边界要求的有效区域
• 质心计算：裁剪后的多边形可能是复杂形状，shapely的centroid方法能准确计算其几何中心，这是Lloyd算法实现点均匀分布的核心步骤
• 稳定性处理：对交集为空的极端情况保留原点位，避免点数量减少，保证迭代过程的稳定性

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