Douglas-Peucker algorithm

from Wikipedia, the free encyclopedia

The Douglas-Peucker algorithm (also Ramer-Douglas-Peucker algorithm ) is an algorithm for smoothing curves in the area of vector graphics and generalization of maps. The aim is to simplify a route given by a sequence of points by omitting individual points (weeding) so that the rough shape is retained. The degree of coarsening is controlled by specifying the maximum distance between the original points and the approximating route. The initial form of the algorithm was given by Urs Ramer and (independently) by David Douglas and Thomas Peucker.

algorithm

The algorithm considers the route as a whole (global approach) and advances to finer approximations. For this purpose, the output sequence is suitably divided into two sections, which in turn run through the algorithm (see recursion ). The algorithm thus implements a divide- and-conquer approach .

Line smoothing according to the Douglas-Peucker algorithm

The initial route (Fig. 0) is given as a sequence of n points

as well as tolerance .

The distance from the first and last point is considered as an approximation of K , a in Figure 1. To check whether this approximation is sufficient, the point among the inner points of K is searched for which is the greatest distance from this distance:

In Figure 1 this is point c with distance b . If or , the approximation is sufficient and the inner points are rejected if necessary. Otherwise the approximation is refined and the two partial sequences

  and  

are in turn checked to see whether their inner points can be discarded (Figs. 2 and 3).

The result of the algorithm is the path defined by the sequence of non-rejected points, blue in Fig. 4. None of the rejected points, gray in Fig. 4, has a distance greater than .

Pseudocode

function DouglasPeucker(PointList[], epsilon)
    // Finde den Punkt mit dem größten Abstand
    dmax = 0
    index = 0
    for i = 2 to (length(PointList) - 1)
        d = LotrechterAbstand(PointList[i], Line(PointList[1], PointList[end])) 
        if d > dmax
            index = i
            dmax = d
 
    // Wenn die maximale Entfernung größer als Epsilon ist, dann rekursiv vereinfachen
    if dmax > epsilon
        // Recursive call
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
 
        // Ergebnisliste aufbauen
        ResultList[] = {recResults1[1...end-1], recResults2[1...end]}
    else
        ResultList[] = {PointList[1], PointList[end]}
 
    // Ergebnis zurückgeben
    return ResultList[]
end

Distance formula

If the broken line (at least to a good approximation) in a plane, then the distances can efficiently calculate, by before the iteration over the interior points of an in-plane unit normal vector to the line through and determined, and this then in each case with the displacement vectors scalar multiplication . In more than two dimensions, you first calculate the base point of the perpendicular .

The authors Ramer or Douglas and Peucker did not consider the possibility that the base point of the perpendicular is not on the connecting line, but outside, on its extension. This means that points can be omitted that are more than the guaranteed distance from the final result.

literature