Spline

Grundidee und Bedeutung

Ein Spline n-ten Grades, auch Polynomzug genannt, ist eine Funktion, die abschnittsweise aus Polynomen höchstens n-ten Grades besteht. Die Übergangsstellen zwischen zwei Polynomstücken heißen Knoten. Dort gelten Glattheitsbedingungen; häufig wird verlangt, dass ein Spline n-ten Grades (n−1)-mal stetig differenzierbar ist. Funktionswert und Ableitungen bis zu dieser Ordnung schließen dann ohne Sprung aneinander an. Bestehen alle Abschnitte aus linearen Funktionen, spricht man von einem linearen Spline oder Polygonzug. Entsprechend gibt es quadratische, kubische und höhergradige Splines.

Splines dienen vor allem zur Interpolation, also zum Ermitteln einer Funktion, die vorgegebene Werte genau annimmt, und zur Approximation, also zur näherungsweisen Darstellung von Daten oder Formen. Weil sie stückweise definiert sind, sind sie flexibler als ein einziges Polynom, bleiben aber vergleichsweise einfach und glatt. Bei der Spline-Interpolation werden starke Schwingungen vermieden, wie sie bei Polynomen hohen Grades auftreten können (Runges Phänomen). Splines werden außerdem im CAD zur Beschreibung von Kurven und, in mathematisch entsprechender Weise, von Flächen eingesetzt.

Spline-Raum, Basis und Ordnung

Sei τ = (τᵢ)ᵢ₌₀,…,ₙ₋₁ eine streng wachsende Knotenfolge. Eine Funktion p: [τ₀, τₙ₋₁[ → ℝ heißt stückweise Polynomfunktion mit Maximalgrad d, wenn sie sich in jedem Teilintervall [τᵢ, τᵢ₊₁[ als Polynom höchstens d-ten Grades darstellen lässt. Der Spline-Raum S_{d,τ} ist der Vektorraum aller solchen Funktionen, die zusätzlich (d−1)-mal stetig differenzierbar sind.

Zur Darstellung verwendet man abgeschnittene Potenzfunktionen (u)₊ᵈ = 0 für u < 0 und (u)₊ᵈ = uᵈ für u ≥ 0. Für d = 0 ergibt sich die Sprungfunktion, für d = 1 die Rampenfunktion; für d ≥ 1 ist die Funktion (d−1)-mal stetig differenzierbar. Jeder Spline p ∈ S_{d,τ} besitzt die Form p(u) = Σᵢ₌₀ᵈ c_{i,0}(u−τ₀)₊ⁱ + Σⱼ₌₁ⁿ⁻² c_{d,j}(u−τⱼ)₊ᵈ. Die Funktionen (u−τ₀)₊ⁱ für i = 0,…,d und (u−τⱼ)₊ᵈ für j = 1,…,n−2 bilden daher eine Basis von S_{d,τ}. Der Raum hat die Dimension n+d−1.

An ausgewählten Knoten kann man die Glattheit durch zusätzliche Basisfunktionen niedrigeren Grades gezielt verringern. In der B-Spline-Darstellung geschieht dies über mehrfach vorkommende Knoten. Dann gilt τᵢ ≤ τᵢ₊₁ sowie τᵢ < τᵢ₊d₊₁. Verschiedene Spline-Arten unterscheiden sich wesentlich durch die gewählte Basis des Spline-Raums.

Grad d und Ordnung k eines Splines hängen durch k = d+1 zusammen.

Kubische Splines und Anwendungen

Kubische Splines bestehen aus Polynomabschnitten höchstens dritten Grades. Für jeden Abschnitt können Randbedingungen als Punkte sowie als Werte der ersten und zweiten Ableitung vorgegeben werden. Diese Ableitungen bestimmen unter anderem Steigung und Krümmung beziehungsweise den Kurvenradius. Dadurch lässt sich über die gesamte Kurve eine stetige Krümmung erreichen.

Diese Eigenschaft ist beispielsweise bei Achterbahnen wichtig, um ruckartige Wechsel der Beschleunigung zu vermeiden und Querbeschleunigungen allmählich aufzubauen. Kubische Splines werden auch bei der genauen Verlegung von Hochgeschwindigkeits-Eisenbahnstrecken sowie beim Entwurf von Freiformkurven und Freiformflächen im Schiff-, Flugzeug- und Automobilbau verwendet. Burmester-Schablonen stellen kubische Splines dar und dienen zum Zeichnen von Ausgleichskurven für Wertescharen.

B-Spline-Basis und Berechnung

B-Spline bedeutet Basis-Spline. Die B-Spline-Basis ist numerisch stabil, durch Rekursion berechenbar und besitzt einen kompakten Träger: Eine Basisfunktion ist nur in einem kleinen Intervall von null verschieden. Deshalb wirken sich Änderungen ihrer Koeffizienten nur örtlich aus.

Die B-Spline-Basisfunktionen N_{i,p,τ} des Grades p werden für i = 0,…,n−p−2 und einen Knotenvektor τ = (τ₀,…,τₙ₋₁) mit n ≥ 2p definiert. Ihre Definition mithilfe dividierter Differenzen lautet N_{i,p,τ}(u) = (τ_{i+p+1}−τᵢ)[τᵢ,…,τ_{i+p+1}]{ū}(ū−u)₊ᵖ. Ihr Träger liegt innerhalb von [τᵢ,τ{i+p+1}]. Sind alle beteiligten Knoten verschieden, ist N_{i,p,τ} (p−1)-mal stetig differenzierbar.

Wichtige Eigenschaften sind:

• Nichtnegativität: N_{i,p,τ}(u) ≥ 0.

• Lokaler Träger: N_{i,p,τ}(u) > 0 für u ∈ ]τᵢ,τ_{i+p+1}[ und N_{i,p,τ}(u) = 0 außerhalb von [τᵢ,τ_{i+p+1}[.

• Zerlegung der Eins: Σᵢ₌₀ⁿ⁻ᵖ⁻² N_{i,p,τ}(u) = 1 für u ∈ [τₚ,τ_{n−p−1}[.

Für die praktische Berechnung dient die Rekursion von de Boor, Cox und Mansfield: N_{i,0,τ}(u) = 1 für u ∈ [τᵢ,τᵢ₊₁[, sonst 0, N_{i,p,τ}(u) = ((u−τᵢ)/(τ_{i+p}−τᵢ))N_{i,p−1,τ}(u) + ((τ_{i+p+1}−u)/(τ_{i+p+1}−τ_{i+1}))N_{i+1,p−1,τ}(u). Die Knoten erfüllen τᵢ ≤ τᵢ₊₁ und τᵢ < τᵢ₊ₚ. Die Ableitung ist N′{i,p,τ}(u) = (p/(τ{i+p}−τᵢ))N_{i,p−1,τ}(u) − (p/(τ_{i+p+1}−τ_{i+1}))N_{i+1,p−1,τ}(u). Entsteht wegen mehrfacher Knoten ein Nenner null, ist die zugehörige Funktion automatisch die Nullfunktion; der entsprechende Summand wird deshalb durch null ersetzt.

B-Spline-Kurven und de-Boor-Algorithmus

Eine B-Spline-Kurve C(u) mit Maximalgrad p wird durch Kontrollpunkte Pᵢ, auch De-Boor-Punkte genannt, und B-Spline-Basisfunktionen festgelegt: C(u) = Σᵢ₌₀ⁿ⁻ᵖ⁻² PᵢN_{i,p,τ}(u), u ∈ [τₚ,τ_{n−p−1}[. In der Ebene sind die Kontrollpunkte zweidimensional, im Raum dreidimensional. Die Kurve liegt stets in der konvexen Hülle der De-Boor-Punkte und wird somit von ihnen eingeschlossen. Wegen der Lokalität beeinflusst Pᵢ die Kurve nur im Intervall [τᵢ,τ_{i+p+1}[. Sind die ersten p+1 Knoten gleich, gilt P₀ = C(τₚ); sind die letzten p+1 Knoten gleich, gilt P_{n−p−2} = C(τ_{n−1−p}).

Zur effizienten Auswertung einer Kurve wird meist der de-Boor-Algorithmus eingesetzt. Zunächst sucht man ein Intervall [τᵢ,τᵢ₊₁[, das u enthält. Anschließend werden Hilfsgrößen aus den zugehörigen Kontrollpunkten initialisiert und wiederholt durch gewichtete Mittel ersetzt: α_{l,j} = (u−τ_{i+j})/(τ_{i+j+l}−τ_{i+j}), q_{l,j} = q_{l−1,j}(1−α_{l,j}) + q_{l−1,j+1}α_{l,j}. Bei gleichen Knoten setzt man q_{l,j} = q_{l−1,j}. Das Endergebnis ist C(u) = q_{d,0}. Sollen an derselben Stelle u mehrere Splines ausgewertet werden, die sich nur in den Punkten Pᵢ unterscheiden, kann die direkte Summe mit bereits berechneten Basiswerten effizienter sein.

Bézierkurven besitzen eine ähnliche Kontrollpunktdarstellung, beruhen jedoch auf Bernsteinpolynomen. Das Blossoming stellt einen einfachen Zusammenhang zwischen Bézier- und B-Spline-Kurven her.

Flächen und Verallgemeinerungen

Eine B-Spline-Fläche verwendet zwei Parameter und zwei B-Spline-Basen. Für Maximalgrade p und q, Knotenvektoren τ und μ sowie Kontrollpunkte Pᵢⱼ gilt C(u,v) = Σᵢ₌₀ⁿ⁻ᵖ⁻² Σⱼ₌₀ᵐ⁻ᑫ⁻² PᵢⱼN_{i,p,τ}(u)N_{j,q,μ}(v). Sie ist über dem Rechteck [τₚ,τ_{n−1−p}] × [μ_q,μ_{m−1−q}] definiert. Ein Kontrollpunkt wirkt nur lokal auf einen entsprechenden rechteckigen Bereich. Werden an beiden Rändern jeder Parameterachse jeweils die ersten beziehungsweise letzten p+1 oder q+1 Knoten gleichgesetzt, interpoliert die Fläche ihre vier Eckkontrollpunkte.

Neben B-Splines gibt es weitere Varianten, etwa den kubisch hermiteschen Spline. NURBS verallgemeinern Splines, indem sie stückweise rationale Funktionen statt Polynomen verwenden. Mit NURBS-Kurven lassen sich Kreise exakt darstellen.