Ramer–Douglas–Peucker Algorithm

The Ramer–Douglas–Peucker Algorithm is a an algorithms that reduce the number of points that is approximated by a series of points. It is also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm. In simple words, it represent a complex line with fewer points in a visually proper way.

Original dataset (right) and reduced output (left) from Ramer-Douglas-Peucker Algorithm. Image from NAMEKDEV.

Overview

The main purpose of this algorithm is to find a similar curve with fewer points for a given curve composed of line segments (also called Polylines). This algorithm define 'disimilar' based on the maxium distance between the original curve and the simplied curve, i.e. the Hausdroff Distance. The simplified curve consist of a subset of points that defined the original curve. The Ramer–Douglas–Peucker Algorithm is most commonly used in geospatial visualizations, like Google Maps, but also useful for other in-browser visualizations as well.

Working of Ramer–Douglas–Peucker Algorithm

In order to use this algorithms, the user must the epsilon ( ε ), a threshold limit that is used to determine which point to determine and discard, and it should be a value greater than zero.

Step-1 : This algorithms stored the first and the last point of the curve and then it draws the shortest line from the bookend points.

Step-2: Its determine the point farthest point from the line segment with the first and last points as end points.

Step-3: Any points within the epsilon distance from this line will be removed and the approximation will be drawn.

The process repeats recurcively until the new approximation for the polyline has been formed.

Pseudocode

The Pseudocode of Ramer–Douglas–Peucker Algorithm :

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

Complexity

The running time of Ramer–Douglas–Peucker Algorithm when a polyline consist of n-1 segments and n vertices is given by the reccurence T(n)=T(i+1)+T(n-i)+O(n) where is the value of Index in peudocode.

In worst case, the algorithm has a time complexity of O(n²).

In best case, it has a time complexity of O(n log(n)) .

Applications

This algorithms is used for proccessing vector graphics and and cartographic generalization. It is widely used in Robotics to perform simplification and denoising of range data accquired by a rotating range scanner.

Example of Ramer–Douglas–Peucker Algorithm

Download the code here