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

Question

我目前正在尝试构 build 备在运行期间覆盖的区域。此过程的第一步似乎是构建覆盖区域的多边形。由于图案不是标准形状，凸包通过跳到可能的最大覆盖区域来夸大覆盖区域。

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

有没有人见过用于构造非凸包或凹包的直接算法或者任何 python 代码来实现相同的结果？

我尝试过主要是 qhull 的凸包，边缘尺寸有限，但效果有限。我还注意到一些无法分发的许可库，所以不幸的是，这不在讨论之列。有更好的想法或食谱吗？

Answer 1

您可以尝试查看 Alpha Shapes。 CGAL 库可以计算它们。

编辑:我看到您链接的论文引用了 alpha 形状，并且还有一个算法列表。这对你来说还不够高吗？既然你把 python 列为一个标签，我确定 Python 中有 Delaunay 三角剖分库，我认为这是实现算法最难的部分；您只需要确保可以修改生成的三角测量输出。边界查询功能可能可以用关联数组来实现。