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

Question

6

我目前正在尝试构建设备在运行期间覆盖的区域。这个过程的第一步似乎是构建覆盖区域的多边形。由于该模式不是标准形状，所以凸壳会通过跳到最大覆盖面积来夸大覆盖面积。

我找到了一篇论文，似乎涵盖了非凸壳生成的概念，但没有讨论如何在高级语言中实现它。 http://www.geosensor.net/papers/duckham08.PR.pdf 有没有人看到过构建非凸壳或凹壳的简单算法，或者任何可以实现相同结果的Python代码？

我已经尝试了凸壳，主要是qhull，并且使用了有限的边缘大小，但成功有限。此外，我注意到一些受许可证限制的库将无法分发，所以不幸的是那个方法行不通。还有更好的想法或菜谱吗？

- TelsaBoil

1

可能相关信息：http://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions - Gilead

1

问题定义清晰吗？您想要覆盖点的任何非凸壳体吗？还是有一些额外的限制条件？考虑三个顶点形成一个等边三角形，第四个点位于中心。至少存在三种可能的非凸壳体可以包围这些点。 - Adrian McCarthy

4

哇，所有这些不同的 StackExchange 网站确实很好地将问题移出了能够回答它们的人的视线范围。:( - dash-tom-bang

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Victor Liu · Accepted Answer

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

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