Ramer–Douglas–Peucker algorithm

The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm that decimates 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 (which is 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.

Algorithm

Simplifying a piecewise linear curve with the Douglas–Peucker algorithm.

The starting curve is an ordered set of points or lines and the distance dimension ε > 0.

The algorithm recursively divides the line. Initially it is given all the points between the first and last point. It automatically marks the first and last point to be kept. It then finds the point that is farthest from the line segment with the first and last points as end points; this point is obviously farthest on the curve from the approximating line segment between the end points. If the point is closer than ε to the line segment, then any points not currently marked to be kept can be discarded without the simplified curve being worse than ε.

If the point farthest from the line segment is greater than ε from the approximation then that point must be kept. The algorithm recursively calls itself with the first point and the farthest point and then with the farthest point and the last point, which includes the farthest point being marked as kept.

When the recursion is completed a new output curve can be generated consisting of all and only those points that have been marked as kept.

The effect of varying epsilon in a parametric implementation of RDP

Non-parametric Ramer–Douglas–Peucker

The choice of ε is usually user-defined. Like most line fitting / polygonal approximation / dominant point detection methods, it can be made non-parametric by using the error bound due to digitization / quantization as a termination condition.[1]

Pseudocode

(Assumes the input is a one-based array)

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

Link: https://karthaus.nl/rdp/

Application

The algorithm is used for the processing of vector graphics and cartographic generalization. It does not always preserve the property of non-self-intersection for curves which has led to the development of variant algorithms.[2]

The algorithm is widely used in robotics[3] to perform simplification and denoising of range data acquired by a rotating range scanner; in this field it is known as the split-and-merge algorithm and is attributed to Duda and Hart.[4]

Complexity

The running time of this algorithm when run on a polyline consisting of $n-1$ segments and $n$ vertices is given by the recurrence $T(n)=T(i+1)+T(n-i)+O(n)$ where $i\in \{1,\ldots ,n-2\}$ is the value of index in the pseudocode. In the worst case, $i=1$ or $i=n-2$ at each recursive invocation and this algorithm has a running time of $\Theta (n^{2})$ . In the best case $i=\lfloor n/2\rfloor$ or $i=\lceil n/2\rceil$ at each recursive invocation in which case the running time has the well-known solution (via the master theorem for divide-and-conquer recurrences) of $O(n\log n)$ .

Using (fully- or semi-)Dynamic convex hull data structures, the simplification performed by the algorithm can be accomplished in $O(n\log n)$ time.[5]

Similar algorithms

Alternative algorithms for line simplification include:

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

References

Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung (2012). "A novel framework for making dominant point detection methods non-parametric". Image and Vision Computing. 30 (11): 843–859. doi:10.1016/j.imavis.2012.06.010.
Wu, Shin-Ting; Marquez, Mercedes (2003). "A non-self-intersection Douglas-Peucker algorithm". 16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003). Sao Carlos, Brazil: IEEE. pp. 60–66. CiteSeerX 10.1.1.73.5773. doi:10.1109/SIBGRA.2003.1240992. ISBN 978-0-7695-2032-2.
Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). A comparison of line extraction algorithms using 2D range data for indoor mobile robotics (PDF). Autonomous Robots. 23 (2). pp. 97–111. doi:10.1007/s10514-007-9034-y.
Duda, Richard O.; Hart, Peter E. (1973). Pattern classification and scene analysis. New York: Wiley. ISBN 0-471-22361-1.
Hershberger, John; Snoeyink, Jack (1992). Speeding Up the Douglas-Peucker Line-Simplification Algorithm (PDF) (Technical report).

External links

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung (2012). "A novel framework for making dominant point detection methods non-parametric". Image and Vision Computing. 30 (11): 843–859. doi:10.1016/j.imavis.2012.06.010.

[2] Wu, Shin-Ting; Marquez, Mercedes (2003). "A non-self-intersection Douglas-Peucker algorithm". 16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003). Sao Carlos, Brazil: IEEE. pp. 60–66. CiteSeerX 10.1.1.73.5773. doi:10.1109/SIBGRA.2003.1240992. ISBN 978-0-7695-2032-2.

[3] Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). A comparison of line extraction algorithms using 2D range data for indoor mobile robotics (PDF). Autonomous Robots. 23 (2). pp. 97–111. doi:10.1007/s10514-007-9034-y.

[4] Duda, Richard O.; Hart, Peter E. (1973). Pattern classification and scene analysis. New York: Wiley. ISBN 0-471-22361-1.

[5] Hershberger, John; Snoeyink, Jack (1992). Speeding Up the Douglas-Peucker Line-Simplification Algorithm (PDF) (Technical report).