Ramer–Douglas–Peucker algorithm

The Douglas -Peucker algorithm (also Ramer -Douglas -Peucker algorithm) is an algorithm for curve smoothing in the Vector and generalization of cards. The objective is a value given by a sequence of points polyline by omitting individual points (English weeding ) to facilitate such a way that the rough shape remains unchanged. The degree of coarsening is controlled by specifying the maximum distance between the original points and the approximating polyline. The initial form of the algorithm is given by Urs Ramer and ( independently ) by David Douglas and Thomas Peucker.

Algorithm

The algorithm considers the polyline as a whole ( global approach ) and proceeds to finer approximations. For this purpose, the output sequence is appropriately divided into two sections, which then in turn the algorithm by running (see recursion). The algorithm thus implements an approach based on the principle of divide and rule.

If the Ausgangsstreckenzug ( image 0) is as a result of n points

And tolerance.

As an approximation of the K line is seen from the first and last point a in Figure 1 to check whether this approximation is sufficient, is among the interior points of K wanted the point, which has the largest distance from this line:

In Figure 1 this is the point C and the distance b. If or, then the approximation is sufficient and the interior points be discarded. Otherwise, the approximation is to be refined and the two sub-sequences

In turn, are then checked whether their interior points can be discarded (Fig. 2 and 3).

The result of the algorithm is defined by the sequence of the non-rejected points lineament blue in Figure 4, none of the discarded points, gray in Figure 4, the result is at a distance greater than.

Pseudocode

Function DouglasPeucker (Point List [ ], epsilon)      / / Find the point with the greatest distance      dmax = 0      index = 0      for i = 2 to (length ( Point List) - 1 )          d = LotrechterAbstand (Point List [ i], Line ( Point List, Point List [end ]))          if d> dmax              index = i              dmax = d        / / If the maximum distance is greater than epsilon, then simplify recursively      if dmax > = epsilon          / / Recursive call          recResults1 [] = DouglasPeucker (Point List [ first .. index ], epsilon)          recResults2 [] = DouglasPeucker (Point List [index ... end ], epsilon)            Build / / Result          Result List [] = { recResults1 [ 1 .. end -1] recResults2 [ 1 .. end ]}      else          Result List [] = { Point List, Point List [end ]}        / / Return the result      return Result List [ ] end distance formula

If the polygonal line (at least to a good approximation ) in a plane, so the distances can be efficiently calculated by carrying before iterating over the points inside an in-plane unit normal vector to the line and determined and this then scalar multiplication with each of the displacement vectors. In more than two dimensions we first calculated the foot of the perpendicular.

The authors Ramer and Douglas and Peucker had the option not considered that the foot of the perpendicular is not on the connection line, but outside, on their extension. This can be omitted points which have a larger than the assured distance from the end result.