Mathematik: 3D-Daten interpolieren

[Matze]

Hallo zusammen,

ich habe im Internet recherchiert, aber irgendwie steige ich nicht durch.

Folgende Aufgabenstellung:

Es sind mehrere Punkte mit X-, Y- und Z-Koordinate gegeben. Das können 5, aber auch 500 Punkte sein.
Nun möchte ich anhand der Punkte eine Gleichung aufstellen, um weitere Punkte interpolieren zu können (X und Y einsetzen und Z soll heraus kommen).

Das möchte ich softwaretechnisch lösen, aber die Theorie dazu möchte ich verstehen.

Kann mir das jemand von euch erklären?

Grüße
Matze

[BUG]

Wenn du in die Mathematik einsteigen willst, dann sind Splines das richtige Suchwort.

Eine naive Lösung wäre, die drei nächsten Nachbarn zu suchen (also das umschließende Dreieck) zu suchen und darin nach Distanz zu wichten.

[Medium]

Wenn du nicht auf ein spzefisches Ergebnis aus bist, und einfach nur eine möglichst "natürliche" Interpolation brauchst, lohnt es sich mal Catmull-Rom Splines anzusehen. Die sind vergleichsweise einfach aufgebaut, lösen das Tangentenproblem recht ansehnlich von selbst, und sehr performant zu berechnen. (Die verallgemeinerung von diesen wären Cardinal Splines, welche mehr Spielraum bzgl. des Tangentenverhaltens bieten. Sind natürlich auch eine Ecke komplizierter.)

Tipp, weil ich damit schon mal auf die Nase gefallen bin: Was du bei fast keiner (zumindest keiner sehr aufwändig modifizierten) Lösung haben wirst, sind Equidistante Punkte bei linear wachsendem Laufindex. Es drubbelt sich alles eher in Richtung der Stützpunkte. (Ist je nach Einsatzzweck aber belanglos.)

Freunde sich auch damit an, dass praktisch alle Splines abschnittsweise berechnet werden. Heisst: Du kannst in der Regel nicht einfach dein X einsetzen, sondern musst zwischen zwei bekannten Punkten immer wieder von 0 bis 1 interpolieren. Es lohnt sich daher von Anfang an eine Datenstruktur zu haben, die einem sehr einfach das Segment um einen gewünschten Punkt zurück liefert ohne lange danach zuchen zu müssen.

Bei den meisten Splines ist die Dimensionalität fast egal, da oftmals alle Achsen unabhängig voneinander behandelt werden. Wenn du also eine 2D Lösung hast, ist 3D praktisch geschenkt.

Noch ein Tipp: Von B-Splines würde ich erst mal die Finger lassen. Die Theorie dahinter ist recht heftig, je nach Lage der Datenpukte tendieren die auch teils stark zu "überschwingen" (lange, enge Spikes um einen Datenpunkt herum), aber vor allem sind das approximierende Splines. Heisst: Sie verlaufen nicht zwangsweise genau durch deine Punkte, sondern nähern diese bloß mehr oder weniger stark an. Auch Bezier-Splines sind für deinen Fall aus dem selben Grund vermutlich ungeeignet.

[Matze]

Hallo,

vielen Dank für eure Antworten. Ganz speziell dir, Medium!

Splines scheinen das richtige Schlagwort zu sein. Die "Catmull-Rom Splines" werde ich mir als erstes ansehen. "Überschwingende" Splines wären in meinem Anwendungsfall sehr ungeeignet.

Grüße und einen schönen Abend
Matze