Douglas-Peucker-Algorithmus
Der Ramer-Douglas-Peucker-Algorithmus wird verwendet, um ein Polygon oder eine Polylinie durch Entfernen von Punkten zu vereinfachen . Der Algorithmus wurde 1973 von David H. Douglas und Thomas K. Peucker veröffentlicht. Er wird bei der Komprimierung von Vektordaten und der kartografischen Verallgemeinerung verwendet .
Prinzip
Eine Polylinie (n Punkte) kann vereinfacht und durch eine einzelne Linie (zwei Punkte) ersetzt werden, wenn der Abstand ihrer Punkte von der durch die Enden der Polylinie gebildeten Linie am weitesten von einem bestimmten Schwellenwert entfernt ist.
Der Algorithmus arbeitet rekursiv nach der Methode „ Teilen und Erobern “.
Bei der Initialisierung wählen wir den ersten und den letzten Punkt (Fall einer Polylinie) oder einen beliebigen Punkt (Fall eines Polygons) aus. Dies sind die Anfangsgrenzen.
Bei jedem Schritt werden alle Punkte zwischen den Anschlüssen durchlaufen und der Punkt ausgewählt, der am weitesten von dem von den Anschlüssen gebildeten Segment entfernt ist:
- Wenn zwischen den Grenzwerten kein Punkt liegt, endet der Algorithmus.
- Wenn dieser Abstand unter einem bestimmten Schwellenwert liegt, werden alle Punkte zwischen den Grenzwerten gelöscht.
- Wenn es größer ist, kann die Polylinie nicht direkt vereinfacht werden. Der Algorithmus wird rekursiv an zwei Unterteilen der Polylinie aufgerufen: vom ersten Terminal zum entfernten Punkt und vom entfernten Punkt zum letzten Terminal.
Pseudocode
fonction DouglasPeucker(points[1..n], ε) // Trouve l'indice du point le plus éloigné du segment dmax = 0 index = 0 pour i = 2 à n - 1 d = distance du points[i] au segment [points[1], points[n]) si d > dmax index = i dmax = d // Si la distance dmax est supérieure au seuil, appels récursifs si dmax > ε // Appel récursif de la fonction recPoints1[1..k] = DouglasPeucker(points[1…index], ε) recPoints2[1..m] = DouglasPeucker(points[index…n], ε) // Construit la liste des résultats à partir des résultats partiels renvoie la concaténation de recPoints1[1…k-1] et recResults2[1…m] sinon // Tous les points sont proches → renvoie un segment avec les extrémités renvoie [points[1], points[n]]Komplexität
Beachten Sie, dass der Algorithmus notwendigerweise endet, da im schlimmsten Fall die Polylinie (oder das Polygon) nicht vereinfacht werden kann und jeder durch die Rekursion gebildete Zweig endet, wenn die Grenzen nicht durch einen Knoten getrennt sind (Fall 1).
Im besten Fall liegt die Komplexität darin, dass bei jeder Iteration die Anzahl der Rekursionszweige mit zwei multipliziert wird und alle Punkte besucht werden. Der schlimmste Fall ist, weil er dem Fall entspricht, in dem jedes Segment auf der Ebene des zweiten Punktes geschnitten wird. Wir gehen daher in der ersten Iteration n-2 Punkte durch, in der zweiten n-3 Punkte usw.
Durch Verwendung einer dynamischen Datenstruktur zur Darstellung einer konvexen Hüllkurve kann der Algorithmus im schlimmsten Fall implementiert werden.
Siehe auch
Der Algorithmus von Visvalingam (1992) liefert ebenfalls sehr gute Ergebnisse, sogar noch besser
siehe diese einfache Beschreibung
oder dieser ganze Artikel
Anmerkungen und Referenzen
- David H. Douglas und Thomas K. Peucker, „ Algorithmen zur Reduzierung der Anzahl von Punkten, die zur Darstellung einer digitalisierten Linie oder ihrer Karikatur erforderlich sind “, Cartographica: The International Journal for Geographic Information and Geovisualization , University of Toronto Press, vol. 10, n o 2 1973, p. 112-122
- Hershberger, John; Snoeyink, Jack (1992). Beschleunigung des Douglas-Peucker-Algorithmus zur Linienvereinfachung (PDF) (Technischer Bericht).