如何从一系列点生成非凸包？

Question

我现在正在尝试计算一个设备在运行期间覆盖的区域。 这个过程的第一步似乎是构建一个覆盖区域的多边形。 由于这个覆盖的形状不是标准的，所以用凸包来表示会夸大覆盖的面积，因为它会跳到可能的最大覆盖区域。

我找到了一篇论文，似乎讨论了非凸包生成的概念，但没有关于如何在高级语言中实现这个的讨论。 http://www.geosensor.net/papers/duckham08.PR.pdf

有没有人见过简单的算法来构建非凸包或凹包，或者有没有什么Python代码可以实现同样的效果？

我尝试过使用凸包，主要是qhull，边缘大小有限，效果也不太理想。 另外，我注意到一些有许可证的库是不能分发的，所以这就不行了。 有没有更好的主意或者参考资料？

Answer 1

你可以试着了解一下Alpha Shapes（阿尔法形状）。CGAL这个库可以用来计算它们。

编辑: 我看到你链接的论文提到了阿尔法形状，并且还有算法的列表。这个内容对你来说是不是不够深入呢？因为你提到过Python这个标签，我相信在Python中有Delaunay三角剖分的库，我觉得这可能是实现这个算法中最难的部分；你只需要确保能够修改得到的三角剖分结果。边界查询功能可能可以用关联数组来实现。