Punktsequenz-Interpolation

Question

Wie würden Sie bei einer beliebigen Folge von Punkten im Raum eine glatte, kontinuierliche Interpolation zwischen diesen Punkten erzeugen?

2D- und 3D-Lösungen sind willkommen. Lösungen, die eine Liste von Punkten mit beliebiger Granularität erzeugen, und Lösungen, die Kontrollpunkte für Bezier-Kurven erzeugen, sind ebenfalls willkommen.

Außerdem wäre es cool, eine iterative Lösung zu sehen, die frühe Abschnitte der Kurve annähert, während sie die Punkte erhält, so dass man damit zeichnen kann.

Answer 1

El Catmull-Rom-Verzahnung wird garantiert durch alle Kontrollpunkte geleitet. Ich halte dies für praktischer als die Einstellung von Zwischenkontrollpunkten für andere Arten von Splines.

Este PDF von Christopher Twigg hat eine schöne kurze Einführung in die Mathematik des Splines. Der beste zusammenfassende Satz ist:

Catmull-Rom-Splines haben C1 Kontinuität, lokale Kontrolle und Interpolation, liegen aber nicht innerhalb von der konvexen Hülle ihrer Kontrollpunkte Punkte.

Anders ausgedrückt: Wenn die Punkte eine scharfe Rechtskurve anzeigen, neigt sich der Spline nach links, bevor er sich nach rechts dreht (ein Beispielbild ist in dem Dokument enthalten). Die Enge dieser Kurven ist steuerbar, in diesem Fall über den Tau-Parameter in der Beispielmatrix.

Hier ist anderes Beispiel mit etwas herunterladbarem DirectX-Code.

Answer 2

Eine Möglichkeit ist Lagrange polynominal die eine Methode zur Erzeugung eines Polynoms ist, das alle gegebenen Datenpunkte durchläuft.

Während meines ersten Jahres an der Universität habe ich ein kleines Tool geschrieben, um dies in 2D zu tun, und Sie können Sie finden es auf dieser Seite wird er Lagrange-Löser genannt. Auf der Wikipedia-Seite gibt es auch eine Beispielimplementierung.

Das funktioniert folgendermaßen: Sie haben ein Polynom der Ordnung n, p(x) wobei n die Anzahl der Punkte ist, die Sie haben. Sie hat die Form a_n x^n + a_(n-1) x^(n-1) + ...+ a_0 , donde _ ist tiefgestellt, ^ ist Macht. Diese wird dann in eine Reihe von Gleichungen umgewandelt:

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

Sie wandeln die obige Matrix in eine augmentierte Matrix um und lösen die Koeffizienten a_0 ... a_n . Dann haben Sie ein Polynom, das durch alle Punkte geht, und Sie können nun zwischen den Punkten interpolieren.

Beachten Sie jedoch, dass dies für Ihre Zwecke möglicherweise nicht geeignet ist, da es keine Möglichkeit bietet, die Krümmung usw. anzupassen - Sie sind auf eine einzige Lösung festgelegt, die nicht geändert werden kann.

Answer 3

Werfen Sie einen Blick auf B-Splines . Ihr Vorteil gegenüber Bezier-Kurven ist, dass jeder Teil nur von lokalen Punkten abhängig ist. Das Verschieben eines Punktes hat also keine Auswirkung auf Teile der Kurve, die weit entfernt sind, wobei "weit entfernt" durch einen Parameter des Splines bestimmt wird.

Das Problem mit dem Langrange-Polynom ist, dass das Hinzufügen eines Punktes extreme Auswirkungen auf scheinbar beliebige Teile der Kurve haben kann; es gibt keine "Lokalisierung" wie oben beschrieben.

Answer 4

Haben Sie sich die Unix Verzahnung Befehl? Kann man sie dazu zwingen, das zu tun, was man will?

Answer 5

Leider funktionieren die Lagrange-Interpolation oder andere Formen der Polynominterpolation nicht bei einer beliebigen Anzahl von Punkten. Sie funktionieren nur bei einer Menge, bei der in einer Dimension z. B. x

x _i < x _i+1

Für eine willkürliche Menge von Punkten, z. B. eine Flugroute eines Flugzeugs, bei der jeder Punkt ein Paar (Längengrad, Breitengrad) ist, ist es besser, die Reise des Flugzeugs einfach mit dem aktuellen Längen- und Breitengrad und der Geschwindigkeit zu modellieren. Indem Sie die Geschwindigkeit, mit der sich das Flugzeug drehen kann (seine Winkelgeschwindigkeit), davon abhängig machen, wie nahe es dem nächsten Wegpunkt ist, können Sie eine glatte Kurve erzielen.

Die sich daraus ergebende Kurve wäre weder mathematisch aussagekräftig noch würde sie Ihnen Bézier-Kontrollpunkte liefern. Der Algorithmus wäre jedoch unabhängig von der Anzahl der Wegpunkte rechnerisch einfach und könnte eine interpolierte Liste von Punkten mit beliebiger Granularität erzeugen. Es wäre auch nicht erforderlich, dass Sie den kompletten Satz von Punkten im Voraus bereitstellen, Sie könnten einfach Wegpunkte am Ende des Satzes wie erforderlich hinzufügen.