Douglas Peucker reloaded: GPS Track glätten, vereinfachen oder reduzieren

26 August 2011 von Klaus Bechtold

Vor etwa 4 Jahren, im Dezember 2007, habe ich über dieses Thema schon mal geblogged: Track glätten nach dem Douglas-Peucker-Algorithmus. Damals hatte ich die Methode nach dem bekannten Algorithmus bei GPSies.com eingebaut.

Aufgrund des Anstoßes eines sehr engagierten Benutzers (Johannes aus der Nähe von Halle), musste ich dieses Thema noch einmal aufgreifen. Er lies nicht locker, mir eine mehrstufige Glättung schmackhaft zu machen. Hm, ich bin oft “Vorschlags-Resistent”, aber irgendwann gebe ich dann doch mal nach ;-)

Track glätten – was ist das eigentlich?

Eine GPS Aufzeichnung hat oft Ausreißer, die aufgrund von Reflexionen oder Abschattungen (schlechter GPS-Empfang) entstehen. Zudem entstehen “Punktwolken”, wenn man mal auf einem Fleck stehen bleibt, um sich etwas genauer anzuschauen oder wenn man mal “verschwinden” muss.

Diese Ausreißer und “Punktwolken” gilt es nun zu entfernen. Da eine GPS Aufzeichnung nichts anderes als eine Koordinaten-Reihe ist, können auf den Strecken mathematische Verfahren angewendet werden. Am bekanntesten ist wohl der Douglas-Peucker-Algorithmus.


Quelle und Copyrights: Wikipedia

Wozu das ganze?

Es gibt noch viele GPS Geräte auf dem Markt, die nur eine gewissen Anzahl von Punkten erlauben. Wenn eine Strecke aus beispielsweise 8.000 Punkten besteht und das Gerät aber nur 500 Punkte erlaubt, dann musst sie reduziert werden. Neben der einfachen mathematischen Reduzierung (“Holzhammermethode”, jeder 16. Punkt muss weg), gibt es mit dem D-P-Algorithmus die Möglichkeit, die Strecke “intelligent” zu vereinfachen, um den Streckenverlauf nicht wesentlich zu verändern.

Was ist neu?

Es gibt bei GPSies jetzt 3 Stufen zum Glätten der GPS Tracks:

  1. schwach
  2. mittel
  3. stark

Bei den Stufen ändert sich der “Korridor”, also die Stärke, mit der der Algorithmus angewendet wird.

Wie kann ich das ausprobieren?

Die mehrstufige Glättung wird bei fast allen Download- und Importmöglichkeiten von GPSies angeboten (siehe unter “Optionen einblenden”). Am einfachsten und eindrucksvollsten ist das Resultat jedoch im Streckeneditor zu überprüfen:

  1. wähle (d)eine Strecke aus und klicke auf “Strecke bearbeiten”
  2. klicke auf “Strecke verändern”

Die Strecke wird in den GPSies-Editor geladen. Auf der rechten Seite findest du nun die 3 Buttons, mit denen die Glättung angewendet werden kann. Nach dem Klicken lädt sich die Strecke mit der jeweiligen Vereinfachung neu.

Tipps zum Ausprobieren

  1. merke dir die Anzahl der Punkte und den Streckenverlauf bevor die die Glättung anwendest
  2. beginne mit der schwachen Glättung
  3. überprüfe das Ergebnis
  4. zum Ausprobieren klicke nicht auf “speichern”

  1. — Chris    9. November 2011, 15:55    #

    Hi!

    Was mir bisher am wenigsten gefallen hat, ist das die Suchfunktionen von Portalen wie gpsies zwar schon schön ortsbasierend sind, meist aber anhand des Startpunkts.

    Eine Runde – die 20km von meinem Wohnort entfernt startet, bei mir lang geht, und wieder zurück – finde ich also nicht, wenn ich im Umkreis von 5km eine RUndstrecke von 20km Länge suche.

    Dein Algorithmus für die Verringerung der Punkte macht so ein Problem schonmal leichter handhabbar.
    Wie würdest Du so etwas realisieren? Würdest Du soetwas realisieren für Gpsies?

    PS: Keep going – mir gefällt die Seite gut : )

  2. Klaus    10. November 2011, 08:01    #

    Hallo Chris,

    vielleicht mache ich so etwas später mal. Das ist sehr aufwändig, denn es müssen eine Million Strecken mit im Schnitt 1.000 Geokoordinaten indiziert werden, da kommen zum heutigen Zeitpunkt eine Milliarde Punkte zusammen. Diese Daten müssen in eine Datenbank und dafür benötige ich dann einen weiteren Server und so weiter. Ist manchmal nicht so einfach, wie es auf den ersten Blick aussieht.

    LG, Klaus


Schreibe einen Kommentar (Veröffentlichung erst nach Freischaltung):




* Pflichtfelder

Vor dem Absenden, bitte zuerst "Vorschau" anklicken...



|