如何筛选可“逃逸”点集的有效圆？Delaunay三角优化需求

问题分析 #

当前使用scipy.spatial.Delaunay(golden_spots)结合DT.find_simplex(circle_centers)的方案，本质是判断圆心是否处于金色点集的凸包内部。但该逻辑会误将圆心在凸包外、或圆可延伸至凸包外的可逃逸圆标记为需排除对象，同时无法精准识别凸包内部真正被点集封闭的圆。

解决方案思路 #

核心逻辑拆分两步，分别覆盖外围可逃逸圆和凸包内部圆的判断：

• 判定外围可逃逸圆：判断圆是否能触及金色点集凸包的外部（包括圆心在凸包外，或圆心在凸包内但圆半径足够大到超出凸包），这类圆直接判定为符合“可逃逸”条件。
• 判定凸包内部可逃逸圆：利用Voronoi图，判断凸包内部的圆心所在Voronoi单元是否为无限单元（即单元连通到凸包外部）。无限单元对应的圆可向外部延伸，属可逃逸；有限单元则表示被点集完全封闭，需排除。

代码实现 #

依赖库导入 #

import numpy as np
from scipy.spatial import ConvexHull, Voronoi, KDTree

步骤1：筛选可触及凸包外部的圆 #

# 替换为你的实际数据
golden_spots = np.array([[x1,y1], [x2,y2], ...])  # 金色点坐标数组
circle_centers = np.array([[cx1,cy1], [cx2,cy2], ...])  # 圆心坐标数组
radius = 5.0  # 同图内圆的统一半径

# 计算金色点集的凸包
hull = ConvexHull(golden_spots)

# 计算每个圆心到凸包的距离（点在凸包内时为点到凸包边界的最短距离，外部则为0）
def calc_dist_to_hull(point, hull):
    dists = hull.equations[:,:-1].dot(point) + hull.equations[:,-1]
    min_dist = np.min(dists)
    return max(-min_dist, 0.0)

hull_distances = np.array([calc_dist_to_hull(center, hull) for center in circle_centers])
# 圆能触及凸包外部的条件：距离<=半径
can_escape_outer = hull_distances <= radius

步骤2：筛选凸包内部可逃逸圆 #

# 处理完全在凸包内部的圆（无法触及凸包外部的圆）
inner_centers = circle_centers[~can_escape_outer]

# 构建金色点集的Voronoi图
vor = Voronoi(golden_spots)
# 标记所有无限Voronoi单元（连通到外部）
infinite_region_flags = [-1 in region for region in vor.regions]

# 找到每个内部圆心最近的金色点，映射到对应的Voronoi单元
kdtree = KDTree(golden_spots)
nearest_point_idx = kdtree.query(inner_centers, k=1)[1]
point_regions = [vor.point_region[idx] for idx in nearest_point_idx]

# 判断内部圆心所在单元是否为无限单元（可逃逸）
can_escape_inner = np.array([infinite_region_flags[reg] for reg in point_regions])

合并结果并结合第一个条件 #

# 合并两类可逃逸圆的索引
escapable_indices = np.where(can_escape_outer)[0].tolist()
escapable_indices += np.where(~can_escape_outer)[0][can_escape_inner].tolist()

# 结合第一个条件（金色点不在圆内）的筛选结果（假设已完成该条件的mask：no_golden_inside）
final_keep_indices = [idx for idx in escapable_indices if no_golden_inside[idx]]
final_valid_circles = circle_centers[final_keep_indices]

关键细节说明 #

• 凸包距离计算：确保即使圆心在凸包内，只要圆的边界能超出凸包，就判定为可逃逸，避免误判大半径的外围圆。
• Voronoi单元判断：无限单元意味着该区域存在通往点集外部的路径，对应圆可向外“逃逸”；有限单元则完全被点集包围，符合需排除的封闭空间特征。

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