是否有有效的算法来生成 2D 凹壳？

https://stackoverflow.com/questions/83593

01-07-2019
|

题

拥有 GIS 文件（城市地图）中的一组（2D）点，我需要生成定义该地图（其边界）“轮廓”的多边形。其输入参数将是点集和“最大边长”。然后它将输出相应的（可能是非凸的）多边形。

到目前为止，我发现的最佳解决方案是生成 Delaunay 三角形，然后删除长于最大边长的外部边。当所有外部边缘都比这短之后，我只需删除内部边缘并得到我想要的多边形。问题是，这非常耗时，我想知道是否有更好的方法。

解决方案

这论文讨论了 高效生成简单多边形，用于表征平面上一组点的形状 并提供了算法。还有一个使用相同算法的 Java 小程序这里.

其他提示

我们实验室的一位前学生在他的博士论文中使用了一些适用的技术。我相信其中之一称为“阿尔法形状”，并在以下论文中引用：

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

该论文提供了一些您可以遵循的进一步参考资料。

伙计们这里声称开发了一种 k 最近邻方法来确定一组点的凹包，其行为“在点的数量上几乎呈线性”。遗憾的是他们的论文似乎受到很好的保护，你必须询问他们为了它。

这是一个很好的参考资料集其中包括上述内容，可能会引导您找到更好的方法。

答案对其他人来说可能仍然很有趣：一个人可以申请一个 行进方阵算法的变体, ，应用 (1) 在凹形外壳内，以及 (2) 然后应用（例如3）不同秤这取决于点的平均密度。比例需要是彼此的整数倍，这样您就可以构建一个可用于高效采样的网格。这允许快速找到空样本=正方形、完全位于点“簇/云”内的样本以及介于两者之间的样本。然后，后一类可用于轻松确定代表凹壳一部分的折线。

这种方法中的一切都是线性的，不需要三角测量，它不使用 alpha 形状，并且它与此处描述的商业/专利产品不同（ http://www.concavehull.com/ )

一个简单的解决方案是沿着多边形的边缘行走。给定连接点 P0 和 P1 的边界上的当前边，边界 P2 上的下一个点将是具有最小可能 A 的点，其中

H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength

然后你设置

P0 <- P1
P1 <- P2

并重复，直到回到起点。

这仍然是 O(N^2)，因此您需要对点列表进行一些排序。如果您对点进行排序（例如距离城市质心的方位），则可以限制每次迭代时需要考虑的点集。

好问题！我根本没有尝试过这个，但我的第一个镜头是这种迭代方法：

创建一个集合 N（“不包含”），并将集合中的所有点添加到 N。
从 N 中随机选取 3 个点形成初始多边形 P。将它们从 N 中删除。
使用一些多边形内的点算法并查看 N 中的点。对于 N 中的每个点，如果它现在被 P 包含，则将其从 N 中删除。一旦发现 N 中的点仍未包含在 P 中，请继续步骤 4。如果 N 变空，则完成。
将你找到的点称为 A。找到P中最接近A的线，并将A添加到它的中间。
返回步骤 3

我认为只要它表现得足够好，它就会起作用——对你最初的 3 点进行良好的启发可能会有所帮助。

祝你好运！

您可以使用此插件在 QGIS 中完成此操作；https://github.com/detlevn/QGIS-ConcaveHull-Plugin

根据您需要它如何与数据交互，可能值得在此处查看它是如何完成的。

Bing Maps V8 交互式 SDK 在高级形状操作中具有凹壳选项。

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

在 ArcGIS 10.5.1 中，3D Analyst 扩展模块具有最小边界体积工具，其几何类型为凹包、球体、包络线或凸包。它可以在任何许可证级别使用。

这里有一个凹壳算法： https://github.com/mapbox/concaveman

一个快速的近似解决方案（对于凸包也有用）是找到东西向每个小元素的北界和南界。

根据您想要的详细信息量，创建固定大小的上限/下限数组。对于每个点，计算它位于哪个 E-W 列，然后更新该列的上限/下限。处理完所有点后，您可以为那些遗漏的列插入上限/下限点。

还值得事先快速检查一下是否有很长的细形状，并决定是否将 NS 或 Ew 分类。

作为广泛采用的参考，PostGIS 从凸包开始，然后将其塌陷，您可以在此处看到它。