如何提取矩形内的Voronoi顶点及Voronoi边与矩形的交点？

实现思路 #

• 用scipy.spatial.Voronoi生成全局Voronoi图
• 筛选坐标落在矩形[-1,10]×[-1,10]内的原始Voronoi顶点
• 遍历所有Voronoi边，判断边的端点是否跨出矩形边界，若跨边界则计算该边与矩形四条边的交点
• 整合内部顶点与边界交点，可视化验证结果

修改后的完整代码 #

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

# 定义矩形边界
x_min, x_max = -1, 10
y_min, y_max = -1, 10

# 生成随机种子点（可替换为自定义点集）
np.random.seed(42)
points = np.random.rand(20, 2) * 11 - 1  # 确保点落在[-1,10]范围内

# 生成Voronoi图
vor = Voronoi(points)

# 1. 筛选矩形内部的Voronoi顶点
interior_vertices = []
for vertex in vor.vertices:
    x, y = vertex
    if x_min < x < x_max and y_min < y < y_max:
        interior_vertices.append(vertex)
interior_vertices = np.array(interior_vertices)

# 2. 计算Voronoi边与矩形边界的交点
def segment_rectangle_intersection(seg_start, seg_end, rect):
    # rect参数格式: (x_min, x_max, y_min, y_max)
    x_min_r, x_max_r, y_min_r, y_max_r = rect
    intersections = []
    
    # 检查线段与矩形四条边的交点
    # 左边界x=x_min_r
    if (seg_start[0] < x_min_r and seg_end[0] > x_min_r) or (seg_start[0] > x_min_r and seg_end[0] < x_min_r):
        t = (x_min_r - seg_start[0]) / (seg_end[0] - seg_start[0])
        y = seg_start[1] + t * (seg_end[1] - seg_start[1])
        if y_min_r <= y <= y_max_r:
            intersections.append([x_min_r, y])
    # 右边界x=x_max_r
    if (seg_start[0] < x_max_r and seg_end[0] > x_max_r) or (seg_start[0] > x_max_r and seg_end[0] < x_max_r):
        t = (x_max_r - seg_start[0]) / (seg_end[0] - seg_start[0])
        y = seg_start[1] + t * (seg_end[1] - seg_start[1])
        if y_min_r <= y <= y_max_r:
            intersections.append([x_max_r, y])
    # 下边界y=y_min_r
    if (seg_start[1] < y_min_r and seg_end[1] > y_min_r) or (seg_start[1] > y_min_r and seg_end[1] < y_min_r):
        t = (y_min_r - seg_start[1]) / (seg_end[1] - seg_start[1])
        x = seg_start[0] + t * (seg_end[0] - seg_start[0])
        if x_min_r <= x <= x_max_r:
            intersections.append([x, y_min_r])
    # 上边界y=y_max_r
    if (seg_start[1] < y_max_r and seg_end[1] > y_max_r) or (seg_start[1] > y_max_r and seg_end[1] < y_max_r):
        t = (y_max_r - seg_start[1]) / (seg_end[1] - seg_start[1])
        x = seg_start[0] + t * (seg_end[0] - seg_start[0])
        if x_min_r <= x <= x_max_r:
            intersections.append([x, y_max_r])
    
    return np.array(intersections)

boundary_intersections = []
# 遍历所有Voronoi边（跳过无穷远边）
for ridge in vor.ridge_vertices:
    v1, v2 = ridge
    if v1 == -1 or v2 == -1:
        continue
    seg_start = vor.vertices[v1]
    seg_end = vor.vertices[v2]
    # 计算当前边与矩形的交点
    inters = segment_rectangle_intersection(seg_start, seg_end, (x_min, x_max, y_min, y_max))
    if len(inters) > 0:
        boundary_intersections.extend(inters)
boundary_intersections = np.array(boundary_intersections)

# 3. 可视化结果
fig, ax = plt.subplots(figsize=(8,8))
# 绘制原始Voronoi图
voronoi_plot_2d(vor, ax=ax, show_vertices=False, line_colors='gray', line_width=1)
# 绘制矩形边界
rect = plt.Rectangle((x_min, y_min), x_max-x_min, y_max-y_min, fill=False, edgecolor='black', linewidth=2)
ax.add_patch(rect)
# 标记内部Voronoi顶点（蓝色）
if len(interior_vertices) > 0:
    ax.scatter(interior_vertices[:,0], interior_vertices[:,1], c='blue', s=50, zorder=5, label='内部顶点')
# 标记边界交点（红色，对应附图中的红圈）
if len(boundary_intersections) > 0:
    ax.scatter(boundary_intersections[:,0], boundary_intersections[:,1], c='red', s=50, zorder=5, label='边界交点')
ax.set_xlim(x_min-0.5, x_max+0.5)
ax.set_ylim(y_min-0.5, y_max+0.5)
ax.legend()
plt.show()

# 输出结果
print("内部Voronoi顶点:\n", interior_vertices)
print("\n边界交点:\n", boundary_intersections)

关键说明 #

• 内部顶点筛选：默认严格判断顶点在矩形内部，若需要包含边界上的点，可将判断条件中的<改为<=
• 边界交点计算：通过线段跨边判断+线性插值计算交点，确保交点落在矩形的四条边上
• 可视化验证：用蓝色标记内部顶点，红色标记边界交点，直观确认结果准确性

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