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

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

解决方案

回答

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

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

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

回答

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

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

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

回答

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

• 创建一个集合N("不包含")，并将集合中的所有点添加到N。
• 从N中随机选取3个点以形成初始多边形P。将其从N中移除。
• 使用某些多边形中的点算法，查看N中的点。对于N中的每个点，如果现在包含在P中，请将其从N中删除。一旦在N中找到一个点，该点仍不包含在P中，继续执行第4步。如果N变为空，则操作完成。
• 呼叫找到的点A。找到P中最接近A的线，并在中间添加A。
• 返回第3步

我认为，只要它表现得足够好，并且对我们最初的3分有启发性就可以了。

祝你好运！

回答

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

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

回答

一个简单的解决方案是在多边形的边缘周围走动。给定边界连接点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)，因此我们需要对点列表进行一些排序。如果将点与城市质心的方位进行排序，则可以限制每次迭代时需要考虑的点集。