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

Question

我目前正在试着在一个操作周期内构建一个设备覆盖的区域。 这个过程的第一步似乎是构建覆盖区域的多边形。 由于图案不是一个标准的形状，凸出的外壳通过跳到最大的覆盖区域来夸大覆盖面积。在

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

有没有人见过构造非凸壳或凹壳的直接算法，或者可能有任何python代码来实现相同的结果？在

我尝试过凸壳主要是qhull，有限的边缘尺寸和有限的成功。 另外，我也注意到一些许可的库将无法分发，因此不幸的是，这是不可能的。 有更好的主意或食谱吗？在

Answer 1

你可以试着看看阿尔法形状。CGAL库可以计算它们。在

编辑：我看到你链接的论文引用了alpha形状，还有一个算法列表。这对你来说还不够高吗？由于您将python列为一个标记，我确信python中有Delaunay三角剖分库，我认为这是实现该算法最困难的部分；您只需确保可以修改生成的三角剖分输出。边界查询函数可以用关联数组实现。在