Das deutsche Python-Forum

Hallo,

für mein Pygame Malprogramm möchte ich gern die Punkte zwischen zwei beliebigen, vom Grafiktablet zurückgegebenen Cursorpositionen interpolieren. Genau genommen möchte ich aus den letzten 3 oder 4 eingelesenen Punkten eine Funktion/Spline berechnen und zwischen dem letzten und vorletzten Punkt Füllpunkte berechnen.

Idealerweise suche ich eine Funktion, der ich eine Liste von Punkten [(x0, y0), (x1, y1), (x2, y2), ...] sowie eine Anzahl von z.B. 100 übergebe, die damit eine Kurvenfunktion bzw. Gruppe von Funktionen erstellt und mir eine Liste mit 100 (im Beispiel) gleichmäßig auf die Kurvenlänge verteilte Interpolationspunkte zurückgibt. Evtl. sogar ANZAHL Punkte zwischen gegebenen Stützpunkten. Kennt jemand eine geeignete Funktion? Auch bessere Lösungsansätze als meiner (siehe unten) sind gern gesehen!

Ich habe mir bereits Scipys Interpolate Modul angesehen, doch auch die Splines basieren auf Interpolationspolynomen, welche nur Punkte mit stetig steigende x-werten zulassen, andernfalls kommt nonsens heraus, sagt die SciPy-Referenz. Das Grid bringt mir nichts, denn ich möchte einen ebenen Spline und keine interpolierte Fläche.
Bei drei diskreten Punkten P0, P1 und P2 könnte ich mir als workaround vorstellen, die Punkte in der Ebene so zu drehen, dass x1 möglichst mittig zwischen x0 und x2 legt. Dann Zwischenwerte interpolieren und die schließlich um denselben Winkel zurück zu drehen.

Aber wenn es bereits eine Funktion gibt, die beliebig orientierte Punkte zu einem ebenen Spline kombiniert, würde ich die vorziehen.

Grüße,
Michael

Hallo,

leider kann ich dir keinen konkreten Vorschlag in Python geben, aber dein Problem hat Ähnlichkeiten zu jenen aus der Signalverarbeitung (auch der digitalen). Ich würde an deiner Stelle versuchen dies mit einer Polynominterpolation zu lösen. Da hättest du die freiheit überall einzugreifen und genau für dein Problem zu konstruieren. Leider ist diese Thematik (mathematisch) sehr umfangreich, zur Übersicht könnte dir der dazugehörige Wikipediaartikel [1] helfen.

Oft lässt sich ein solches Problem als Minimierungsproblem verstehen.

Einfaches Beispiel für eine Gerade auf diskreten Datensetzen:

x_i = {-2, -1, 0, 1, 2}
y_i = {0.5, 0.5, 2, 3.5, 3.5}

Annäherung durch Gerade: y = a + bx

Als Basis dient eine Fehlerfunktion:

Q = SUM von i=1 bis N von (y_i - f(x_i))^2
=> SUM_i=1^N(y_i -(a + b*x_i))^2

Ziel ist es nun die Fehlerfunktion Q zu minimieren

Also dQ/da = 0 und dQ/db = 0
=> für dQ/da = SUM_i=1^N => SUM_i=1^N y_i = a * SUM_i=1^N 1 + b * SUM_i=1^N x_i
=> für dQ/db = SUM_i=1^N => SUM_i=1^N y_i * x_i = a * SUM_i=1^N x_i + b * SUM_i=1^N x_i^2

Dafür kann man nun auch einen Trick anwenden da Matrix A ([1, x_1],[1, x_2], ... , [1, x_n]) mit SUM...^N von ... gleichwertig.

Also:

A^T*A = ([1,1, ... ,1], [x_1, x_2, ... , x_n]) * ([1, x_1],[1, x_2], ... , [1, x_n]) => ([SUM y_i], [SUM x_i]) = A^T*A*([a], )

Mit dem Beispiel von oben:

SUM y_i = 10
SUM x_i = 9

A = ([1, -2], [1, -1], [1, 0], [1, 1], [1, 2])

A^T*A = ([5, 0], [0, 10])

A^T*y = A^T*A*([a, b]) => ([a],) = (A^T*A)^-1 * A^T*y

Also:
([10], [9]) = ([5, 0], [0, 10]) * ([a], ) => a = 2 und b = 9/10

Die Koeffizienten kannste dann einsetzen und damit beliebig viele Punkte von der Ausgleichsfunktion bestimmen.

Für Parabeln kannst du die Basisfunktion dann erweitern:

y = f(x) = a + b*x + c*x^2 mit Matrix A := ([1, x_1, x_1^2],[..., ..., ...], [1, x_n, x_n^2)

Für ein Polynom 3. Grades dann:

y = a + bx + cx^2 + dx^3

etc.

Ich hoffe es wird klar was ich meine. Leider habe ich keine Funktion im Forum für Mathematische ausdrücke gefunden... Wenn mir die jemand zeigt, kann ich den Beitrag gerne auch noch editieren. Es hilft sicherlich wenn man sich die Formeln mal aufschreibt damit sie leserlich werden :)

Wenn du obrigen Weg nimmst kannst du viel der mathematischen Operationen mit numpy, scipy etc. abdecken. Müsstest also nur eine für dich günstige Basisfunktion finden (evtl. Kreisfunktion / Ellipse).

Was mir gerade noch einfällt:
Es gibt diverse Probleme bei der Polynominerpolation, wenn du z.B. den Grad des Polynoms zu hoch wählst können zwar alle Werte exakt approximiert werden, allerdings sind die Zwischenwerte nonsens. Stell dir z.B. nen Sinus vor und Messwerte der Form x = {pi*n} mit n entahlten in {0, 1, 2, ...}. Eine Gerade währe ausreichen ein Sinus entspricht aber ebenso dem Kriterium.

Weiterhin kannst du obriges Verfahren nochmals iterativ ausführen (Minimierung der Fehlerquadrate) mit einer gewichteten Funktion aus der ersten Berechnung um den tatsächlichen Abstand zu minimieren, nicht nur entlang der y-Achse.

Der Weg lässt sich leicht auch auf 2-Dimensionale Probleme erweitern.

Besten Gruß
Acuda

[1] http://de.wikipedia.org/wiki/Polynominterpolation

Edit: Ich hoffe so viel Mathe ist nicht unangebracht in einem Python-Forum?

Hi Acuda,

vielen Dank für Deine ausführliche Antwort und Herleitung. Das ist eine Menge Stoff, den ich mir mal in Ruhe durchgehen muss.

Polynominterpolation hatte ich, bis auf meinen workaround, eigentlich ausgeschlossen, weil reine Polynome Funktionen von x sind, die eindeutig vom Definitionsbereich in den Wertebereich abbilden. Sprich: es gibt für ein Polynom nicht mehrere Funktionswerte für ein und denselben x-Wert.

Meinst Du mit Deiner Aussage im letzten Satz, dass sich der Weg leicht auf zweidimensionale Probleme erweitern lässt, dass ich damit eben auch die von mir erwähnten beliebigen Punkte in einer Ebene verbinden kann?

Ich habe mein altes C-Heft von 2002 wieder gefunden und dort zu affinen Abbildungen nachgelesen. Wie es aussieht, brauche ich sowas wie ein B-Spline. Eine Suche im Netz brachte mich z.B. zur pycurve Bibliothek:
http://www.pygame.org/project-pycurve-1390-.html
Noch konnte ich sie nicht testen, aber ich bin optimistisch, dass mir diese Bib auch ohne Mathe helfen könnte, was deutlich schneller gehen würde.

Viele Grüße,
Michael

Michael Schneider hat geschrieben:Polynominterpolation hatte ich, bis auf meinen workaround, eigentlich ausgeschlossen, weil reine Polynome Funktionen von x sind, die eindeutig vom Definitionsbereich in den Wertebereich abbilden. Sprich: es gibt für ein Polynom nicht mehrere Funktionswerte für ein und denselben x-Wert.

Anscheinend habe ich ein anderes Verständnis von dem was du machen möchtest. Ich habe das so verstanden, dass du z.B. einen Strich zeichnest und sagen wir mal 5 Punkte bekommst nun aber darin eine Kurve / Gerade reinlegen möchtest um alle 5 Punkte möglichst genau zu treffen, und um dann weitere Stützstellen zu ermitteln.

Bei einem geraden Strich nach unten hättest du dann vermutlich das Problem ja.

Michael Schneider hat geschrieben: Meinst Du mit Deiner Aussage im letzten Satz, dass sich der Weg leicht auf zweidimensionale Probleme erweitern lässt, dass ich damit eben auch die von mir erwähnten beliebigen Punkte in einer Ebene verbinden kann?

Mit einem 2D-Problem würdest du nicht unbedingt dein Problem lösen. damit Ich meinte ursprünglich, dass du dann ein Polynom n-ter Ordnung in 2 Dimensionen (vgl. 3D-Plot) hättest. Also x-y-Koordinaten mit dazugehörigem Wert.

Für ein Polynom 2ter Ordnung in R^2 würde mann z.B. folgende Basisfunktion verwenden können: y = a + bx + cy + dxy + ex^2 + fy^2

Da du aber sowieso einen anderen Weg gefunden hast...

Michael Schneider hat geschrieben: Noch konnte ich sie nicht testen, aber ich bin optimistisch, dass mir diese Bib auch ohne Mathe helfen könnte, was deutlich schneller gehen würde.

Das freut mich das du etwas gefunden hast was dir weiter helfen konnte. Ich hoffe das Mathe-Zeug war oder ist dir vielleicht doch noch mal nützlich. Ich beschäftige mich aktuell mit Bildverarbeitung und freue mich da eigentlich immer wenn es auch mal ein bisschen Hintergrund gibt und nicht nur die Aussage "verwende Funktion xy, dann klappts".

Aber ich werde mir die Lib auch mal anschauen, allerdings mit Augenmerk auf die Implementierung des Euler-Lagrange-Formalismus, danke dafür!

Gruß Acuda