Python - 具有一些允许的内点的凸包
我想制作一组 2D 点的凸包（在 python 中）。我发现了几个有帮助的示例，但我有一个我想要但无法实现的额外功能。我想要做的是创建凸包，但如果内部点足够“接近”边界，则允许它拾取内部点。见下图->如果 θ < x 度，然后将该内部点添加到船体中。
显然，这会使事情变得更加复杂，正如我从我的想法和测试中发现的那样。例如，如果添加一个内部点，那么它可能允许添加另一个进一步的内部点。
速度在这里并不是真正的问题，因为我要处理的点的数量相对较小。我宁愿有一个更强大的算法，而不是一个快速的算法。
我想知道是否有人知道任何这样的例子，或者可以为我指出从哪里开始的正确方向。谢谢。
I'd like to make a convex hull of a set of 2D points (in python). I've found several examples which have helped, but I have an extra feature I'd like that I haven't been able to implement. What I want to do is create the convex hull but allow it to pick up interior points if they are sufficiently "close" to the boundary. See the picture below -> if theta < x degrees, then that interior point gets added to the hull.
Obvious this can make things a bit more complex, as I've found out from my thoughts and tests. For example, if an interior point gets added, then it could potentially allow another further interior point to be added.
Speed is not really a concern here as the number of points I'll be working with will be relatively small. I'd rather have a more robust algorithm then a quick one.
I'm wondering if anyone knows of any such example or could point me in the right direction of where to start. Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
不过，凹形船体可能就是您想要的据我所知，它不使用角度。 LOCAL 项目 使用的算法似乎使用 k 个最近邻。
Concave hull might be what you're looking for, though it doesn't use an angle as far as I know. The algorithm that the LOCAL project uses seems to use k nearest neighbours.
您可以首先计算凸包，然后破坏其边缘，看看是否应该破坏任何边缘以包含内部点。
You could first compute the convex hull, and then ruin round the edges of that seeing if any of the edges should be broken to include an interior point.
您正在寻找的概念可能是阿尔法形状。调整 alpha，您会在凹壳中承认或多或少的点。 查看 Edelsbrunner 算法以查找 alpha 形状。
The notion you are looking for may be alpha-shape. Tuning alpha, you admit more or less points in your concave hull. Look at Edelsbrunner algorithm for alpha-shape finding.