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

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

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

Ορισμός

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

B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),

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

\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:

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₀ για την εκτίμηση ενός πολυωνύμου Μπέρνσταϊν χρησιμοποιούνται οι δύο διαγώνιες του τριγώνου για την κατασκευή τμήματος αυτού

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₀.

Ξεκινάμε την αναδρομική σχέση με

\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{aligned}\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{aligned}}

που είναι το αναμενόμενο πολυώνυμο Μπέρνσταϊν βαθμού 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$ .

Η ακόλουθη εικόνα δείχνει αυτήν τη διαδικασία για μία κυβική καμπύλη Μπεζιέ:

Σημειώστε ότι τα ενδιάμεσα σημεία που δημιουργήθηκαν είναι στην ουσία τα σημεία ελέγχου των δύο νέων καμπυλών Μπεζιέ, οι οποίες συμπίπτουν ακριβώς με την αρχική. Ο αλγόριθμος αυτός δεν υπολογίζει μόνο την καμπύλη στο $\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_{i}x_{i},w_{i}y_{i},w_{i}z_{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

Δείτε επίσης