2003:D4:B700:8EDB:DE15:B9D5:3E89:76E: /* Algorithmus */

2021-08-16T05:46:09Z

Algorithmus

Neue Seite

Der '''Douglas-Peucker-Algorithmus''' (auch '''Ramer-Douglas-Peucker-Algorithmus''') ist ein [[Algorithmus]] zur Kurven[[Glätten (Mathematik)|glättung]] im Bereich der [[Vektorgrafik]] und [[Generalisierung (Kartographie)|Generalisierung]] von Karten. Das Ziel ist, einen durch eine [[Folge (Mathematik)|Folge]] von [[Punkt (Geometrie)|Punkten]] gegebenen [[Polygonzug (Mathematik)|Streckenzug]] durch Weglassen einzelner Punkte (engl. {{lang|en|weeding}}) so zu vereinfachen, dass die grobe Gestalt erhalten bleibt. Der Grad der Vergröberung wird gesteuert durch Vorgabe des maximalen Abstands zwischen den ursprünglichen Punkten und dem [[Approximation|approximierenden]] Streckenzug. Die Ausgangsform des Algorithmus wurde von [[Urs Ramer]] und (unabhängig) von [[David Douglas (Begriffsklärung)|David Douglas]] und [[Thomas Peucker]] angegeben.

== Algorithmus ==
Der Algorithmus betrachtet den Streckenzug als Ganzes (globaler Ansatz) und schreitet zu feineren Approximationen fort. Dazu wird die Ausgangsfolge geeignet in zwei Abschnitte geteilt, die dann ihrerseits den Algorithmus durchlaufen (siehe [[Rekursion#Formale Typen von Rekursion|Rekursion]]). Der Algorithmus realisiert damit einen Ansatz nach dem Prinzip des [[Teile-und-herrsche-Verfahren]]s.

[[Datei:Douglas Peucker.png|mini|Linienglättung nach dem Douglas-Peucker-Algorithmus]]
Gegeben ist der Ausgangsstreckenzug (Bild 0) als Folge von ''n'' Punkten
: <math>K=(P_1, \dots, P_i, \dots, P_n)</math>
sowie die Toleranz <math>\varepsilon > 0</math>.

Als Approximation von ''K'' wird die Strecke <math>\overline{P_1\,P_n}</math> aus erstem und letztem Punkt betrachtet, '''a''' in Bild 1. Um zu prüfen, ob diese Approximation ausreicht, wird unter den <math>n-2</math> inneren Punkten von ''K'' derjenige Punkt <math>P_m</math> gesucht, welcher den größten Abstand von dieser Strecke hat:
: <math>d_{max}= \max_{i=2\dots n-1}d\left(P_i, \overline{P_1P_n}\right)</math>

In Bild 1 ist dies der Punkt '''c''' mit dem Abstand '''b'''. Ist <math>n=2</math> oder <math>d_{max} \leq \varepsilon</math>, so ist die Approximation ausreichend und die inneren Punkte werden ggf. verworfen. Andernfalls wird die Approximation zu <math>(P_1, P_m, P_n)</math> verfeinert und die beiden Teilfolgen
: <math>K_{1}=(P_1, \dots, P_m)</math>   und   <math>K_{2}=(P_m, \dots, P_n)</math>
werden ihrerseits daraufhin überprüft, ob ihre inneren Punkte verworfen werden können (Bild 2 und 3).

Das Ergebnis des Algorithmus ist der durch die Folge der nicht verworfenen Punkte definierte Streckenzug, blau in Bild 4. Keiner der verworfenen Punkte, grau in Bild 4, hat zum Ergebnis einen Abstand größer als <math>\varepsilon</math>.

=== 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

== Abstandsformel ==
Liegt der Streckenzug (zumindest in guter Näherung) in einer Ebene, so lassen sich die Abstände <math>d_i</math> effizient berechnen, indem man vor der [[Iteration#Informatik|Iteration]] über die inneren Punkte <math>P_i</math> einen in der Ebene liegenden [[Normaleneinheitsvektor]] zur Geraden durch <math>P_1</math> und <math>P_n</math> ermittelt und diesen dann jeweils mit den Verschiebungs[[vektor]]en <math>\overrightarrow{P_1P_i}</math> [[Skalarprodukt|skalar multipliziert]]. In mehr als zwei Dimensionen berechnet man zuerst den Fußpunkt des [[Lot (Mathematik)|Lotes]].

Die Autoren Ramer bzw. Douglas und Peucker hatten die Möglichkeit nicht berücksichtigt, dass der Fußpunkt des Lotes nicht auf der Verbindungslinie liegt, sondern außerhalb, auf ihrer Verlängerung. Dadurch können Punkte wegfallen, die vom Endergebnis einen größeren als den zugesicherten Abstand haben.

== Literatur ==
* Urs Ramer: ''An iterative procedure for the polygonal approximation of plane curves.'' In: ''Computer Graphics and Image Processing.'' Band 1, Nr. 3, 1972, {{ISSN|0146-664X}}, S. 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.'' Band 10, Nr. 2, 1973, {{ISSN|0008-3127}}, S. 112–122.
* Geoffrey Dutton: ''Scale, Sinuosity and Point Selection in Digital Line Generalization.'' In: ''Cartography and Geographic Information Science.'' Band 26, Nr. 1, 1999, {{ISSN|1523-0406}}, S. 33–54, [[doi:10.1559/152304099782424929]] ([http://www.spatial-effects.com/papers/jour/GDutton-CAGIS.pdf GDutton-CAGIS.pdf spatial-effects.com]; PDF).
* Konrad Ebisch: ''A correction to the Douglas–Peucker line generalization algorithm.'' In: ''Computers & Geosciences.'' Band 28, 2002, Nr. 8, {{ISSN|0098-3004}}, S. 995–997, [[doi:10.1016/S0098-3004(02)00009-2]] ([https://web.archive.org/web/20150914113139/http://mappinghacks.com/code/PolyLineReduction Polyline Reduction -- 3DSoftware.com]).

[[Kategorie:Algorithmus]]
[[Kategorie:Computergrafik]]

Douglas-Peucker-Algorithmus - Versionsgeschichte

2003:D4:B700:8EDB:DE15:B9D5:3E89:76E: /* Algorithmus */