Kubische Splines

[ähM_Key]

Hi!

Ich habe im Netz viele Lösungen gefunden, wie man bei z.B. folgenden (in der Reihenfolge) gegebenen Punkten einen Kubischen Spline erzeugen kann:

(0;0)
(1;2)
(3;2)
(4;0)
Soweit kein Problem, da die X-Koordinaten imme größer werden.

Nun möchte ich aber folgende Punkte (in der Reihenfolge) abfahren:

(0;0)
(1;2)
(3;2)
(2;0)
D.h. mit einer Funktion Y(X) ist das nicht mehr machbar (da es in diesem Fall 2 Y Werte für einen X-Wert gibt).
-> Ich bräuchte eine parametriesierte Funktion X(t); Y(t).

Ist das mit kubischen Splines realisierbar oder muss man auf Bezier&Co ausweichen? Wenn ja wie?
(Oder hat jemand ne Idee, wie man die Anfasserpunkte bei Bezier gut automatisch generieren kann?)

Danke, Gruß, MK

[ogni42]

Vielleicht reicht es Dir ja (auch wenn der gefahrene Weg etwas länger wird), wenn Du einfach zwischen zwei Punkten ein Polynom dritten Grades (also y = ax^3+bx^2+cx+d) einsetzt. In den Punkten kannst Du die Steigungen noch vorgeben und das dann abschnittsweise lösen.

[SprinterSB]

Mit Polynomen kann es nicht gehen, weil die resultierende Kurve keine Funktion ist (die Kurze kehrt irgendwo ihre Richtung von links→rechts zu rechts→links um).

So was sollte mit quadratischen Bézier-Kurven gehen.

Dazu verbindest du zunächst die Punkte mit Linien und bekommst ein Polygonzug, bzw ein Vektorzug.

In jedem Punk bestimmst du dann die Tangente an die zu erstellende Kurve. Das machst du so, daß die Tangente gleichen Winkel zu den beiden jeweils anliegenden Polygonzug-Segmenten hat.

Diese Tangenten schneiden sich in Punkten, die du mit den Punken deiner Kurze als Kontrollpolygon für die quadratischen Bézierkurven (http://de.wikipedia.org/wiki/B%C3%A9zierkurve#Quadratische_B.C3.A9zierkurven_.2 8n.3D2.29) nimmst.

[ähM_Key]

Ja, also ich hatte das Problem schon optimal gelößt, mir ist es nur nicht aufgefallen, weil die Kurve noch nicht schön genug war ;)
Habe festgestellt, dass ich Catmull-Rom Splines (wie von SprinterSB beschrieben) verwendet habe, wobei die Geschwindigkeit des Roboters und der Punkteabstand den Faktor Tau beeinflussen. Nur darf man bei engen Kurven halt nicht zu schnell Fahren, weil sonst unschöne Hacken entstehen.
Würde euch das Program ja gerne zeigen, geht aber ni, weil Wettbewerb ;)

MK

[SprinterSB]

Das Verfahren hat aber den Pferdefuß, daß das nicht geht, wenn zwei benachbarte Tangenten parallel sind. Und wenn sie "fast" parallel sind, wird die Kurve sehr lange mit einer scharfen Kehre im Mittelteil.

Evtl ist es also besser, kubische Béziers zu verwenden und an das Hilfspolygon die Nebenbedingung zu stellen, daß das Minimum der Krümmung (http://de.wikipedia.org/wiki/Kr%C3%BCmmung#Berechnung_der_Kr.C3.BCmmung_f.C3.BC r_ebene_Kurven) maximal ist für die Kurve. Damit wird die Kurve so offen als möglich und man kann mit maximaler Geschwindigkeit (vergleichen mit allen anderen kubischen B) durchflitzen.

Oder man setzt noch eins oben drauf und nimmt nicht die Krümmung als Maß der Dinge, sondern wirklich die Zeit, die der Robbi braucht. Dann geht's Richtung Variationsrechnung (http://de.wikipedia.org/wiki/Variationsrechnung), und man sucht so was wie ne Brachistochrone (http://de.wikipedia.org/wiki/Brachistochrone). Man sucht dann also nicht den Weg, der maximale Geschwindigkeit erlaubt, sondern den zeitschnellsten Weg.