Quadratisch/kubische Interpolation

Diese Berechnung dient zur Echtzeit-Interpolation von Benutzereingaben mit einer zu geringen Rate, um ein Schütteln des gesteuerten Gerätes zu vermeiden und eine stetige Bewegung sicherzustellen.

Gegeben sind ein bewegliches Objekt im Zustand ⟪P_1(t_1, s_1, v_1)⟫ und zwei Punkte ⟪P_2(t_2, s_2)⟫, ⟪P_3(t_3, s_3)⟫ mit ⟪t_1<t_2⟫ und ⟪t_2<t_3⟫.

Gesucht ist eine Funktion ⟪f(t)⟫, die

  • die stetig und stetig differenzierbar ist (weder ⟪f(t)⟫ noch ⟪f'(t)⟫ "springen"),
  • die Punkte ⟪P_1(t_1, s_1)⟫ und ⟪P_3(t_3, s_3)⟫ berührt, und
  • im Punkt ⟪P_1(t_1, s_1)⟫ die Steigung ⟪v_1⟫ hat (⟪f'(t_1)=v_1⟫).
t1 t2 t3 s1 s2 s3 P1 P2 P3
⟪f(t)=at²+bt+c⟫

Die Aufgabe ist durch die Randbedingungen nicht hinreichend bestimmt.

Als zusätzliche Randbedingung setzen wir die Steigung ⟪v_3⟫ am Punkt ⟪P_3⟫ fest. Dazu legen wir eine Parabel durch die Punkte ⟪P_1⟫, ⟪P_2⟫ und ⟪P_3⟫ und erhalten eindeutig eine quadratische Funktion ⟪q(t) = at²+bt+c⟫ mit der Ableitung ⟪q'(t) = 2at+b⟫.

Daraus ergibt sich ⟪v_3⟫:

⟪v_3 := q'(t_3) = 2at_3 + b⟫

Unsere vorgegebe Steigung ⟪v_1⟫ im Punkt ⟪P_1⟫ stimmt im allgemeinen nicht mit der Steigung der Parabel überein:

⟪v_1!=q'(t_1)⟫.

Deshalb ist ⟪q(t)⟫ noch nicht unsere gesuchte Funktion.

Wir definieren die Funktion ⟪f(t)⟫ als Folge von zwei kubischen Funktionen:

⟪ Delta t := (t_3 - t_1) / 2 rArr t_3 = t_1 + 2 Delta t ⟫

⟪ f(t_1) = s_1 ⟫

⟪ f'(t_1) = v_1 ⟫

⟪ f''(t) := { (a_1, if t lt t_1 + Delta t ","), (a_2 , if t ge t_1+Delta t ".") :} ⟫

Die Werte für ⟪a_1⟫ und ⟪a_2⟫ ergeben sich aus den Randbedingungen.

Aus der Randbedingung ⟪ f'(t_1 + 2 Delta t) = f'(t_3) = v_3 ⟫ folgt:

⟪ f'(t_1+Delta t) = f'(t_1) + a_1 Delta t = v_1 + a_1 Delta t ⟫

⟪ f'(t_1+2Delta t) = f'(t_1+Delta t) + a_2 Delta t = v_1 + a_1 Delta t + a_2 Delta t = v_1 + (a_1+a_2) Delta t ⟫

⟪ v_3 = v_1 + (a_1+a_2) Delta t ⟫

⟪ (v_3 - v_1) / (Delta t) = a_1+a_2 ⟫

⟪(1)⟫ ⟪ a_1+a_2 = p | p := (v_3 - v_1) / (Delta t) ⟫

Aus der Randbedingung ⟪ f(t_1 + 2 Delta t) = f(t_3) = s_3 ⟫ folgt:

⟪ f(t_1+Delta t) = s_1 + v_1 Delta t + a_1/2 Delta t² ⟫

⟪ {: ( f(t_1+2Delta t) , = , s_1 + v_1 Delta t + a_1/2 Delta t² + f'(t_1 + Delta t ) Delta t + a_2/2 Delta t² ), ( , = , s_1 + v_1 Delta t + a_1/2 Delta t² + (v_1 + a_1 Delta t) Delta t + a_2/2 Delta t² ), ( , = , s_1 + v_1 Delta t + a_1/2 Delta t² + v_1 Delta t + a_1 Delta t² + a_2/2 Delta t² ) :} ⟫

⟪ f(t_1+2Delta t) = s_3 = s_1 + 2 v_1 Delta t + 1/2 ( 3a_1 + a_2 ) Delta t² ⟫

⟪ (2 (s_3 - s_1 - 2 v_1 Delta t)) / (Delta t²) = 3a_1 + a_2 ⟫

⟪(2)⟫ ⟪ 3a_1 + a_2 = q | q := 2 (s_3 - s_1 - 2 v_1 Delta t) / (Delta t²) ⟫

Aus ⟪(1)⟫ und ⟪(2)⟫ ergibt sich:

⟪{: ( a_1 , + , a_2 , = , p ), ( 3a_1 , + , a_2 , = , q ), ( , , downarrow , , ), ( a_1 , , , = , ( q-p) / 2 ), ( , , a_2 , = , (3p-q) / 2 ∎) :}⟫

Der Algorithmus:

Hilfsparabel:

⟪ d := t_1²t_2 + t_2²t_3 + t_3²t_1 - t_1²t_3 - t_2²t_1 - t_3²t_2 ⟫

⟪a := (s_1t_2 + s_2t_3 + s_3t_1 - s_1t_3 - s_2t_1 - s_3t_2) / d⟫

⟪b := (t_1²s_2 + t_2²s_3 + t_3²s_1 - t_1²s_3 - t_2²s_1 - t_3²s_2) / d⟫

Endgeschwindigkeit aus Hilfsparabel:

⟪v_3 := 2at_3 + b⟫

Länge der beiden Intervalle:

⟪ Delta t := (t_3 - t_1) / 2 ⟫

Hilfswerte:

⟪ p := (v_3 - v_1) / (Delta t) ⟫

⟪ q := 2 (s_3 - s_1 - 2 v_1 Delta t) / (Delta t²) ⟫

Beschleunigung für erste und zweite Hälfte:

⟪ a_1 := (q-p) / 2 ⟫

⟪ a_2 := (3p-q) / 2 ⟫

Startwerte für die Berechnung der zweiten Hälfte:

⟪ t_m = t_1 + Delta t ⟫

⟪ v_m = v_1 + a_1 * Delta t ⟫

⟪ s_m = s_1 + v_1 * Delta t + a_1/2 * Delta t^2 ⟫

⟪ f(t) := { ( s_1 + v_1 t' + a_1/2 t'² , [ t' := t- t_1 ] , if t le t_m ","), ( s_m + v_m t' + a_2/2 t'², [ t' := t-(t_1 + Delta t)] , if t ge t_m ".") :} ⟫