道格拉斯-普克算法

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

## 思路

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

## 算法

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

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

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

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

### 無母數化的拉默 - 道格拉斯 - 普克演算法

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

### 偽代碼

（假設輸入是一個索引從 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/ （頁面存檔備份，存於網際網路檔案館）

## 應用

該算法用於處理矢量圖形和製圖綜合。它並不總是保留曲線的非自交屬性，這導致了變體算法的發展。

該算法廣泛應用於機器人技術中，對旋轉式測距掃描儀獲取的測距數據進行簡化和去噪處理；在這個領域，它被稱為分割合併算法，歸功於 Duda 和 Hart。

## 複雜度

該算法在由 $n-1$ 段和 $n$ 個頂點組成的折線上運行時的時間由遞迴 $T(n)=T(i+1)+T(n-i)+O(n)$ 給出，其中 $i\in \{1,\ldots ,n-2\}$ 是偽代碼中的索引值。在最壞的情況下，每次遞迴調用時， $i=1$ 或 $i=n-2$ ，該算法的運行時間為 $\Theta (n^{2})$ 。在最好的情況下，在每次遞迴調用時， $i=\lfloor n/2\rfloor $ 或 $i=\lceil n/2\rceil $ ，在這種情況下，運行時間具有 $O(n\log n)$ 的眾所周知的解（通過分治法的主定理）。

使用（全或半）動態凸包資料結構，算法所進行的簡化可以在 $O(n\log n)$ 時間內完成。

## 類似算法

線簡化的替代算法包括：

* Visvalingam–Whyatt
* Reumann–Witkam
* Opheim simplification
* Lang simplification
* Zhao-Saalfeld

## 參見

* 曲線擬合

## 延伸閱讀

* Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(3), 244–256 (1972) doi:10.1016/S0146-664X(72)80017-0
* David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112–122 (1973) doi:10.3138/FM57-6770-U75U-7727
* John Hershberger & Jack Snoeyink, "Speeding Up the Douglas–Peucker Line-Simplification Algorithm", Proc 5th Symp on Data Handling, 134–143 (1992). UBC Tech Report TR-92-07 available at http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07 （頁面存檔備份，存於網際網路檔案館）
* R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", (1973), Wiley, New York (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html)
* Visvalingam, M; Whyatt, JD. Line Generalisation by Repeated Elimination of the Smallest Area (Technical report). Discussion Paper. Cartographic Information Systems Research Group (CISRG), The University of Hull. 1992 [2020-12-18]. 10. （原始內容存檔於 2021-01-30）.

## 參考文獻

## 外部連結

* Boost.Geometry 支持 Douglas-Peucker 簡化算法。 （頁面存檔備份，存於網際網路檔案館）
* Ramer-Douglas-Peucker 等簡化算法的 C++ 開源實現 （頁面存檔備份，存於網際網路檔案館）
* 用於 KML 數據的算法的 XSLT 實現。 （頁面存檔備份，存於網際網路檔案館）
* 您可以在本頁底部看到應用於自行車騎行的 GPS 日誌的算法。 （頁面存檔備份，存於網際網路檔案館）
* 此算法的交互式可視化 （頁面存檔備份，存於網際網路檔案館）
* F# 實現 （頁面存檔備份，存於網際網路檔案館）
* Ruby gem 實現 （頁面存檔備份，存於網際網路檔案館）
* JTS, Java Topology Suite （頁面存檔備份，存於網際網路檔案館），包含了許多算法的 Java 實現，包括 Douglas-Peucker 算法 （頁面存檔備份，存於網際網路檔案館）。