有没有一种有效的algorithm来生成二维凹面船体？
从GIS文件（城市地图）中获取一组（2D）点，我需要生成定义该地图（边界）的“轮廓”的多边形。 其input参数将是设置的点和“最大边缘长度”。 然后它会输出相应的（可能是非凸的）多边形。
我发现迄今为止最好的解决scheme是生成Delaunay三angular形，然后删除比最大边长更长的外边。 在所有的外部边缘比这个更短之后，我只需要移除内部边缘并得到我想要的多边形。 问题是，这是非常耗时的，我想知道是否有更好的方法。
本文讨论了简单多边形的有效生成方法，用于描述平面中一组点的形状，并给出algorithm。 这里还有一个Java applet使用相同的algorithm。
我们实验室的前一名学生使用了一些适用于他的博士论文的技术。 我相信其中之一被称为“alpha形状”，并在以下文章中引用：
people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
该文件提供了一些可供参考的参考资料。
对于其他人来说，答案可能还是有趣的：可以应用步进平方algorithm的变化 ，应用（1）在凹壳内，（2）然后在（例如3）不同的尺度上 ，这取决于平均密度点。 这些尺度需要是彼此的整数倍，例如，您可以构build可用于高效采样的网格。 这样可以快速find空样本=正方形，完全位于“群/云”点之间的样本，以及位于两者之间的样本。 后一类可以用来容易地确定代表凹形船体一部分的多义线。
在这种方法中，所有东西都是线性的，不需要三angular测量，它不使用alpha形状，它与商业/专利产品不同（详见http://www.concavehull.com/ ）
这里的人声称已经开发出了k个最近邻的方法来确定一组点的凹壳，这些点在“点的数量上几乎是线性的”。 可悲的是，他们的论文看起来很谨慎，你得问问他们 。
这里有一套很好的参考资料 ，包括上面的内容，可能会让你find更好的方法。
一个简单的解决scheme是走在多边形的边缘。 给定当前边界连接点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），所以你想要点你的点数列表。 您可以限制每次迭代时需要考虑的一组点，例如，根据城市中心的方位进行sorting。
好问题！ 我还没有尝试过，但我的第一枪是这种迭代方法：
- 创build一个N（“不包含”），并将所有点添加到您的设置N.
- 从N中随机抽取3个点，形成一个初始多边形P.将它们从N中移除。
- 对于N中的每一个点，如果它现在被P所包含，则将它从N中删除。一旦在N中find一个点仍然不包含在P中，继续第4步。如果N变空，就完成了。
- 调用find的点A.findP最靠近A的那一行，并在其中间加上A.
- 回到步骤3
我认为只要performance的好，它就会起作用 – 对你最初的3分有一个很好的启发可能会有所帮助。
祝你好运！
这个插件可以在QGIS中完成。 https://github.com/detlevn/QGIS-ConcaveHull-Plugin
根据你需要怎样与你的数据交互，可能值得看看它是如何完成的。
一个快速的近似解决scheme（对凸包也是有用的）是find东西向的每个小元素的南北界。
基于你想要多less细节，创build一个固定大小的上/下限数组。 对于每个点计算它所在的EW列，然后更新该列的上限/下限。 处理完所有点后，可以插入错过的列的上/下点。
这也是值得做一个快速检查，非常长的薄形状，并决定是否NS或EW。
