Douglas-Peucker-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Douglas-Peucker-Algorithmus (auch Ramer-Douglas-Peucker-Algorithmus) ist ein Algorithmus zur Kurvenglättung im Bereich der Vektorgrafik und Generalisierung von Karten. Das Ziel ist, einen durch eine Folge von Punkten gegebenen Streckenzug durch Weglassen einzelner Punkte (engl. 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 approximierenden Streckenzug. Die Ausgangsform des Algorithmus wurde von Urs Ramer und (unabhängig) von David Douglas und Thomas Peucker angegeben.

Algorithmus[Bearbeiten | Quelltext bearbeiten]

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). Der Algorithmus realisiert damit einen Ansatz nach dem Prinzip des Teile-und-herrsche-Verfahrens.

Linienglättung nach dem Douglas-Peucker-Algorithmus

Gegeben ist der Ausgangsstreckenzug (Bild 0) als Folge von n Punkten

sowie die Toleranz .

Als Approximation von K wird die Strecke aus erstem und letztem Punkt betrachtet, a in Bild 1. Um zu prüfen, ob diese Approximation ausreicht, wird unter den inneren Punkten von K derjenige Punkt gesucht, welcher den größten Abstand von dieser Strecke hat:

In Bild 1 ist dies der Punkt c mit dem Abstand b. Ist oder , so ist die Approximation ausreichend und die inneren Punkte werden ggf. verworfen. Andernfalls wird die Approximation zu verfeinert und die beiden Teilfolgen

  und  

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 .

Pseudocode[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Liegt der Streckenzug (zumindest in guter Näherung) in einer Ebene, so lassen sich die Abstände effizient berechnen, indem man vor der Iteration über die inneren Punkte einen in der Ebene liegenden Normaleneinheitsvektor zur Geraden durch und ermittelt und diesen dann jeweils mit den Verschiebungsvektoren skalar multipliziert. In mehr als zwei Dimensionen berechnet man zuerst den Fußpunkt des 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[Bearbeiten | Quelltext bearbeiten]