是否存在可指定排除点的concave-hull（凹包）算法？

核心可行性结论 #

可以通过动态调整alpha参数的Alpha Shapes方法实现你要求的功能，且该方法天然适配你「从凸包出发逐步切除多余区域、尽可能减少边数」的需求。

Alpha参数逻辑 #

alpha值为探测圆半径的倒数，参数变化的效果遵循以下规律：

• alpha = 0时，生成的形状就是输入点集的凸包，边数最少，覆盖范围最大
• alpha逐渐增大时，形状边界会逐步向内凹陷，切除凸包中没有点分布的多余区域，边数随之增加
• alpha增大到临界值后，形状会碎化为离散的点集

动态调参实现逻辑 #

你可以通过二分搜索法快速找到满足约束的最优alpha值，兼顾「包含所有内部点、排除所有外部点」的硬约束和「边数最少」的优化目标：

1. 确定初始参数范围
   • 左边界alpha_low = 0，对应凸包，必然可以包含所有内部点
   • 右边界alpha_high取足够大的初始值（可先测试一个能让所有外部点都落在形状外的数值即可）
2. 迭代搜索最优alpha
   • 取中间值alpha_mid = (alpha_low + alpha_high) / 2，生成对应多边形
   • 校验两个约束条件：
     • 若存在内部点落在多边形外：说明alpha过大，形状收缩过度，将alpha_high = alpha_mid
     • 若存在外部点落在多边形内：说明alpha过小，形状过于宽松，将alpha_low = alpha_mid
   • 迭代到参数范围收敛到你可接受的精度为止
3. 输出结果
   收敛后得到的alpha值生成的多边形，就是满足约束的边数最少的凹多边形。

Python实现参考代码 #

import alphashape
from shapely.geometry import Point

# 输入数据：inner_pts为内部点集，outer_pts为外部点集，均为[[x1,y1], [x2,y2],...]格式
inner_pts = ...
outer_pts = ...

# 二分参数初始值
alpha_low = 0.0
alpha_high = 100.0  # 可根据你的点集坐标范围调整
eps = 1e-6  # 收敛精度

for _ in range(100):  # 最多迭代100次，精度足够
    alpha_mid = (alpha_low + alpha_high) / 2
    # 生成alpha shape多边形
    polygon = alphashape.alphashape(inner_pts, alpha_mid)
    # 校验约束1：所有内部点都在多边形内
    all_inner_in = all(polygon.contains(Point(p)) for p in inner_pts)
    # 校验约束2：所有外部点都在多边形外
    all_outer_out = all(not polygon.contains(Point(p)) for p in outer_pts)
    
    if all_inner_in and all_outer_out:
        # 满足约束，尝试更小的alpha（减少边数）
        alpha_high = alpha_mid
    elif not all_inner_in:
        # 内部点漏了，alpha太大，要缩小
        alpha_high = alpha_mid
    else:
        # 外部点进来了，alpha太小，要放大
        alpha_low = alpha_mid

# 最终最优多边形
final_polygon = alphashape.alphashape(inner_pts, alpha_high)

注意事项 #

如果迭代后仍无法找到满足约束的alpha值，说明内外点集存在边界冲突（比如存在相邻的内外点距离过近），此时可以切换为你最初设想的「凸包逐步切割」方案：先生成内部点的凸包，每次找到落在凸包内的外部点，用半平面切除包含该外部点的多余区域，直到所有外部点都被排除为止，该方案也可以保证最终多边形边数最少。

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