跳至內容

道格拉斯-普克算法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

拉默-道格拉斯-普克演算法(英語:Ramer–Douglas–Peucker algorithm),又稱道格拉斯-普克演算法(英語:Douglas–Peucker algorithm)和迭代端點擬合算法(英語:iterative end-point fit algorithm),是一種將線段組成的曲線降採樣為點數較少的類似曲線的算法。它是最早成功地用於製圖綜合英語cartographic generalization的算法之一。

思路

[編輯]

該算法的目的是,給定一條由線段構成的曲線(在某些情況下也稱為折線),找到一條點數較少的相似曲線。該算法根據原曲線與簡化曲線之間的最大距離(即曲線之間的郝斯多夫距離)來定義 "不相似"。簡化曲線由定義原始曲線的點的子集組成。

算法

[編輯]
用道格拉斯-普克算法簡化一條分段線性曲線。

起始曲線是一組有序的點或線,距離維度 ε > 0。

該算法遞歸劃分線。最初,它被賦予了第一點和最後一點之間的所有點。它自動標記要保留的第一點和最後一點。然後它找到離以第一點和最後一點為終點的線段最遠的點;這個點顯然是曲線上離終點之間的近似線段最遠的點。如果這個點離線段的距離比 ε 更近,那麼在簡化曲線不比 ε 差的情況下,可以捨棄任何當前沒有標記保留的點。

如果離線段最遠的點大於近似值 ε,那麼該點必須保留。該算法以第一點和最遠點遞歸調用自身,然後以最遠點和最後一點調用自身,其中包括最遠點被標記為保留。

當遞歸完成後,可以生成一條新的輸出曲線,該曲線由所有且僅由那些被標記為保留的點組成。

在RDP的參數化實現中,改變 ε 的影響。

非參數化的拉默-道格拉斯-普克演算法

[編輯]

ε 的選擇通常由用戶定義。像大多數線擬合/多邊形逼近/主點檢測方法一樣,它可以通過使用數碼化/量化引起的誤差邊界作為終止條件來實現非參數化。[1]

偽代碼

[編輯]

(假設輸入是一個索引從1開始的數組)

function DouglasPeucker(PointList[], epsilon)
    // Find the point with the maximum distance
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to (end - 1) {
        d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
        if (d > dmax) {
            index = i
            dmax = d
        }
    }
    
    ResultList[] = empty;
    
    // If max distance is greater than epsilon, recursively simplify
    if (dmax > epsilon) {
        // Recursive call
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

        // Build the result list
        ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Return the result
    return ResultList[]
end

連結:https://karthaus.nl/rdp/頁面存檔備份,存於互聯網檔案館

應用

[編輯]

該算法用於處理向量圖形製圖綜合英語cartographic generalization。它並不總是保留曲線的非自交屬性,這導致了變體算法的發展。[2]

該算法廣泛應用於機械人技術[3]中,對旋轉式測距掃描儀獲取的測距數據進行簡化和去噪處理;在這個領域,它被稱為分割合併算法,歸功於DudaHart[4]

複雜度

[編輯]

該算法在由 段和 個頂點組成的折線上運行時的時間由遞歸 給出,其中 是偽代碼中的索引值。在最壞的情況下,每次遞歸調用時,,該算法的運行時間為 。在最好的情況下,在每次遞歸調用時,,在這種情況下,運行時間具有 的眾所周知的解(通過分治法的主定理)。

使用(全或半)動態凸包英語Dynamic convex hull數據結構,算法所進行的簡化可以在 時間內完成。[5]

類似算法

[編輯]

線簡化的替代算法包括:

參見

[編輯]

延伸閱讀

[編輯]

參考文獻

[編輯]
  1. ^ Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung. A novel framework for making dominant point detection methods non-parametric. Image and Vision Computing. 2012, 30 (11): 843–859. doi:10.1016/j.imavis.2012.06.010. 
  2. ^ Wu, Shin-Ting; Marquez, Mercedes. A non-self-intersection Douglas-Peucker algorithm. 16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003). Sao Carlos, Brazil: IEEE. 2003: 60–66. CiteSeerX 10.1.1.73.5773可免費查閱. ISBN 978-0-7695-2032-2. doi:10.1109/SIBGRA.2003.1240992.  |book-title=被忽略 (幫助)
  3. ^ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland. A comparison of line extraction algorithms using 2D range data for indoor mobile robotics (PDF). Autonomous Robots 23 (2). 2007: 97–111 [2020-12-18]. doi:10.1007/s10514-007-9034-y. (原始內容 (PDF)存檔於2021-04-23).  參數|journal=與模板{{cite conference}}不匹配(建議改用{{cite journal}}|book-title=) (幫助)
  4. ^ Duda, Richard O.; Hart, Peter E. Pattern classification and scene analysis需要免費註冊. New York: Wiley. 1973. ISBN 0-471-22361-1. 
  5. ^ Hershberger, John; Snoeyink, Jack. Speeding Up the Douglas-Peucker Line-Simplification Algorithm (PDF) (技術報告). 1992 [2020-12-18]. (原始內容 (PDF)存檔於2021-05-06). 

外部連結

[編輯]