Das Kefk Network Wiki befindet sich im Testbetrieb.

Douglas-Peucker-Algorithmus

Aus Kefk.

Wechseln zu: Navigation, Suche

Der Douglas-Peucker-Algorithmus ist ein Algorithmus zur Kurvenglättung (engl. weeding) bzw. Punktausdünnung. Die Ausgangsform des Algorithmus wurde im Jahr 1973 von David Douglas and Thomas Peucker entwickelt.

Inhaltsverzeichnis

Idee

Das Ziel des Algorithmus ist eine, durch eine Folge von Punkten oder Strecken gegebene, Kurve durch Weglassen einzelner Punkte zu vereinfachen. Dabei soll die Gestalt der Kurve als solche jedoch erhalten bleiben. Es wird nicht die Anzahl der Zielpunkte gesteuert, sondern es wird ein Abstandmaß für den maximalen Abstand zwischen den Punkten der Ausgangskurve und der Zielkurve angegeben.

Der Algorithmus erzeugt nun eine Approximationskurve bestehend aus einer Teilmenge der Punkte der Ausgangskurve. Bei der Erzeugung der Kurve wird die Ausgangskurve sukzessiv in Abschnitte unterteilt, die dann den Algorithmus als eigene Aufgabe durchlaufen. Die Zielkurve entsteht aus den einzelnen approximierten Abschnitten derart, dass kein Punkt der Ausgangskurve weiter von der Zielkurve entfernt liegt, als das vorgegebene Abstandsmaß. Der Algorithmus realisiert damit einen Ansatz nach dem Prinzip Teile und Herrsche.

Algorithmus

Bild:Douglas Peucker.png
Linienglättung nach dem Douglas-Peucker-Algorithmus

Gegeben ist die Ausgangskurve als geordnete Menge von Punkten oder Strecken

K: \{P_1, \dots, P_i, \dots, P_n\}\quad bzw. \quad K: \{\overline{P_{i}\,P_{i+1}}\},\; i = 1\dots n-1

sowie das Abstandsmaß \varepsilon > 0. Da im Folgenden mit der Punktmenge operiert wird, müssen gegebenenfalls die Punkte aus den Strecken extrahiert und in einer Punktmenge angeordnet werden. Die Ausgangskurve ist im Bild in Schritt 0 dargestellt.

Approximation eines Abschnitts

Aus der gegebenen Punktmenge K:\{P_1, \dots, P_n\}\quad wird aus den Punkte P1 und Pn eine Strecke gebildet (im Bild a). Falls mehr als zwei Punkte in der Punktmenge waren, wird nun der Punkt Pm mit 2\leq m\leq n-1 gesucht, welcher den größten orthognonalen Abstand von der Strecke \overline{P_1\,P_n} hat:

d_{max}= \max_{i=2\dots n-1}d_{orthogonal}\left(P_i, \overline{P_1P_n}\right) = \max_{i=2\dots n-1}d\left(P_i, P_1 P_n\right)

Im Bild ist dies der Punkt c mit dem Abstand b. Ist d_{max} \leq \varepsilon oder die Punktemenge K nur 2 Elemente groß, so wird die Ergebnismenge als

K': \{P_1, P_n\}\quad

definiert und die Funktion verlassen. Diese Punktmenge repräsentiert nun die aktuelle Approximationskurve. Anderenfalls fährt man mit dem folgenden Schritt fort.

Bereichsteilung und Rekursion

Es wird eine Aufteilung von K in die Mengen

K_{1}: \{P_1, \dots, P_m\}\quad und \quad K_{2}: \{P_m, \dots, P_n\}

vorgenommen und der Algorithmus mit diesen beiden Mengen als Ausgangskurve jeweils rekursiv aufgerufen (Schritte 2 und 3 im Bild). Die Ergebnismengen K'1 und K'2 werden nun verwendet, um die Ergebnismenge der Funktion zu bilden.

K': \{K'_1 \cup K'_2\}\quad

Ergebnis

Die Ausgabe des Algorithmus also rekursiv erzeugt, in dem alle approximierten Teilabschnitte vereinigt werden, wobei die doppelt vorkommenden Punkte eliminiert werden müssen. Die Indizes aller Punkte sind dann automatisch aufsteigend sortiert und kommen nur einmal vor. Das Ergebnis nach Abschluss aller rekursiven Aufrufe ist die Zielmenge K' der Punkte, welche die Zielkurve repräsentieren:

K': \{P_1, P_{j_1}, \dots, P_{j_i}, P_n\},\;j_i \in [2, n-1],\;j_i > j_{i-1},\;P_{j_i} \in K

Diese Kurve liegt so, dass für jeden Punkt der Ausgangskurve der Abstand zur Zielkurve kleiner als das Abstandsmaß \varepsilon ist (im Bild Schritt 4).

Pseudocode 

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[2])) 
  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


Anwendung

Der Algorithmus findet Anwendung bei der Verarbeitung von Vektorgrafik und der Generalisierung.

Wikipedia
 Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Douglas-Peucker-Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.
Von „http://www.kefk.org/wiki/Douglas-Peucker-Algorithmus“
Persönliche Werkzeuge