你如何从一系列点生成非凸包？ [英] How do you generate the non-convex hull from a series of points?

问题描述

目前我正试图在一段运营期内构建设备所覆盖的区域。
此过程的第一步似乎是构建覆盖区域的多边形。
由于图案不是标准形状，因此通过跳到尽可能最大的覆盖区域，凸面可以夸大覆盖区域。

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

有没有人看到过构造非凸包或凹包或者任何python代码以获得相同结果的直接算法？

我尝试过凸包，主要是qhull，边缘有限，成功有限。
另外我也注意到一些不能分发的许可库，所以很不幸。
任何更好的想法或食谱？

解决方案

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

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

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?

解决方案

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.

这篇关于你如何从一系列点生成非凸包？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！