从 GIS 文件（城市地图）中获得一组（2D）点，我需要生成定义该地图（其边界）的“轮廓”的多边形。它的输入参数将是点集和“最大边长”。然后它将输出相应的（可能是非凸的）多边形。
到目前为止，我发现的最佳解决方案是生成 Delaunay 三角形，然后删除比最大边长更长的外部边。在所有外部边缘都比这短之后，我只需删除内部边缘并获得我想要的多边形。问题是，这非常耗时，我想知道是否有更好的方法。
Fabio Ceconello
问问题
32747 次
10 回答
10
我们实验室的一位前学生在他的博士论文中使用了一些适用的技术。我相信其中之一被称为“阿尔法形状”，并在以下论文中被引用：
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
该论文提供了一些您可以参考的进一步参考资料。
于 2008-09-17T14:24:59.340 回答
2
对于其他人来说，答案可能仍然很有趣：一个人可能会应用行进平方算法的变体，应用（1）在凹壳内，（2）然后在（例如 3）不同的尺度上，我取决于平均密度点。比例尺必须是彼此的整数倍，这样您就可以构建一个可用于有效采样的网格。这允许快速找到空样本=正方形，完全在点的“集群/云”内的样本，以及介于两者之间的样本。后一类然后可以用来容易地确定代表凹壳的一部分的折线。
在这种方法中，一切都是线性的，不需要三角测量，它不使用 alpha 形状，并且与此处描述的商业/专利产品不同 ( http://www.concavehull.com/ )
于 2012-01-29T15:40:02.747 回答
1
一个快速的近似解决方案（也适用于凸包）是找到每个东西向的小元素的南北边界。
根据您想要多少细节，创建一个固定大小的上限/下限数组。对于每个点，计算它所在的 EW 列，然后更新该列的上限/下限。处理完所有点后，您可以为那些错过的列插入上/下点。
对于非常长的薄形状并决定是否将 NS 或 Ew 分类，也值得事先快速检查。
于 2008-09-17T14:25:20.837 回答
1
好问题！我根本没有尝试过，但我的第一个镜头是这种迭代方法：
- 创建一个集合 N（“不包含”），并将集合中的所有点添加到 N。
- 从 N 中随机选取 3 个点，形成一个初始多边形 P。将它们从 N 中移除。
- 使用一些多边形点算法并查看 N 中的点。对于 N 中的每个点，如果它现在包含在 P 中，则将其从 N 中删除。一旦在 N 中找到仍然不包含在 P 中的点，继续执行第 4 步。如果 N 为空，则完成。
- 将找到的点称为 A。在 P 中找到最靠近 A 的线，并在中间添加 A。
- 返回第 3 步
我认为只要它表现得足够好，它就会起作用——对你最初的 3 点进行一个好的启发式可能会有所帮助。
祝你好运！
于 2008-09-17T14:37:14.677 回答
1
一个简单的解决方案是绕着多边形的边缘走动。给定连接点 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) 所以你需要对你的点列表进行一点排序。如果您对点进行排序，例如，它们与城市质心的方位角，您可以限制每次迭代时需要考虑的点集。
于 2008-09-17T14:42:29.160 回答
1
您可以使用此插件在 QGIS 中进行操作； https://github.com/detlevn/QGIS-ConcaveHull-Plugin
根据您需要它与数据交互的方式，可能值得在这里查看它是如何完成的。
于 2016-02-18T23:01:09.123 回答
1
作为广泛采用的参考，PostGIS 从凸包开始，然后将其嵌入，您可以在此处查看。
于 2017-11-29T18:14:11.540 回答
1
Bing Maps V8 交互式 SDK 在高级形状操作中具有凹壳选项。
在 ArcGIS 10.5.1 中，3D Analyst 扩展模块具有最小边界体积工具，其几何类型包括凹壳、球体、包络或凸壳。它可以在任何许可级别使用。
这里有一个凹壳算法：https ://github.com/mapbox/concaveman
于 2018-02-13T22:06:17.457 回答