python - Python - 具有一些允许的内部点的凸壳

Question

我想制作一组 2D 点的凸包（在 python 中）。我找到了几个有用的例子，但我有一个额外的功能我想要我无法实现。我想要做的是创建凸包，但如果它们足够“接近”边界，则允许它拾取内部点。请参见下图 -> 如果 theta < x 度，则该内部点将添加到船体中。

正如我从我的想法和测试中发现的那样，显然这会使事情变得更加复杂。例如，如果添加了一个内部点，那么它可能会允许添加另一个更进一步的内部点。

速度在这里并不是一个真正的问题，因为我将使用的点数相对较少。我宁愿有一个更健壮的算法，而不是一个快速的算法。

我想知道是否有人知道任何这样的例子，或者可以指出我从哪里开始的正确方向。谢谢。

Answer 1

凹形船体可能是您正在寻找的东西，尽管据我所知它没有使用角度。LOCAL 项目使用的算法似乎使用了 k 个最近邻。

Answer 2

您可以首先计算凸包，然后围绕其边缘进行破坏，看看是否应该破坏任何边缘以包含内部点。

Answer 3

您正在寻找的概念可能是 alpha 形状。调整 alpha，您在凹壳中承认或多或少的点。查看用于 alpha 形状查找的 Edelsbrunner 算法。