关于数学：是否有一种有效的算法来生成2D凹面船体？

从GIS文件(城市地图)中获得一组(2D)点，我需要生成定义该地图(其边界)的"轮廓"的多边形。 它的输入参数是设置的点数和"最大边缘长度"。 然后它将输出相应的(可能是非凸的)多边形。

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

我们实验室的一位前学生在其博士学位论文中使用了一些适用的技术。我相信其中一种称为" alpha形状"，并在以下论文中进行了引用：

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

该论文提供了一些您可以遵循的其他参考。

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

对于其他人来说，答案可能仍然很有趣：一个人可以应用行进平方算法的一种变体，在凹壳内应用(1)，然后在(例如3)上应用取决于我的平均密度的不同比例点。比例尺必须是彼此的整数倍，因此您可以构建可用于有效采样的网格。这样可以快速找到空样本=正方形，完全位于点的"群集/云"之内的样本以及介于它们之间的样本。然后可以使用后一种类别轻松确定代表凹壳一部分的折线。

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

这里的家伙声称已经开发出一种k最近邻方法来确定一组点的凹包，该点的行为"几乎线性地取决于点的数量"。不幸的是，他们的文件似乎受到很好的保护，您必须要他们的文件。

这是一整套包括上述内容的参考，可能会使您找到更好的方法。

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

您可以使用此插件在QGIS中进行操作。
https://github.com/detlevn/QGIS-ConcaveHull-Plugin

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

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

然后你设置

并重复直到回到起点。

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

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

我认为只要性能足够好，它就会奏效-对您最初的3分进行启发式的尝试可能会有所帮助。

祝好运！

一个快速的近似解决方案(对凸包也有用)是找到东西各个小元素的北边界和南边界。

根据所需的详细信息，创建大小固定的上限/下限数组。
对于每个点，计算它在哪个E-W列中，然后更新该列的上下边界。处理完所有点后，您可以为错过的那些列插上/下点。

对于非常长的薄形状，还需要事先进行快速检查，并决定是否将NS或Ew装箱。

作为广为接受的参考，PostGIS从凸包开始，然后将其陷进去，您可以在此处看到它。

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819