是否有生成二维凹壳的有效算法? [英] Is there an efficient algorithm to generate a 2D concave hull?

问题描述

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

Having a set of (2D) points from a GIS file (a city map), I need to generate the polygon that defines the 'contour' for that map (its boundary). Its input parameters would be the points set and a 'maximum edge length'. It would then output the corresponding (probably non-convex) polygon.

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

The best solution I found so far was to generate the Delaunay triangles and then remove the external edges that are longer than the maximum edge length. After all the external edges are shorter than that, I simply remove the internal edges and get the polygon I want. The problem is, this is very time-consuming and I'm wondering if there's a better way.

推荐答案

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

This paper discusses the Efficient generation of simple polygons for characterizing the shape of a set of points in the plane and provides the algorithm. There's also a Java applet utilizing the same algorithm here.

这篇关于是否有生成二维凹壳的有效算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！