爲封閉多邊形尋找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算法的好起點

回答

相關問題