logo标签列表

有没有一种高效的算法可以生成2D凸壳？

algorithmgeometry2dgisconcave-hull
67

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

目前为止我找到的最佳解决方案是生成Delaunay三角形，然后删除外部边缘长度大于最大边长的部分。当所有外部边都小于此长度时，我只需删除内部边即可获得所需的多边形。问题在于，这非常耗时，我想知道是否有更好的方法。

1
实际上，我认为ArcGIS没有内置的算法可以做他想要的事情。ArcGIS有能力进行凸包计算，但是凹多边形的处理就比较复杂了。 - Chris Upchurch
2
你能更精确地定义你的问题吗？ :)给定5个点：一个正方形的4个角和它的中心点。如果你的最大边长允许覆盖中心点，那么你的边界将是什么？此时，你可以任意选择正方形的四条边中的任意一条“弯曲”，从而包含中心点。 - Luke Halliwell
1
是的，我用问题中提到的方法（使用Delaunay三角形）进行了一些工作。后来我对nsanders提出的alpha shapes概念做了一些工作，但在我解决它之前，该问题的优先级降低了，我转而处理其他问题。 - Fabio Ceconello
2
Delaunay算法的时间复杂度是正确的（O(n log n)）。我怀疑在渐进意义下你很难做得更好。 - Alexandre C.
1
@frank 这不是手动的，而是一个用于处理GPS导航应用程序地图的自动化工具的一部分。在我的特定情况下，它确实是任意的，因为这些点是街角，生成的多边形将成为城市的轮廓。我使用了一个任意值，以给出足够详细的多边形，同时不会太重以至于难以呈现。我认为必须这样做，你必须根据你的应用程序需求来确定最大长度 - 我不知道如何在事先自动计算它。 - Fabio Ceconello
显示剩余10条评论
10个回答
11
1
Alpha形状基于Delaunay三角剖分，因此它肯定涉及一个Delaunay三角剖分计算。 - balint.miklos
在我看来，Alpha Shapes 只是一个概念。 - Micromega
4

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

2
链接失效。Java源代码似乎在http://ambientspatial.net/ddo/?p=143。 - Ian
@Ian 第二个链接也失效了。 - Robotex
@Robotex 哇，那是六年前的事了。现在我真的一点都不记得了，很抱歉。 - Ian
3
这里的人 声称 开发了一种 k 最近邻方法来确定一组点的凹壳，其表现“几乎与点数成线性关系”。可惜他们的论文似乎很好保护，你需要向 他们 询问。
以下是一个好的参考资料集，其中包括上述信息，可能会帮助您找到更好的方法。
2
看起来这就是相关论文：http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf这个想法非常聪明和简单 - 就我所理解的而言，它只是对于凸壳的 Graham 扫描技术的直接修改。不需要找到 Delaunay 三角剖分等。 - Zach Conn
1
该论文的名称是“凹壳：一种K近邻方法，用于计算一组点所占据的区域”，可在此处获取：http://repositorium.sdum.uminho.pt/handle/1822/6429 - deshu
2
答案可能仍然对其他人有趣：可以应用 marching square 算法的变体，（1）在凸包内应用，（2）然后在不同的比例（例如3），这取决于点的平均密度。这些比例需要是整数倍，这样就可以建立一个网格来进行有效的采样。这样可以快速找到空样本=正方形、完全位于“簇/云”点内部的样本以及那些介于两者之间的样本。然后可以使用后一类来轻松确定表示凸包一部分的折线。
这种方法中的一切都是线性的，不需要三角剖分，也不使用 alpha 形状，并且与此处描述的商业/专利产品不同（http://www.concavehull.com/）。
1
一个简单的解决方案是绕着多边形的边界走。给定当前边缘om，连接点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)，因此您需要对点列表进行排序。如果您按照它们相对于城市重心的方位角进行排序，可以在每次迭代时限制需要考虑的点集。

1
1

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

根据您需要多少细节，创建一个固定大小的上/下限数组。对于每个点，计算它在哪个东西方向的列中，然后更新该列的上/下限。在处理完所有点之后，您可以插值那些错过的列的上/下限点。

事先进行快速检查非常值得，以确定是将NS还是Ew分组对于非常长而薄的形状。

1

好问题！我还没有尝试过这个方法，但我的第一步会是使用迭代法：

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

我认为只要表现足够好，它就可以工作 - 对于您的初始3个点的良好启发式可能会有所帮助。

祝你好运！

1
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接