我想做一个二维点集的凸包（在python中）。我已经找到了一些有帮助的例子，但我有一个额外的功能，我希望我还没有能够实现我想做的是创建凸面外壳，但允许它拾取内部点，如果它们足够“接近”边界。请看下面的图片->如果θ很明显，这会让事情变得更复杂，正如我从我的想法和测试中发现的那样。例如，如果添加了一个内部点，则可能允许添加另一个内部点。
在这里，速度并不是一个真正的问题，因为我将要处理的点数相对较少。我宁愿有一个更稳健的算法，而不是一个快速的算法。
我想知道是否有人知道任何这样的例子，或能给我指出正确的方向，从哪里开始。谢谢。
最佳答案
Concave hull可能是你要找的，尽管据我所知它没有使用角度。the LOCAL project使用的算法似乎使用k个最近邻。