如何从一系列点生成非凸包？
我目前正在尝试构建设备在运行期间覆盖的区域。 此过程的第一步似乎是构建覆盖区域的多边形。 由于图案不是标准形状，凸包会通过跳跃到可能的最大覆盖区域来夸大覆盖区域。
我发现一篇论文似乎涵盖了非凸包生成的概念，但没有讨论如何在高级语言中实现这一概念。 http://www.geosensor.net/papers/duckham08.PR.pdf
有没有人见过构造非凸壳或凹壳的直接算法，或者可能有任何Python代码来实现相同的结果？
我尝试过凸包，主要是 qhull，其边缘尺寸有限，但成功有限。 我还注意到一些许可的库将无法分发，所以不幸的是，这不可行。 有更好的想法或食谱吗？
I am currently trying to construct the area covered by a device over an operating period.
The first step in this process appears to be constructing a polygon of the covered area.
Since the pattern is not a standard shape, convex hulls overstate the covered area by jumping to the largest coverage area possible.
I have found a paper that appears to cover the concept of non-convex hull generation, but no discussions on how to implement this within a high level language.
http://www.geosensor.net/papers/duckham08.PR.pdf
Has anyone seen a straight forward algorithm for constructing a non-convex hull or concave hull or perhaps any python code to achieve the same result?
I have tried convex hulls mainly qhull, with a limited edge size with limited success.
Also I have noticed some licensed libraries that will not be able to be distributed, so unfortunately thats off the table.
Any better ideas or cookbooks?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以尝试研究 Alpha Shapes。 CGAL 库可以计算它们。
编辑：我看到您链接的论文引用了 alpha 形状，并且还有一个算法列表。这对你来说还不够高吗？既然你将 python 列为标签，我确信 Python 中有 Delaunay 三角测量库，我认为这是实现该算法最难的部分；您只需要确保可以修改生成的三角测量输出。边界查询函数可能可以用关联数组来实现。
You might try looking into Alpha Shapes. The CGAL library can compute them.
Edit: I see that the paper you linked references alpha shapes, and also has an algorithm listing. Is that not high level enough for you? Since you listed python as a tag, I'm sure there are Delaunay triangulation libraries in Python, which I think is the hardest part of implementing the algorithm; you just need to make sure you can modify the resulting triangulation output. The boundary query functions can probably be implemented with associative arrays.