是否有有效的算法来生成 2D 凹壳?
题
拥有 GIS 文件(城市地图)中的一组(2D)点,我需要生成定义该地图(其边界)“轮廓”的多边形。其输入参数将是点集和“最大边长”。然后它将输出相应的(可能是非凸的)多边形。
到目前为止,我发现的最佳解决方案是生成 Delaunay 三角形,然后删除长于最大边长的外部边。当所有外部边缘都比这短之后,我只需删除内部边缘并得到我想要的多边形。问题是,这非常耗时,我想知道是否有更好的方法。
其他提示
我们实验室的一位前学生在他的博士论文中使用了一些适用的技术。我相信其中之一称为“阿尔法形状”,并在以下论文中引用:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
该论文提供了一些您可以遵循的进一步参考资料。
答案对其他人来说可能仍然很有趣:一个人可以申请一个 行进方阵算法的变体, ,应用 (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 在高级形状操作中具有凹壳选项。
在 ArcGIS 10.5.1 中,3D Analyst 扩展模块具有最小边界体积工具,其几何类型为凹包、球体、包络线或凸包。它可以在任何许可证级别使用。
这里有一个凹壳算法: https://github.com/mapbox/concaveman
一个快速的近似解决方案(对于凸包也有用)是找到东西向每个小元素的北界和南界。
根据您想要的详细信息量,创建固定大小的上限/下限数组。对于每个点,计算它位于哪个 E-W 列,然后更新该列的上限/下限。处理完所有点后,您可以为那些遗漏的列插入上限/下限点。
还值得事先快速检查一下是否有很长的细形状,并决定是否将 NS 或 Ew 分类。
作为广泛采用的参考,PostGIS 从凸包开始,然后将其塌陷,您可以在此处看到它。