Αλγόριθμος του 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, το πολυώνυμο στο σημείο t0 μπορεί να εκτκιμηθεί με την αναδρομική σχέση

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

Όταν επιλέγεται ένα σημείο t0 για την εκτίμηση ενός πολυωνύμου 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

στο σημείο t0.

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

\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 σημεία ελέγχου Pi

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

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

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

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]