W
Hallo casijau,
Der 'De Casteljau'-Algorithmus dient dazu, eine Bezierkurve in zwei Kurven mit gleicher Anzahl Stützpunkte zu teilen. Das erste Teilstück sind die Punkte P(k)_0 mit k[0..n]. Und das zweite Teilstück sind alle P(k)_i mit k[n..0] und i=n-k. Siehe das passende Bild dazu.
Ich unterstelle mal, das ist das, was Du erreichen willst.
casijau schrieb:
Ich weiß, dass der Casteljau-Algorithmus folgendermaßen lautet:
P(k+1) = (1-t_0) *P(k) + t_0*P(k)*(I+1)
.. nicht ganz. Wenn Du 'De Casteljau' in Google eingibst, so geht es auch gleich zur korrekten Formel
P(k+1)_i = (1 - t0) * P(k)_i + t0 * P(k)(i+1)
bzw. wenn man k durch k-1 ersetzt
P(k)_i = (1 - t0) * P(k-1)_i + t0 * P(k-1)(i+1)
und jedes P(0)_i entspricht dem i'ten Bezierpunkt.
Und genauso lässt sich das auch codieren. Die Funktion DeCasteljau soll einen Punkt P(k)_i berechnen, also
class Punkt; // Punkt sei eine eigene Klasse
Punkt DeCasteljau( int k, int i, double t0, Punkt* P ) // P[] sind die Stützpunkte
{
if( k == 0 ) // P(0)_i sind immer die Stützpunkte selbst
return P[i];
return (1 - t0) * DeCasteljau( k-1, i, t0, P ) + t0 * DeCasteljau( k-1, i+1, t0, P );
}
Diese Funktion ruft sich solange selbst auf, bis k zu 0 wird.
Das wäre auch schon alles. Es müssen lediglich die richtigen 'k' und 'i' eingesetzt werden, wie oben bereits beschrieben, um zu den Stützpunkten der beiden Teilstücke zu kommen.
Der Code ist zwar ungünstig vom Laufzeitverhalten, da viele Punkte mehrfach berechnet werden, aber wie man sieht ist er sehr einfach.
Du brauchst nur noch einen Klasse 'Punkt', damit Punkt mit Punkt addiert und double mit Punkt multipliziert werden kann. Frage nach, wenn Du nicht weist, wie das geht.
Für die Profies: die flexible Variante von DeCasteljau sähe natürlich so aus:
template< typename I >
typename std::iterator_traits< I >::value_type DeCasteljau( int k, int idx, double t0, I P )
{ // wie oben.
aber casijau wird daran eh schon genug zu knabbern haben.
Gruß
Werner
