Ramer–Douglas–Peucker algorithm
lastmod 2024-03-06created 2024-03-062 edits
The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm.
An algorithm that reduces a curve composed of line segments to a similar curve with fewer points.
It was one of the earliest successful algorithms developed for cartographic generalization.
Idea
The purpose of the algorithm is, given a curve composed of line segments (also called a polyline in some contexts), to find a similar curve with fewer points. The algorithm defines "dissimilar" based on the maximum distance between the original curve and the simplified curve (i.e., the Hausdorff distance between the curves). The simplified curve consists of a subset of the points that defined the original curve.