是否有一个有效的算法来产生2D凹船体？ [英] Is there an efficient algorithm to generate a 2D concave hull?

问题描述

有一组（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.

我发现迄今最好的解决办法是创造了德劳内三角形，然后取下外部边缘，比最大边长更长。在所有的外部边缘比身材较矮，我只需删除内部边缘并得到我想要的多边形。问题是，这是非常耗时的，我不知道是否有一个更好的办法。

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.

推荐答案

检查thiis 的http://www.wipo.int/pctdb/en/wo.jsp?WO=2008107859&IA=IB2008050849&DISPLAY=DESC

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