Kubische Splines

Gegeben

Stützpunkte. Wähle

Kurven (Polynome) kleiner Ordnung für den Verlauf innerhalb der

Intervalle.

Kurven erster Ordnung (Geraden) ergeben nur den Linienzug. Ein solcher Linienzug ist -stetig, da die einzelnen Linien an den Stützpunkten dieselben -und -Werte haben.

Kurven zweiter Ordnung (Parabeln) kann man so wählen, daß sie an den Intervallgrenzen einmal stetig differenzierbar (-stetig) sind. Geometrisch bedeutet das, daß dort nicht nur die Orte übereinstimmen, sondern auch die Steigungen. Mit Parabeln lassen sich nur Kegelschnitte darstellen; die Einsatzmöglichkeiten sind also begrenzt.

Kurven dritter Ordnung mit stetigen ersten und zweiten Ableitungen (-stetig) an den Intervallgrenzen (kubische Splines) können zu einer Gesamtkurve mit weichen Übergängen an den Nahtstellen zusammengesetzt werden. ''weich'' heißt, daß das Auge der gezeichneten Kurve nicht mehr ansehen kann, wo die Stützpunkte liegen. Neben der Steigung ist auch die Krümmung identisch. Dies sind die einfachsten Kurven, mit denen sich bereits komplexe Formen erzeugen lassen.

Gesucht:: Approximation einer Kurve , die durch vorgegebene Punkte laufen soll (z.B. für Pfadanimation).
Bemerkung:: ist in parametrisierter Form gegeben (d.h. ), da die explizite Form pro -Wert nur einen -Wert erlaubt.

Die Stützpunkte seien $f(t_{i})$ , die resultierenden Intervalle seien $[t_{i},t_{i + 1}]$ , die für das Intervall zuständige Funktion sei $f_{i} (t)$ , $1 \leq i\leq n-1$ .

Jedes hat die Form

$\begin{eqnarray*} f_{i} (t) & = &f (t_{i}) + a_{i} \cdot (t - t_{i})+ b_{i}\cdo... ...t_{i})^{3}\\ & & t_{i}\leq t \leq t_{i+1}, ~ i=1, \ldots ,n - 1 \end{eqnarray*}$

Es muß gelten

$f_{i}(t_{i+1})$ $f_{i+1}(t_{i+1})$ für $i=1, \ldots, n-2$ gleicher Wert

$f_{i}' (t_{i+1})$ $f_{i+1}' (t_{i+1})$ für $i=1, \ldots, n-2$ gleiche Steigung

$f_{i}'' (t_{i+1})$ $f_{i+1}'' (t_{i+1})$ für $i=1, \ldots, n-2$ gleiche Steigungsänderung

Nach Vorgabe von und $a_{n-1}$ entsteht ein Gleichungssystem mit Gleichungen und Unbekannten $a_{2}, a_{3}, \ldots ,a_{n-2}$ .

Die Werte von und $a_{n-1}$ können z.B. ermittelt werden durch Festlegung $f'' (t_{1})=f'' (t_{n})=0$ (natürliche Spline-Interpolation).

Für die Folge reicht jede monoton wachsende Folge. Geeignet ist z.B. die Folge der euklidischen Abstände zwischen den Stützpunkten. Statt den Abstand $d=\sqrt{dx^{2} + dy^{2}}$ zu berechnen, verwendet man die Näherungsformel $\frac{1}{3}\cdot (\vert dx\vert+\vert dy\vert+2\cdot \max (\vert dx\vert,\vert dy\vert))$ .

Abbildung 7.1: Vom Spline-Algorithmus erzeugte Kurveninterpolation

/****************************************************************************/ /* Spline-Interpolation durch Polynome 3. Grades */ /****************************************************************************/ private static double[] calcfx = new double[MAX_POINTS];// x-Funktionswerte private static double[] calcfy = new double[MAX_POINTS];// y-Funktionswerte private static double[] x = new double[MAX_POINTS]; // x-Koord Stuetzpunkte private static double[] y = new double[MAX_POINTS]; // y-Koord Stuetzpunkte private static double[] t = new double[MAX_POINTS]; // t-Werte Stuetzpunkte /** berechnet Intervallgrenzen */ void besetze_arrays( int point_cnt, // Anzahl der Polygonpunkte Point punkt[]) // Punktliste { int i; double ax,ay,dd; for (i=0; i<point_cnt; i++) { // besetze x- und y-Koords x[i] = (double) punkt[i+1].x; y[i] = (double) punkt[i+1].y; } t[0] = 0.0; // besetze t-Werte mit dem for (i=1; i<point_cnt; i++) { // Euklidischen Abstand ax=Math.abs(x[i]-x[i-1]); // der Stuetzpunke ay=Math.abs(y[i]-y[i-1]); dd = ax + ay; if (ax > ay) dd = dd+2*ax; // Euklid-Naeherungsformel else dd = dd+2*ay; t[i] = t[i-1]+dd/3; } } /** berechnet die Approximation der Kurve */ void curve_fitting( int point_cnt, // point_cnt Stuetzpunkte Point punkt[], // uebergeben im Array punkt int spline_size) // fuer spline_size // Interpolationswerte { int i,n=0; besetze_arrays(point_cnt, punkt); // erzeuge Intervallgrenzen // Gleitkommaversion von punkt // bestimme Interpolationswerte cubic_spline(point_cnt, t, x, spline_size, calcfx); cubic_spline(point_cnt, t, y, spline_size, calcfy); for (i=0; i<spline_size; i++) // und uebertrage sie spline_punkt[i+1] = new Point((int)calcfx[i],(int)calcfy[i]); } /** loest Gleichungssystem zur Bestimmung der Koeffizienten a,b,c */ void cubic_spline( int n, // Anzahl der Stuetzpunkte double t[], double f[], // Stuetzpkte (t[i],f[t[i]]) int spline_size, // Anzahl Interpolationswerte double calcf[]) // Ausgabearray fuer die { // Interpolationswerte int i,j; double a[] = new double[MAX_POINTS]; double b[] = new double[MAX_POINTS]; double c[] = new double[MAX_POINTS]; double delta_t[] = new double[MAX_POINTS]; double D[] = new double[MAX_POINTS]; double m[] = new double[MAX_POINTS]; double k[] = new double[MAX_POINTS]; double bh,dh,e,h,wt,dt; for (i=1; i<n; i++) { delta_t[i] = t[i]-t[i-1]; D[i] = (f[i]-f[i-1])/delta_t[i]; } m[0] = delta_t[2]; delta_t[0] = t[2]-t[0]; h = delta_t[1]; k[0] = ((h + 2*delta_t[0])*D[1]*delta_t[2]+h*h*D[2])/delta_t[0]; for (i=1; i<(n-1); i++) { h = -delta_t[i+1]/m[i-1]; k[i] = h*k[i-1]+3*(delta_t[i]*D[i+1]+delta_t[i+1]*D[i]); m[i] = h *delta_t[i-1] + 2* (delta_t[i] + delta_t[i+1]); } h = t[n-1]-t[n-3]; dh = delta_t[n-1]; k[n-1] = ((dh+h+h)*D[n-1]*delta_t[n-2] + dh*dh*D[n-2])/h; h = -h/m[n-2]; m[n-1] = delta_t[n-2]; m[n-1] = h*delta_t[n-2] + m[n-1]; a[n-1] = (h*k[n-2]+k[n-1])/m[n-1]; for (i=n-2; i>=0; i--) a[i] = (k[i]-delta_t[i]*a[i+1])/m[i]; for (i=1; i<n; i++) { dh = D[i]; bh = delta_t[i]; e = a[i-1]+a[i]-dh-dh; b[i-1] = 2*(dh-a[i-1]-e)/bh; c[i-1] = 6*e/(bh*bh); } wt = 0; j=0; dt = t[n-1]/(double)(spline_size-1); for (i=0; i<spline_size; i++) { while ((t[j+1]<wt)&&(j<spline_size)) j++; h = wt - t[j]; calcf[i] = f[j]+h*(a[j]+h*(b[j]+h*c[j]/3)/2); wt = wt+dt; } calcf[spline_size-1]= f[n-1]; }

$f_{i}(t_{i+1})$	$f_{i+1}(t_{i+1})$	für	$i=1, \ldots, n-2$	gleicher Wert
$f_{i}' (t_{i+1})$	$f_{i+1}' (t_{i+1})$	für	$i=1, \ldots, n-2$	gleiche Steigung
$f_{i}'' (t_{i+1})$	$f_{i+1}'' (t_{i+1})$	für	$i=1, \ldots, n-2$	gleiche Steigungsänderung