Ich suche nach Algorithmen, mit Hilfe derer ich den Verlauf einer Kurve glätten kann.

Das Problem: Ich habe eine Kurve, die aus 20.0000-30.000 Punkten besteht. Für den Verlauf der Charakteristik der Kurve sind aber nicht alle Punkte wichtig. Ich muss die Punktzahl jetzt so minimieren, dass nur noch die Punkte übrige bleiben die den Verlauf der Kurve bestimmen.

WICHTIG: Ausreißer dürfen nicht verloren gehen, da sie ein wichtiger Teil der Kurve sind.

Eine mögliche Lösung wäre der Douglas-Peucker-Algorithmus (bei Wikipedia zu finden). Ich brauche aber noch zwei drei weitere Algorithmen.

Bearbeitet 12. Januar 201114 j von Sonne14

Wie unterscheidest du die nichtbestimmenden, unwichtigen Punkte von den wichtigen Ausreißern?

Die unwichtigen Punkte sind die, die mit anderen Punkten ungefähr auf einer linie liegen und somit keine große Beudetung für den Verlauf der Kurve haben und können daher weggelassen werden. Es geht ihr um viele Messungen die zusammen eine Kurve ergeben. Die Ausreißer sind dann die Punkte, an denen etwas schief gelaufen ist und an diesen Stelle muss etwas verbessert werden. Daher sind gerade diese Punkte wichtig.

Der Douglas-Peucker-Algorithmus ist vom Prinzip her schon genau richtig. Allerdings wird die Rechenzeit bei 20.000-30.000 Punkten wahrscheinlich zu lang sein. Es gibt doch bestimmt noch ähnliche Algorithmen.

Wenn Du die Funktion, die den Punkten zu Grunde liegt, dann kannst via Gradientenabsteig oder Downhill-Simplex-Search die Funktion optimieren, so dass ein minimaler quadaratischer Fehler entsteht (lokales Minimum).

evtl Bezier- und B-Splines wären auch noch eine Idee