Algorithmus zur Pfadvereinfachung und Glättung von 2D Trajektorien

Question

Ich suche nach einem Algorithmus zur Pfadvereinfachung und Glättung für 2D Trajektorien. Also habe ich eine geordnete Liste von 2D Punkten. Diese Punkte sollten vereinfacht werden, z. mit dem Ramer-Douglas-Peucker-Algorithmus. Die Ausgabe muss jedoch glatt sein, daher sollte der resultierende Pfad aus Bezier-Kurven oder Splines konstruiert werden. Gibt es eine Modifikation des Ramer-Douglas-Peucker-Algorithmus, der damit umgehen könnte?

Ich fand einen Pfadvereinfachungsalgorithmus in der paper.js-Bibliothek, die genau das tut, was ich suche: http://paperjs.org/examples/path-simplification/ Aber ich war nicht in der Lage, den Algorithmus aus dem undokumentierten Javascript-Quellcode zu verstehen.

Answer 1

Die Arbeit, die Sie tun wollen fällt in die Kategorie "Kurvenanpassung". Es gibt Tonnen von verschiedenen Algorithmen zur Kurvenanpassung, aber fast alle Kurvenanpassungsalgorithmen können in zwei verschiedene Kategorien unterteilt werden: Interpolation und Approximation. Interpolationsalgorithmen erzeugen eine Kurve, die alle Datenpunkte genau durchläuft, während Approximationsalgorithmen eine Kurve erzeugen, die nahe bei den Datenpunkten liegt. Natürlich existieren auch hybride Algorithmen.

Da die Datenpunkte geglättet werden sollen, sollten Sie nach Approximationsalgorithmen suchen. Für die beiden genannten Algorithmen: RDP-Algorithmus und Schneider-Algorithmus (der in Paper.js) sind beide Approximationsalgorithmen. Also, im Grunde können Sie beide verwenden. Für RDP können Sie, nachdem Sie den vereinfachten Pfad erhalten haben, einen Catmull Rom-Spline oder Overhauser-Spline durch die Scheitelpunkte des vereinfachten Pfads erstellen, um eine glatte Kurve zu erhalten. Sie haben jedoch keine direkte Kontrolle über die Abweichung zwischen dem resultierenden Spline und den Scheitelpunkten im ursprünglichen Pfad.

Für den Schneider-Algorithmus beginnt er mit der Anpassung der Datenpunkte an eine kubische Bezier-Kurve mit Endtangentenbeschränkungen. Wenn die Abweichung zu der resultierenden Kurve zu groß ist, teilt sie die Datenpunkte in zwei "Regionen" auf und passt jede Datenregion mit kubischen Bezier-Kurven mit Endtangens-Nebenbedingungen an. Dieser Vorgang wird wiederholt, bis die Abweichung zu allen kubischen Bezier-Kurven klein genug ist.Als Ergebnis erzeugt es eine Reihe von kubischen Bezier-Kurven, die bestenfalls mit C1-Kontinuität verbunden sind (sehr wahrscheinlich ist es nur G1). Da dieser Algorithmus außerdem die Endtangenten von ursprünglichen Datenpunkten auswertet, beeinflusst das Rauschen in dem Datenpunkt die Endtangentenbewertung und daher die kubische Bezier-Anpassung.

Wenn Sie Zeit mit dem Thema Kurvenanpassung verbringen können, sollten Sie in die kleinste Quadrate Anpassung mit B-Spline-Kurven schauen. Dies erzeugt eine Ausgangskurve mit hoher Kontinuität (beispielsweise C2 für kubische B-Spline-Kurven). Wenn Sie nicht viel Zeit zu verbringen haben, ist Schneiders Algorithmus eine gute Wahl, die ein Gleichgewicht zwischen den Implementierungskosten (wenn Sie sie in einer bestimmten Sprache neu implementieren müssen) und der Qualität der resultierenden Kurve findet.

Answer 2

Was Sie am meisten werden wahrscheinlich nach genannt werden Curve Fitting.

Während der Douglas-Peucker-Algorithmus glättet im Wesentlichen ‚Rauschen‘ aus einem Linienzug durch unnötige Punkte zu entfernen - eine Kurvenanpassung Algorithmus Bezier passen Kurven durch diese Punkte.

Here ist ein hübsches schönes Beispiel auf Youtube und here ist das ursprüngliche Papier, das den Algorithmus selbst beschreibt.

---

Was das Paper.js Beispiel:

• This ist die Github Link für diese bestimmte Funktionalität Sie erwähnt und das ist ziemlich gut kommentiert. Die Forschungsarbeit, die verwendet wurde, ist this.

• Auch ist here eine sehr kurze Diskussion auf der Mailingliste über was verwendet wurde und was nicht (anscheinend Ramer-Douglas-Peucker wurde verwendet aber später entfernt)