Αλγόριθμος του de Casteljau

Αλγόριθμος του De Casteljau

Ταξινόμηση
Dewey	518
MSC2010	65Dxx

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

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

Ορισμός

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

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

όπου b ένα πολυώνυμο βάσης Bernstein, το πολυώνυμο στο σημείο 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)}$

Παράδειγμα

Ανάπτυξη παραδείγματος του αλγόριθμου του De Casteljau σε 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₀ για την εκτίμηση ενός πολυωνύμου Bernstein χρησιμοποιούνται οι δύο διαγώνιες του τριγώνου για την κατασκευή τμήματος αυτού

$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]$

Παράδειγμα

Έστω ότι θέλουμε να υπολογίσουμε το πολυώνυμο Bernstein polynomial βαθμού 2 με συντελεστές Bernstein

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

που είναι το αναμενόμενο πολυώνυμο Bernstein βαθμού n.

Καμπύλη Bézier

Όταν εκτιμάται μία καμπύλη Bézier (Μπεζιέ) βαθμού 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]$

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

Γεωμετρική Ερμηνεία

Η γεωμετρική ερμηνεία του αλγόριθμου του De Casteljau είναι απλή.

• Θεωρούμε μία καμύλη Μπεζιέ με σημεία ελέγχου $\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_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

Δείτε επίσης

• Καμπύλη Bézier
• Αλγόριθμος De Boor
• Σχήμα Horner
• Αλγόριθμος Clenshaw