为封闭多边形寻找Douglas-Peucker算法的好起点

我想用Douglas-Peucker算法减少多边形的顶点 - 这对于线和路径来说工作得相当好。为封闭多边形寻找Douglas-Peucker算法的好起点

我的问题是，我想要优化的多边形是封闭的。当选择2个随机相邻点时，优化效果很好 - 除了起点和终点以外 - 因为它们是固定的并且不能被优化。

有没有一种很好的方法来选择一个起点？

来源

2012-01-16 Andreas Löw

我只是随机选择一个点（例如：所有点列表中的“第一个”点）并找到最远点。这与从线段搜索最远点时算法的普通步骤类似。

来源

2012-01-16 08:42:09

问题是：如果我有一个由边上的几个顶点组成的矩形形状，它可能会切割边缘 - 留下梯形而不是矩形。这也可能导致构建具有5个顶点而不是一个顶点的矩形。 – 2012-01-16 08:45:56

@AndreasLöw：这是Douglas-Peucker算法的问题。不保证是最佳的。这是贪婪的，不做任何后退步骤。您可以尝试选择所有可能的起点并评估结果。但如果形状保证为矩形，则可能有更好的算法。 – 2012-01-16 08:49:39

我可能在这里完全误解了这个问题，但它听起来像你只是想将Douglas-Peucker算法（http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm）改编成多边形。你不能仅仅将你的多边形看作一条起点和终点相同的线，这是因为算法要求你将这两个点区分开来。

所以我建议在你的多边形上选取两个任意点，然后分两次运行Douglas-Peucker算法，一次是顺时针方向点之间的路径，一次是点之间的路径逆时针旋转。

你的任意点被保证在最终的解决方案，但否则其尽可能接近的算法线近似。

如果这还不够，您应该搜索LOD或Level Of Detail，因为这是计算机图形学中通常所称的问题，尽管您可能会碰到一堆关于解决多面体问题的页面具有相当复杂的树结构，这可能是也可能不是你想要的。

来源

2012-01-16 09:55:48 dhakim

我在JavaScript库中做了类似的事情，在那里我找到了彼此距离最远的两个点，并使用它们来优化多边形。

这是我敢肯定，你可以适应任何一种语言，你使用的片段：

function polygonPeuckerReduce(path, tolerance) { 
    var points = []; 
    if (path.length < 3) { 
     return points.concat(path); 
    } else { 
     var widest = 0.0, startIndex = 0; 
     // find the widest part of the polygon (only start index is necessary) 
     for (var i = 0, l = path.length; i < l; i++) { 
      var point = path[i]; 
      for (var j = i + 1; j < l; j++) { 
       var distance = point.distanceTo(path[j]); 
       if (distance > widest) { 
        startIndex = i; 
        widest = distance; 
       } 
      } 
     } 

     // re-order the points with the new starting point (faster method) 
     points = path.splice(startIndex, path.length).concat(path); 

     return PEUCKER_INTERNAL(points, tolerance); // the magic 
    } 
}

来源

2015-03-04 21:00:15

另一种可能性是通过三个连续的顶点所有集合扫描并挑选这两个是最远的距离加入他们的前任和后继顶点的线，即挑选属于原始数据集中两个最大拐角的两个顶点。修复这两个顶点，然后将Douglas-Peucker应用到中间顶点。

如果所有的点间距很近，这可能会很嘈杂。在这种情况下，不是简单地考虑三个顶点的连续集合，您可以使用Douglas-Peucker在每个方向上跳过不必要的顶点，从每个输入顶点的两个方向向外工作。这将导致更大，更宽间隔的三元组。再次找到离连接前驱/后继顶点的线最远的两个顶点，修复这些顶点，并将Douglas-Peucker应用到中间顶点。

其他变化是可能的，但是这应该比其他答案中描述的“随机”或“最远分开”提供更好的起始点。

来源

2016-02-17 04:55:59 Kekoa

为封闭多边形寻找Douglas-Peucker算法的好起点

回答

相关问题