Spline


Spline
Beispiel eines Splines mit 8 Knoten
Geflecht: Die Querstreben verhalten sich theoretisch wie Splines

Ein Spline n-ten Grades ist eine Funktion, die stückweise aus Polynomen höchstens n-ten Grades zusammengesetzt ist. Dabei werden an den Stellen, an denen zwei Polynomstücke zusammenstoßen (man spricht auch von Knoten), bestimmte Bedingungen gestellt, etwa dass der Spline (n-1)-mal stetig differenzierbar ist.

Handelt es sich bei dem Spline um eine stückweise lineare Funktion, so nennt man den Spline linear (es handelt sich dann um einen Polygonzug), analog gibt es quadratische, kubische usw. Splines.

Inhaltsverzeichnis

Allgemeines

Der Begriff Spline wurde zuerst in einer englischen Veröffentlichung von Isaac Jacob Schoenberg im Jahr 1946 für glatte, harmonische, zusammengesetzte mathematische Kurven dritten Grades benutzt.

Splines werden vor allem zur Interpolation und Approximation benutzt. Durch die stückweise Definition sind Splines flexibler als Polynome und dennoch relativ einfach und glatt. Dadurch ergeben sich bei der Spline-Interpolation nicht die Nachteile, die durch die starke Oszillation von Polynomen höheren Grades und deren Unbeschränktheit bei der Polynominterpolation entstehen (Runges Phänomen). Splines lassen sich auch gut benutzen, um Kurven darzustellen. Hier finden sie Einsatz im CAD. Mathematisch analog lassen sich auf beide Weisen nicht nur Kurven, sondern auch Flächen beschreiben.

Wortherkunft: Der Begriff stammt aus dem Schiffbau: eine lange dünne Latte (Straklatte, englisch spline), die an einzelnen Punkten durch Molche fixiert wird, biegt sich genau wie ein kubischer Spline mit natürlicher Randbedingung. Die Straklatte ist dabei bestrebt, ihre durch die Biegungen hervorgerufene innere Spannung zu minimieren bzw. zu verteilen.

Kubische Splines

Siehe auch Kubischer C2-Spline und Bikubische Filterung.

Kubische Splines werden unter anderem zur Berechnung des Bahnverlaufes bei Achterbahnen verwendet, um ruckartige Beschleunigungswechsel für die Fahrgäste zu vermeiden. Kubische Splines finden weitere Anwendung bei der exakten Verlegung der Schienen bei Hochgeschwindigkeitsstrecken der Eisenbahn. Auch beim Entwurf von Kurven und Oberflächen (sogenannte „Freiformkurven und -flächen“), wie sie häufig im Schiff-, Flugzeug- und Automobilbau vorkommen, sind Splines von Bedeutung.

Die Eignung von Splines für solche Anwendungen liegt daran, dass sich für jeden Polynomabschnitt Randbedingungen sowohl in Form von Punkten aber auch in Form von Werten für erste und zweite Ableitung (und in Abhängigkeit davon Steigung und Krümmung/Kurvenradius) vorgeben lassen. Dadurch kann erreicht werden, dass die Krümmung entlang der Kurve immer stetig ist. Das hat den Vorteil, dass Querbeschleunigungen beim Abfahren der Kurve immer allmählich aufgebaut werden bzw. an den Knotenpunkten vorgegebene Werte einhalten.

B-Splines

Wie auch der Raum der Polynome ist der Raum der stückweisen Polynome ein Vektorraum und hat eine Basis. Im Kontext numerischer Verfahren, wo Splines häufig eingesetzt werden, ist die Wahl der Basis entscheidend für eventuelle Rundungsfehler und damit für die praktische Einsetzbarkeit. Eine bestimmte Basis hat sich hier als am besten geeignet herausgestellt: sie ist numerisch stabil und erlaubt die Berechnung von Werten der Spline-Funktion mittels einer Drei-Term-Rekursion. Diese so genannten B-Spline-Basisfunktionen haben einen kompakten Träger, sie sind nur auf einem kleinen Intervall von Null verschieden. Änderungen der Koeffizienten wirken sich also nur lokal aus. Splines, die in dieser Basis dargestellt werden, nennt man B-Splines.

Siehe auch: Faltung (Mathematik)

Definition

Die B-Spline-Basisfunktionen N_{i,p,\tau}\ (i=0,\ldots,n-p-2) der Ordnung p mit Knotenvektor \tau = (\tau_0,\ldots,\tau_{n-1}) \quad (n\ge 2\,p) werden durch die Rekursionsformel von de Boor/Cox/Mansfield definiert:[1]

N_{i,0,\tau}(u) = \begin{cases} 1, & u\in\left[\tau_i,\tau_{i+1}\right[ \\ 0, & \mbox{sonst} \end{cases}

und

N_{i,p,\tau}(u) = \frac{u-\tau_{i}}{\tau_{i+p}-\tau_{i}}\,N_{i,p-1,\tau}(u) \;+\; \frac{\tau_{i+p+1}-u}{\tau_{i+p+1}-\tau_{i+1}}\,N_{i+1,p-1,\tau}(u) für p > 0.

Die Elemente des Knotenvektors heißen auch Knotenpunkte (im engl. breakpoints) und müssen die Bedingungen \tau_{i}\le\tau_{i+1} und τi < τi + p erfüllen. Die Ordnung p einer B-Spline-Basisfunktion gibt den Grad für jedes stückweise definierte Polynom innerhalb einer Basis an. Sie ist um eins niedriger als die Anzahl benötigter Koeffizienten.

Im CAD werden fast immer die ersten p und letzten p Knotenpunkte auf den gleichen Wert gesetzt.

Eigenschaften:

Bemerkung:

Die Bedingungen an die Knotenpunkte τi erlauben es, dass in der Rekursionsformel unter Umständen 0 als Nenner auftritt (nämlich wenn τi + p = τi bzw. τi + p + 1 = τi + 1 gilt). Allerdings ist dann die Funktion Ni,p bzw. Ni + 1,p automatisch die Nullfunktion. Auf die entsprechende Fallunterscheidung wird hier verzichtet, man ignoriere die entsprechenden Summanden in diesen Fällen (ersetze sie durch 0). Dies entspricht auch dem Grenzverhalten für z. B. \tau_{i+p}\to\tau_{i}.

B-Spline-Kurve

Eine Spline-Kurve, deren Darstellung auf B-Splines beruht, nennt man B-Spline-Kurve. Bestimmt wird die Kurve durch so genannte De-Boor-Punkte, mit denen sich das Aussehen der Kurve leicht steuern lässt: Die Kurve liegt immer in der konvexen Hülle der De-Boor-Punkte, wird also von ihnen eingeschlossen.

Eine B-Spline-Kurve C(u),\ u\in [\tau_{p},\tau_{n-p+1}] der Ordnung p mit Knotenvektor τ (s. o.) und Kontrollpunkten P_i\ (i=1,\ldots,n-p) (auch De-Boor-Punkte genannt) wird definiert durch

C(u) = \sum_{i=1}^{n-p}\; P_i\,N_{i,p,\tau}(u).

Für Kurven in der Ebene sind die Kontrollpunkte 2-dimensional, für Kurven im Raum 3-dimensional.

Eigenschaften:

  • Lokalität: Der Kontrollpunkt Pi beeinflusst die Kurve nur im Intervall ii + p + 1]
  • Endpunkt-Interpolation: Es ist P1 = Cp), falls der erste Knotenpunkt p-mal wiederholt wird und Pnp = Cnp + 1), falls der letzte Knotenpunkt p-mal wiederholt wird.

Eine ähnliche Darstellung haben Bézier-Kurven. Diese basieren nicht auf der oben genannten Basis, sondern auf den Bernsteinpolynomen. Genau wie bei B-Spline-Kurven die De-Boor-Punkte gibt es hier die Bézier-Punkte, die das so genannte Kontrollpolygon bilden und mit denen man die Kurve leicht graphisch darstellen kann.

B-Spline-Fläche

Eine B-Spline-Fläche der Ordnung p und q mit Knotenvektor \tau = (\tau_{1},\ldots,\tau_{n})\ (n\ge 2p) und \mu = (\mu_{1},\ldots,\mu_{m})\ (m\ge 2q) und Kontrollpunkten (bzw. De Boor Punkten) Pij wird definiert durch

C(u,v) = \sum_{i=1}^{n-p} \sum_{j=1}^{m-q}\; P_{ij}\,N_{i,p,\tau}(u)\,N_{j,q,\mu}(v)

Die Fläche ist definiert über dem Rechteck [\tau_{p},\tau_{n-p+1}] \times [\mu_{q},\mu_{m-q+1}].

Eigenschaften:

  • Lokalität: Der Kontrollpunkt Pij beeinflusst die Fläche nur im Rechteck [\tau_{i},\tau_{i+p}]\times [\mu_{j},\mu_{j+q}]
  • Endpunktinterpolation: Werden die ersten p Knotenpunkte in τ auf den gleichen Wert gesetzt, die letzten p Knotenpunkte in τ auf den gleichen Wert gesetzt, die ersten q Knotenpunkte in μ auf den gleichen Wert gesetzt und die letzten q Knotenpunkte in μ auf den gleichen Wert gesetzt, dann gilt die Endpunktinterpolation, d. h. P1,1 = Cpq), P1,mq = Cpmq + 1), Pnp,1 = Cnp + 1q) und Pnp,mq = Cnp + 1mq + 1)

Weitere Varianten

Neben den B-Splines gibt es weitere Varianten von Splines, beispielsweise den kubisch hermiteschen Spline.

Literatur

  • Carl de Boor: A practical guide to splines. Springer Verlag, New York 1978, ISBN 0-387-90356-9 und ISBN 3-540-90356-9 (Rev. Aufl. von 2001 ISBN 0-387-95366-3)
  • Gerald Farin: Curves and Surfaces for CAGD. A practical guide. 5. Aufl. Academic Press, San Diego 2002 ISBN 1-55860-737-4
  • Günther Nürnberger: Approximation by Spline Functions. Springer Verlag, 1989, ISBN 3-540-51618-2 und ISBN 0-387-51618-2
  • Hartmut Prautzsch, Wolfgang Böhm, Marco Paluszny: Bezier and B-Spline Techniques. Springer Verlag, Berlin 2001 ISBN 3-540-43761-4
  • David Salomon: Curves and Surfaces for Computer Graphics. 2006 Springer Science+Business Media, Inc.; ISBN 0-387-24196-5
  • Isaac Jacob Schoenberg: Contributions to the problem of approximation of equidistant data by analytic functions. Quart. Appl. Math., vol. 4, S. 45–99 und 112–141, 1946.

Weblinks

Einzelnachweise

  1. http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-basis.html
  2. http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-derv.html

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Spline — can refer to:* Flat spline, a device to draw curves * Rotating spline, a mating mechanism on a driveshaft. * Spline (mathematics), a mathematical function used for interpolation or smoothing. * Spline cord, a type of thin rubber cord used to… …   Wikipedia

  • Spline — 〈[splaın] f. 10; EDV〉 durch Kontrollpunkte bestimmte, mit minimaler Krümmung verlaufende Kurve, die mathematisch beschreibbar ist ● Spline Interpolation [engl., „Kurvenlineal“, eigtl. „Keil; Metall , Holzfeder“] * * * Spline   [von engl. spline… …   Universal-Lexikon

  • spline — [splīn] n. [< E Anglian dial., prob. akin to Norw dial. splindra, a large, flat splinter: for IE base see SPLIT] 1. a long, flat, pliable strip, as of wood or metal, esp. one used in drawing curves 2. a) a flat key or strip that fits into a… …   English World dictionary

  • Spline — Spline, n. 1. A rectangular piece fitting grooves like key seats in a hub and a shaft, so that while the one may slide endwise on the other, both must revolve together; a feather; also, sometimes, a groove to receive such a rectangular piece.… …   The Collaborative International Dictionary of English

  • Spline — [splain] der; s, s <aus gleichbed. engl. spline, Herkunft ungeklärt> biegsames Kurvenlineal, das man zum Zeichnen einer glatten Kurve durch vorgegebene Punkte benutzt …   Das große Fremdwörterbuch

  • Spline — Spline. См. Шпонка. (Источник: «Металлы и сплавы. Справочник.» Под редакцией Ю.П. Солнцева; НПО Профессионал , НПО Мир и семья ; Санкт Петербург, 2003 г.) …   Словарь металлургических терминов

  • Spline — 〈[splaın] f.; Gen.: , Pl.: s; EDV〉 durch Kontrollpunkte bestimmte, mit minimaler Krümmung verlaufende Kurve, die mathematisch beschreibbar ist [Etym.: engl., »Kurvenlineal«, eigtl. »Keil; Metall , Holzfeder«] …   Lexikalische Deutsches Wörterbuch

  • spline — “long, thin piece of wood or metal,” 1756, from E.Anglian dialect, perhaps from older Dan. splind or N.Fris. splinj …   Etymology dictionary

  • spline — (izg. splȃjn) m DEFINICIJA mat. funkcija koja ima definirane vrijednosti u određenom broju točaka i kojom se mogu dobiti izglađene vrijednosti u obliku krivulje koja spaja sve zadane točke ETIMOLOGIJA engl …   Hrvatski jezični portal

  • Spline — Cet article possède un paronyme, voir : Spleen. Dans le domaine mathématique de l analyse numérique, une spline est une fonction définie par morceaux par des polynômes. Dans les problèmes d interpolation, la méthode des splines est souvent… …   Wikipédia en Français