是否有一种有效的算法来生成 2D 凹壳? [英] 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.

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