Ramer–Douglas–Peucker algorithm

The Douglas-Peucker algorithm is an algorithm for smoothing curve (Engl. weeding) and Punktausdünnung. Die Ausgangsform des Algorithmus wurde im Jahr 1973 von David Douglas and Thomas Peucker entwickelt. The initial form of the algorithm was established in 1973 by David Douglas and Thomas Peucker.

Idea

The goal of the algorithm is one that through a series of points or lines given, curve by omitting individual points easier. In doing so, the shape of the curve as such but maintained. It is not the number of targets are controlled, but there is a gap measure for the maximum distance between the starting points of the curve and the target curve.

The algorithm now produces an approximation curve consisting of a subset of the starting points of the curve. For the production of the curve, the output curve gradually divided into sections, then the algorithm as a separate task through. The target curve arises from the different sections approximierten so that no starting point of the curve further from the target curve away, as the predetermined distance dimension. The algorithm implemented so that an approach on the principle of divide and rule.

Algorithm

Where is the starting curve as ordered set of points or lines

and the distance dimension \ varepsilon> 0 . Since the following point set with the surgery, the need to points from the line and extracted a point quantity ordered. The output curve is in the picture in step 0.

Pseudo

function DouglasPeucker(PunkteListe[], epsilon)
 // Punkt mit dem maximalen Abstand ermitteln
 dmax = 0
 index = 0
 for i = 2 to (length(PunkteListe) - 1)
  d = OrthogonalerAbstand(PunkteListe[i], Strecke(PunkteListe[1], PunkteListe[end])) 
  if d > dmax
   index = i
   dmax = d
  end
 end
 
 // Abstand prüfen und ggf. in das Ergebnis eintragen
 if dmax >= epsilon
  // rekursiver Aufruf
  rekErgebnis1[] = DouglasPeucker(PunkteListe[1...index], epsilon)
  rekErgebnis2[] = DouglasPeucker(PunkteListe[index...end], epsilon)
  
  // Bilden der Ergebnisliste
  ErgebnisListe[] = {rekErgebnis1[1...end-1] rekErgebnis2[1...end]}
 else
  ErgebnisListe[] = {PunkteListe[1], PunkteListe[end]}
 end
 
 // Ergebnis zurückgeben
 return ErgebnisListe[]
end

Application

The algorithm is used for the processing of vector graphics and generalization.