Also ist eine Klasse CubicSpline entstanden, soweit ausgearbeitet, dass sie irgendwann man in die anderen Werkzeuge integriert werden kann.
Mein CubicSpline kann als "Natural Spline" laufen - dann werden für die Randpunkte die jeweilige Steigung (Tangentenwinkel, 1. Ableitung) aus dem Spline berechnet -, oder als "Clamped Spline" - da wird die Steigung der Randpunkte vorgegeben.
Der Cubic Spline besteht aus Polynomen 3. Grades, und zwar jeweils unterschiedliche zwischen zwei benachbarten Stützpunkten.
Genauer gesagt existieren zwischen zwei Stützpunkten je 2 Polynome, eines für x und eines für y, in Abhängigkeit eines Parameters t,
also y = f(t) und x = g(t).
An einem Stützpunkt gelten für die hier aneinanderstoßenden Polygone die selben Steigungen (1. Ableitung). Dies wird mit ein wenig Trickserei über die Ermittlung der 2. Ableitung gewährleistet. Es entsteht dabei eine sogenannte Tridiagonalmatrix, die sich geschlossen und sehr einfach lösen lässt.
Die Länge von Splines kann man jedoch nicht in geschlossener Form ermitteln, siehe dxf-Thread. Ich habe numerische Integration nach Simpson benutzt. Damit bekommt man die Länge s für einen bestimmten Wert des Parameters t.
Wenn ich jetzt den Spline abwickle, d.h. in Zusi-gerechte Geradenstückchen zerlege, benötige ich aber die Umkehrfunktion, nämlich den Parameter t als Funktion der Länge s. Denn zur Bestimmung jedes Punktes kann ich nachher nur für t die Funktionen f(t) und g(t) anwenden.
Umkehrfunktionen kann man z.B. über Bisektion ermitteln, sowie es im Absteckrechner für alles und jedes gemacht wird (dort "binäre Iteration" getauft). Da aber schon die Längenberechnung selbst eine Iteration ist (Simpson), könnte eine ausgiebige zweite Iteration spürbar auf die Rechenzeit gehen. Also habe ich mit Nullstellenbestimmung nach Newton-Raphson experimentiert (das Verfahren wird auch bei meiner Implementation der transversalen Mercator-Projektion benutzt). Die dafür benötigte 1. Ableitung liegt eh vor, weil sie für die Längenberechnung schon verwendet wurde. Newton-Raphson konvergiert bereits nach 4 oder 5 Schritten.
Zwei Bildchen:
Zunächst ein Natural Spline mit 4 Stützpunkten (grüne Linie). Den Spline selber sieht man nicht, sondern nur seine Zerlegung in viele kurze Geraden (rote Linie). Beim 2. Punkt sieht man besonders deutlich, dass zwischen 1. und 2. Punkt etwas ausgeholt werden muss, um den 2. Punkt auch zu treffen. Die Steigungen der Randpunkte ergeben sich aus dem Spline, sie sind hier nicht fest vorgegeben.
Als Anwendung schwebt mir, wie im anderen Thread erwähnt, der vereinfachte Bau von Straßen und Flüssen vor. Glücklicherweise müssen Zusi-Straßen ja keine Baurichtlinien erfüllen.
Das andere Bild zeigt einen Clamped Spline, mit nur zwei Punkten. Der Spline muss einen 90°-Bogen modellieren. Die Steigungen der Randpunkte sind jetzt also fest vorgegeben, 0° und 90°.
Was man hier schön sieht, ist dass Splines als Konstruktionselemenmt nur bedingt tauglich sind. Die Tangenten passen zwar, aber von einer ordentlichen Kurve kann kaum die Rede sein. Der klassiche Ansatz aus Klothoide, Kreisbogen und wieder Klothoide ist zwar für den Konstrukteur aufwändiger, kommt aber mit den zwei Vorgabepunkten und den zwei Steigungen aus. Der gezeigte 2-Punkte-Spline würde weitere Stützpunkte benötigen, um eine einigermaßen akzeptable Kurve zu ergeben.
Zwei Bemerkungen:
1. Splines werden in der Computergraphik sehr intensiv genutzt. Sie sind Feld-, Wald- und Wiesen-Standard. Direct3D kann sie zwar nicht, aber schon GDI oder GDI+ beherrschen sie. Wenn man sich zum ersten Mal davor setzt, ahnt man zunächst nicht, dass für ihre Berechnung ein gar nicht so kleiner Aufwand getrieben werden muss.
2. Ich bin immer wieder erstaunt, wie schnell man mit dem Versuch geschlossene mathematische Lösungsansätze zu finden, vor die Wand läuft, und auf numerische Verfahren ausweichen muss, also auf gut deutsch, sich auf's systematische Probieren verlegt.
![:]](./images/smilies/pleased.gif "Freude"){kind=small}
.