Ramer-Douglas-Peucker算法在繪製線條時出現問題

Question

我正在開發iOS繪畫應用程序，並且爲了獲得平滑線條，我應用了採樣點的Ramer-Douglas-Peucker算法。

該算法對點的整個矢量起作用，並且隨着點的添加，結果發生變化。它會導致結果曲線在用戶繪製時「跳躍」。

是否有解決此問題的已知解決方案？

Answer 1

我從來沒有實現或使用這種算法，但我能想到的兩種可能的解決方案：

1. 算法應用到該行的分立部分。也就是說，等到用戶繪製了10個點，然後在點0..9上運行算法。然後等待用戶繪製了下10個點並在點10..19上運行算法，依此類推。一個可能的注意事項是它可以在點10,20等創建副作用，但我真的不知道它是否會對用戶明顯。

2. 等待用戶完成繪製，然後在整行上運行該算法一次。我以前在應用中見過這種方法。

這些都具有你正在運行上的每個點的算法不超過兩次（在後一種情況下，恰好一次）的優勢，而如果你每次運行的算法的點添加你最終每次添加一個點時，都會在之前的每個點上運行它，這可能會導致性能損失。

就像我說的，這不是我的專業領域，但我希望它能給你一些想法。

Answer 2

我懷疑這是完全可以避免的，原因很簡單：算法無法猜測未來的要點。

想象一下，你畫出前兩點;顯然你會保留它們。現在轉到第三點。如果R-D-P告訴你放棄中間點，你可能不會因爲那會引起跳躍。等等。禁止跳躍意味着你不允許任何刪除！

也許你可以通過繪製保持穩定的原始曲線和平滑的曲線來減輕心理影響。

這就是說，R-D-P可能不是平滑的最佳方法。