Douglas-Peucker algorithm
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 .
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
- Urs Ramer: An iterative procedure for the polygonal approximation of plane curves. In: Computer Graphics and Image Processing. Volume 1, No. 3, 1972, ISSN 0146-664X , pp. 244-256, doi : 10.1016 / S0146-664X (72) 80017-0 .
- David Douglas, Thomas Peucker: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. In: The Canadian Cartographer. Volume 10, No. 2, 1973, ISSN 0008-3127 , pp. 112-122.
- Geoffrey Dutton: Scale, Sinuosity and Point Selection in Digital Line Generalization. In: Cartography and Geographic Information Science. Volume 26, No. 1, 1999, ISSN 1523-0406 , pp. 33-54, doi : 10.1559 / 152304099782424929 . GDutton-CAGIS.pdf
- Konrad Ebisch: A correction to the Douglas-Peucker line generalization algorithm. In: Computers & Geosciences. Volume 28, 2002, No. 8, ISSN 0098-3004 , pp. 995-997, doi : 10.1016 / S0098-3004 (02) 00009-2 . Polyline Reduction - 3DSoftware.com