De Casteljau

casijau

Hallo zusammen,

wir müssen den Algorithmus von de Casteljau programmieren und ich habe leider keine Ahnung wie das gehen soll. Habe schon in etlichen Foren und Internetauftritten mich über de Casteljau und den Algorithmus informiert, weiß aber leider nicht wie ich das umsetzten soll..
die genaue Aufgabe lautet so: Es soll die Kurve (Bezier-Kurve) an einem bestimmten Punkt mit dem Algorithmus von DECASTELJAU ausgewertet werden.

Kann mir irgendwer einen Tip geben, wie ich ansetzen muss?

MfG, casijau

Bashar

Welches konkrete Problem hast du?

casijau

Ich weiß, dass der Casteljau-Algorithmus folgendermaßen lautet:

P(k+1) = (1-t_0) *P(k) + t_0*P(k)*(I+1)

ich hätte jetzt zwei for-schleifen gemacht, eine temporäre variable geschaffen und diese dann irgendwie für diese (1-t_0) eingesetzt.. jedoch weiß ich wirklich nicht weiter! Oder bin ich komplett auf dem Holzweg?
Das mag vielleicht etwas dumm klingen, aber und wurde nie wirklich in die c++-sprache gelernt, weshalb ich oft große schwierigkeiten habe!

Vielen Dank im Voraus!

zuckerlie

Zeig doch mal, was du bisher gemacht hast. Falls Du noch nichts gemacht hast, schreib uns doch mal bitte einen Pseudocode über deine Vorstellung, wie du es umsetzen würdest.

pumuckl

casijau schrieb:

Das mag vielleicht etwas dumm klingen, aber und wurde nie wirklich in die c++-sprache gelernt, weshalb ich oft große schwierigkeiten habe!

Dann bist du entweder im falschen Kurs oder kriegst unmögliche Hausaufgaben oder hast dich bisher erfolgreich vor dem Lernen gedrückt. So oder so wirst du wohl nicht drumrum kommen, jetzt mit dem Lernen anzufangen. Schnapp dir ein gutes Buch und auf gehts! (Bücherliste in der FAQ). Komplettlösungen und Hausaufgaben wirst du hier kaum finden.

Werner Salomon

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