Python - 带有可接受内部点的凸包

Question

我想用Python来制作一组二维点的凸包。我找到了一些有用的例子，但我想要一个额外的功能，这个功能我还没能实现。我想创建一个凸包，但希望它能把一些靠近边界的内部点也纳入进去。看下面的图片——如果角度小于x度，那么这个内部点就会被加入到凸包中。

显然，这样做会让事情变得有点复杂，我在思考和测试中发现了这一点。例如，如果一个内部点被加入，那么可能会允许另一个更内部的点也被加入。

速度在这里并不是主要问题，因为我处理的点的数量相对较少。我更希望有一个更稳健的算法，而不是一个快速的算法。

我在想有没有人知道这样的例子，或者能给我指个方向，让我知道从哪里开始。谢谢。

Answer 1

你可能在寻找的概念是“alpha形状”。通过调整alpha值，你可以控制在你的凹形外壳中包含更多或更少的点。想了解alpha形状的寻找方法，可以看看Edelsbrunner算法。

Answer 2

你可以先计算出凸包，然后再把边缘处理得圆滑一些，看看有没有边缘需要被打断，以便包含一个内部点。

Answer 3

你可能在找的是凹包络，不过我知道的情况是，它并没有使用角度。LOCAL项目使用的算法似乎是基于k个最近邻的方式。