查找閉合路徑的多邊形近似

我希望能夠找到閉合路徑的最佳擬合多邊形近似值（可能是任何路徑，因爲它們被從圖像中拉出），但是在解決方法上存在問題以編碼算法來找到它。我可以想到一種天真的方法：沿路徑每x個像素點，爲這些像素選擇最合適的線，然後對不同的起始偏移量和長度進行蠻力掃描，並找到最小化最小平方誤差的線用最少量的線。查找閉合路徑的多邊形近似

有一些更優雅的東西。任何人都知道什麼？此外，（畏懼），但這將在JavaScript中實現，除非我真的很絕望，所以很好的庫爲你做的事情是非常排除，（opencv有一個多邊形鉗工例如）。

來源

2013-01-14 Newmu

D3.js 1有一些adaptive resampling代碼可能可以使用。還有一個圖解description of the algorithm使用（Visvalingam的算法）。

來源

2013-01-14 11:25:52

最終實現了Visvalingam的算法，如D3，因爲它具有如此清晰直觀的理解。謝謝你們的建議！ – Newmu

這看起來很簡單（這很好），這個例子非常好，很有趣。直到這個時候，我不需要實現多邊形近似（用於現成的實現），只是通常形狀近似 - 可以使用傅立葉描述符來完成。在壓縮方面，我想這種方法不能用傅里葉描述符來擊敗一個方法，除非形狀邊界完全丟失，或者情況並非如此？（只是好奇） – mmgp

Ramer–Douglas–Peucker這個算法在這裏看起來很合適，而且很容易實現。請注意，可接受的錯誤是此算法的輸入，因此如果您有目標行數，則可以使用error參數進行二進制搜索以命中目標。

來源

2013-01-14 12:10:45 ryanm

看起來不錯，但是能夠指定Visvalingam算法中所需的行數量，使得我可以使用它。 – Newmu

請記住，根據您的輸入數據，刪除每個步驟中最小面積的三角形可能不是最佳行爲。例如，從另外一條直線延伸的非常長，非常細的尖峯將有一個小區域，但是這個線條非常引人注目，您可能希望保留這個特徵。 – ryanm

現在我對結果感到滿意，其目的是純粹的視覺位圖矢量化圖像，所以大多數形狀已經傾向於表現良好。如果問題出現了，我一定會去看看。 – Newmu

查找閉合路徑的多邊形近似

回答

相關問題