algorithm - 是否有生成二维凹包的有效算法？

Question

我有一组来自 GIS 文件(城市 map )的 (2D) 点，我需要生成定义该 map (其边界)“轮廓”的多边形。它的输入参数将是点集和“最大边长”。然后它会输出相应的(可能是非凸的)多边形。

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

Answer 1

我们实验室的一名前学生在他的博士论文中使用了一些适用的技术。我相信其中之一被称为“alpha shapes”，并在以下论文中引用:

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

该论文提供了一些您可以遵循的进一步引用。