# 道格拉斯-普克算法

## 算法

### 伪代码

```function DouglasPeucker(PointList[], epsilon)
//Find the point with the maximum distance
dmax = 0
index = 0
for i = 2 to (length(PointList) - 1)
d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
if d > dmax
index = i
dmax = d
end
end

//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...end-1] recResults2[1...end]}
else
ResultList[] = {PointList[1], PointList[end]}
end

//Return the result
return ResultList[]
end
```

## 参考文献

• 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