# 道格拉斯-普克算法

## 算法

### 非参数化的拉默-道格拉斯-普克演算法

ε 的选择通常由用户定义。像大多数线拟合/多边形逼近/主点检测方法一样，它可以通过使用数字化/量化引起的误差边界作为终止条件来实现非参数化。[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


## 参考文献

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. . 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）.