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

Question

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

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

有没有人看到一个简单的算法来构造一个非凸包或凹包，或者可能是任何python代码来实现相同的结果？

我尝试过主要是qhull的凸包，其边缘尺寸有限，但成功率有限。另外，我注意到有些许可库将无法分发，因此很遗憾，这些都不在话下。还有更好的主意或菜谱吗？

Answer 1

您可以尝试研究Alpha形状。CGAL库可以计算它们。

编辑
：我看到您链接的论文引用了alpha形状，并且还列出了算法。那还不够高吗？自从您将python列为标签以来，我确定Python中有Delaunay三角剖分库，我认为这是实现算法最困难的部分。您只需要确保可以修改生成的三角测量输出即可。边界查询功能可能可以通过关联数组来实现。