Αλγόριθμος του ντε Καστελζώ

Στο μαθηματικό πεδίο της αριθμητικής ανάλυσης, ο αλγόριθμος του **ντε Καστελζώ** (de Casteljau) αποτελεί μία αναδρομική μέθοδο εκτίμησης πολυωνύμων Μπέρνσταϊν ή καμπυλών Μπεζιέ. Ο **αλγόριθμος του ντε Καστελζώ** μπορεί επίσης να χρησιμοποιηθεί για το "σπάσιμο" μίας καμπύλης Μπεζιέ σε δύο για μία αυθαίρετη παραμετρική τιμή.Το όνομά του το πήρε από τον εφευρέτη του Πωλ ντε Καστελζώ.

Παρόλο που θεωρείται αργός ως αλγόριθμος, εμφανίζει ιδιαίτερη αριθμητική ευστάθεια.

## Ορισμός
Έστω ένα πολυώνυμο *B* σε μορφή Μπέρνσταϊν βαθμού *n*

:B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t),

όπου *b* ένα πολυώνυμο βάσης Μπέρνσταϊν, το πολυώνυμο στο σημείο *t*0 μπορεί να εκτκιμηθεί με την αναδρομική σχέση

:\beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n
:\beta_i^{(j)} := \beta_i^{(j-1)} (1-t_0) + \beta_{i+1}^{(j-1)} t_0 \mbox{ , } i = 0,\ldots,n-j \mbox{ , } j= 1,\ldots,n

Τότε, η εκτίμηση του B σε σημείο t_0 μπορεί να εκτιμηθεί σε n βήματα του αλγορίθμου. Το αποτέλεσμα B(t_0) δίνεται από :

:B(t_0)=\beta_0^{(n)}.

Επιπλέον, η καμπύλη Μπεζιέ B μπορεί να διασπαστεί σε σημείο t_0 σε δύο καμπύλες με αντίστοιχα σημεία ελέγχου :
:\beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)}
:\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}

## Παράδειγμα

Ανάπτυξη παραδείγματος του αλγόριθμου του ντε Καστελζώ σε Haskell:

```haskell
deCasteljau :: Double -> [(Double, Double)] -> (Double, Double)
deCasteljau t [b] = b
deCasteljau t coefs = deCasteljau t reduced
  where
    reduced = zipWith (lerpP t) coefs (tail coefs)
    lerpP t (x0, y0) (x1, y1) = (lerp t x0 x1, lerp t y0 y1)
    lerp t a b = t * b + (1 - t) * a
```


## Σημειώσεις
Όταν γίνεται ο υπολογισμός με το χέρι είναι χρήσιμο να καταγράφονται οι συντελεστές σχηματίζοντας ένα τρίγωνο όπως αυτό που ακολουθεί:

:
\begin{matrix}
\beta_0     & = \beta_0^{(0)}     &                   &         &               \\
            &                     & \beta_0^{(1)}     &         &               \\
\beta_1     & = \beta_1^{(0)}     &                   &         &               \\
            &                     &                   & \ddots  &               \\
\vdots      &                     & \vdots            &         & \beta_0^{(n)} \\
            &                     &                   &         &               \\
\beta_{n-1} & = \beta_{n-1}^{(0)} &                   &         &               \\
            &                     & \beta_{n-1}^{(1)} &         &               \\
\beta_n     & = \beta_n^{(0)}     &                   &         &               \\
\end{matrix}


Όταν επιλέγεται ένα σημείο *t*0 για την εκτίμηση ενός πολυωνύμου Μπέρνσταϊν χρησιμοποιούνται οι δύο διαγώνιες του τριγώνου για την κατασκευή τμήματος αυτού

:B(t) = \sum_{i=0}^n \beta_i^{(0)} b_{i,n}(t) \mbox{ , } \qquad t \in [0,1]

σε

:B_1(t) = \sum_{i=0}^n \beta_0^{(i)} b_{i,n}\left(\frac{t}{t_0}\right) \mbox{ , } \qquad t \in [0,t_0]

και

:B_2(t) = \sum_{i=0}^n \beta_{n-i}^{(i)} b_{i,n}\left(\frac{t-t_0}{1-t_0}\right) \mbox{ , } \qquad t \in [t_0,1]

## Παράδειγμα
Έστω ότι θέλουμε να υπολογίσουμε το πολυώνυμο Μπέρνσταϊν δευτέρου βαθμού με συντελεστές Μπέρνσταϊν
:\beta_0^{(0)} = \beta_0
:\beta_1^{(0)} = \beta_1
:\beta_2^{(0)} = \beta_2
στο σημείο *t*0.

Ξεκινάμε την αναδρομική σχέση με
:\beta_0^{(1)} = \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 = \beta_0(1-t_0) + \beta_1 t_0
:\beta_1^{(1)} = \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 = \beta_1(1-t_0) + \beta_2 t_0

και με τη δεύτερη επανάληψη η αναδρομή σταματάει με
: 
\begin{align}
\beta_0^{(2)} & = \beta_0^{(1)} (1-t_0) + \beta_1^{(1)} t_0      \\
\             & = \beta_0(1-t_0) (1-t_0) + \beta_1 t_0 (1-t_0) + \beta_1(1-t_0)t_0 + \beta_2 t_0 t_0 \\
\             & = \beta_0 (1-t_0)^2 + \beta_1 2t_0(1-t_0) + \beta_2 t_0^2
\end{align}


που είναι το αναμενόμενο πολυώνυμο Μπέρνσταϊν βαθμού&nbsp;*n*.

## Καμπύλη Μπεζιέ
Όταν εκτιμάται μία καμπύλη Μπεζιέ βαθμού *n* στο τριδιάστατο χώρο, με *n*+1 σημεία ελέγχου **P***i*

:\mathbf{B}(t) = \sum_{i=0}^{n} \mathbf{P}_i b_{i,n}(t) \mbox{ , } t \in [0,1]

με

:\mathbf{P}_i := 
\begin{pmatrix} 
x_i \\ 
y_i \\
z_i 
\end{pmatrix}
.

Χωρίζουμε την καμπύλη Μπεζιέ σε τρεις ισότητες:

:B_1(t) = \sum_{i=0}^{n} x_i b_{i,n}(t) \mbox{ , } t \in [0,1]
:B_2(t) = \sum_{i=0}^{n} y_i b_{i,n}(t) \mbox{ , } t \in [0,1]
:B_3(t) = \sum_{i=0}^{n} z_i b_{i,n}(t) \mbox{ , } t \in [0,1]

τις οποίες εκτιμάμε ξεχωριστά, χρησιμοποιώντας τον αλγόριθμο του ντε Καστελζώ.

## Γεωμετρική Ερμηνεία
Η γεωμετρική ερμηνεία του αλγόριθμου του ντε Καστελζώ είναι απλή.
* Θεωρούμε μία καμπύλη Μπεζιέ με σημεία ελέγχου \scriptstyle P_0,...,P_n. Ενώνοντας τα συνεχόμενα σημεία δημιουργείται το πολύγωνο ελέγχου της καμπύλης.
* Στη συνέχεια, υποδιαιρούμε κάθε ευθύγραμμο τμήμα του πολυγώνου αυτού με ρυθμό \scriptstyle t : (1-t) και συνδέουμε τα σημεία που παίρνουμε. Με το τρόπο αυτό φτάνουμε σε ένα νέο πολύγωνο το οποίο έχει ένα τμήμα λιγότερο.
* Η διαδικασία επαναλαμβάνεται μέχρι να φτάσουμε στο ενιαίο σημείο - αυτό είναι το σημείο της καμπύλης που αντιστοιχεί στην παράμετρο \scriptstyle t.
Η ακόλουθη εικόνα δείχνει αυτήν τη διαδικασία για μία κυβική καμπύλη Μπεζιέ:

Αρχείο:DeCasteljau1.svg

Σημειώστε ότι τα ενδιάμεσα σημεία που δημιουργήθηκαν είναι στην ουσία τα σημεία ελέγχου των δύο νέων καμπυλών Μπεζιέ, οι οποίες συμπίπτουν ακριβώς με την αρχική. Ο αλγόριθμος αυτός δεν υπολογίζει μόνο την καμπύλη στο \scriptstyle t, αλλά επίσης σπάει την καμπύλη σε δύο κομμάτια στο \scriptstyle t, και παρέχει τις εξισώσεις των δύο υποκαμπυλών σε μορφή Μπεζιέ.

Η παραπάνω ερμηνεία ισχύει και για μη λογικές καμπύλες Μπεζιέ. Για να εκτιμήσουμε μία λογική καμπύλη Μπεζιέ σε \scriptstyle \mathbf{R}^n, μπορούμε να προβάλλουμε το σημείο στο \scriptstyle \mathbf{R}^{n+1}. Για παράδειγμα, μία καμπύλη σε τρεις διαστάσεις μπορεί να έχει τα σημεία ελέγχου της \scriptstyle \{(x_i, y_i, z_i)\} και βάρη \scriptstyle \{w_i\} προβαλλόμενα στα σταθμισμένα σημεία ελέγχου \scriptstyle \{(w_ix_i, w_iy_i, w_iz_i, w_i)\}. Τότε ο αλγόριθμος συνεχίζει με το συνήθει τρόπο, παρεμβάλλοντας στα \scriptstyle \mathbf{R}^4. Τα τετραδιάστατα σημεία που προκύπτουν μπορούν να προβληθούν πίσω στον τρισδιάστατο χώρο με ένα προβολικό μετασχηματισμό.

Γενικά, εφαρμογές σε μία λογική καμπύλη (ή επιφάνεια) ισοδυναμεί με εφαρμογές σε μία μή λογική καμπύλη σε ένα προβολικό χώρο. Η αναπαράσταση ως "σταθμισμένα σημεία ελέγχου" και βάρη συχνά βολεύει στις περιπτώσεις που έχουμε να εκτιμήσουμε λογικές καμπύλες.

## Αναφορές
* Farin, Gerald & Hansford, Dianne (2000). *The Essentials of CAGD*. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3

## Δείτε επίσης
* Καμπύλη Μπεζιέ
* Αλγόριθμος ντε Μπουρ
* Σχήμα Χόρνερ
* Αλγόριθμος Κλένσο

Κατηγορία:Καμπύλες
Κατηγορία:Αριθμητική ανάλυση