מתוך ויקיפדיה, האנציקלופדיה החופשית
באנליזה נומרית , אלגוריתם דה-קַסְטַלְז'וּ מתאר שיטה רקורסיבית כדי להעריך פולינום ברנשטיין או עקומות בזייר , הקרויה על שם ממציאהּ, פול-דה-קסטלז'ו. אלגוריתם דה-קסטלז'ו יכול לשמש גם כדי לפצל עקומת בזייר יחידה לשתי עקומות בזייר בעזרת פרמטר בעל ערך שרירותי.
למרות שהוא איטי יותר במרבית הארכיטקטורות בהשוואה לגישה הישירה, הוא יציב יותר מבחינה נומרית .
עקומת בזייר B (בדרגה n , עם נקודות הבקרה
β
0
,
…
,
β
n
{\displaystyle \beta _{0},\ldots ,\beta _{n}}
B
(
t
)
=
∑
i
=
0
n
β
i
b
i
,
n
(
t
)
{\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t)}
כאשר b הוא פולינום בסיס מתצורת ברנשטיין
b
i
,
n
(
t
)
=
(
n
i
)
(
1
−
t
)
n
−
i
t
i
{\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}}
העקומה בנקודה t 0 ניתנת להערכה בעזרת נוסחת נסיגה
β
i
(
0
)
:=
β
i
,
i
=
0
,
…
,
n
{\displaystyle \beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n}
β
i
(
j
)
:=
β
i
(
j
−
1
)
(
1
−
t
0
)
+
β
i
+
1
(
j
−
1
)
t
0
,
i
=
0
,
…
,
n
−
j
,
j
=
1
,
…
,
n
{\displaystyle \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
{\displaystyle B}
t
0
{\displaystyle t_{0}}
n
{\displaystyle n}
B
(
t
0
)
{\displaystyle B(t_{0})}
B
(
t
0
)
=
β
0
(
n
)
.
{\displaystyle B(t_{0})=\beta _{0}^{(n)}.}
יתר על כן, עקומת בזייר
B
{\displaystyle B}
t
0
{\displaystyle t_{0}}
β
0
(
0
)
,
β
0
(
1
)
,
…
,
β
0
(
n
)
{\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}
β
0
(
n
)
,
β
1
(
n
−
1
)
,
…
,
β
n
(
0
)
{\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}
כאשר עושים את החישוב באופן ידני, שימושי לכתוב את המקדמים במשולש כ:
β
0
=
β
0
(
0
)
β
0
(
1
)
β
1
=
β
1
(
0
)
⋱
⋮
⋮
β
0
(
n
)
β
n
−
1
=
β
n
−
1
(
0
)
β
n
−
1
(
1
)
β
n
=
β
n
(
0
)
{\displaystyle {\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
)
=
∑
i
=
0
n
β
i
(
0
)
b
i
,
n
(
t
)
,
t
∈
[
0
,
1
]
{\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]}
ל:
B
1
(
t
)
=
∑
i
=
0
n
β
0
(
i
)
b
i
,
n
(
t
t
0
)
,
t
∈
[
0
,
t
0
]
{\displaystyle 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
)
=
∑
i
=
0
n
β
i
(
n
−
i
)
b
i
,
n
(
t
−
t
0
1
−
t
0
)
,
t
∈
[
t
0
,
1
]
{\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right){\mbox{ , }}\qquad t\in [t_{0},1]}
אנחנו רוצים להעריך את פולינום ברנשטיין מדרגה 2 עם מקדמי ברנשטיין
β
0
(
0
)
=
β
0
{\displaystyle \beta _{0}^{(0)}=\beta _{0}}
β
1
(
0
)
=
β
1
{\displaystyle \beta _{1}^{(0)}=\beta _{1}}
β
2
(
0
)
=
β
2
{\displaystyle \beta _{2}^{(0)}=\beta _{2}}
בנקודה t 0
אנחנו מתחילים את הרקורסיה עם
β
0
(
1
)
=
β
0
(
0
)
(
1
−
t
0
)
+
β
1
(
0
)
t
0
=
β
0
(
1
−
t
0
)
+
β
1
t
0
{\displaystyle \beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}t_{0}}
β
1
(
1
)
=
β
1
(
0
)
(
1
−
t
0
)
+
β
2
(
0
)
t
0
=
β
1
(
1
−
t
0
)
+
β
2
t
0
{\displaystyle \beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}=\beta _{1}(1-t_{0})+\beta _{2}t_{0}}
עם איטרציה שנייה הרקורסיה מפסיקה עם
β
0
(
2
)
=
β
0
(
1
)
(
1
−
t
0
)
+
β
1
(
1
)
t
0
=
β
0
(
1
−
t
0
)
(
1
−
t
0
)
+
β
1
t
0
(
1
−
t
0
)
+
β
1
(
1
−
t
0
)
t
0
+
β
2
t
0
t
0
=
β
0
(
1
−
t
0
)
2
+
β
1
2
t
0
(
1
−
t
0
)
+
β
2
t
0
2
{\displaystyle {\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}}}
אשר הוא הפולינום ברנשטיין הצפוי מדרגה 2 .
בעת הערכת עקומת בזייר מדרגה n במרחב 3-ממדי עם n +1 נקודות בקרה, P i
B
(
t
)
=
∑
i
=
0
n
P
i
b
i
,
n
(
t
)
,
t
∈
[
0
,
1
]
{\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}
עם
P
i
:=
(
x
i
y
i
z
i
)
{\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}}}
אנחנו מחלקים את עקומת בזייר לשלוש משוואות נפרדות.
B
1
(
t
)
=
∑
i
=
0
n
x
i
b
i
,
n
(
t
)
,
t
∈
[
0
,
1
]
{\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}
B
2
(
t
)
=
∑
i
=
0
n
y
i
b
i
,
n
(
t
)
,
t
∈
[
0
,
1
]
{\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}
B
3
(
t
)
=
∑
i
=
0
n
z
i
b
i
,
n
(
t
)
,
t
∈
[
0
,
1
]
{\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}
אשר אנו מעריכים בנפרד באמצעות האלגוריתם של דה-קסטלז'ו.
האינטרפולציה הגאומטרית של דה-קסטלז'ו הוא ברור וישיר.
נניח עקומת בזייר עם נקודות בקרה
P
0
,
.
.
.
,
P
n
{\displaystyle \scriptstyle P_{0},...,P_{n}}
מחלקים עכשיו כל מקטע של הפוליגון עם יחס
t
:
(
1
−
t
)
{\displaystyle \scriptstyle t:(1-t)}
חוזרים על התהליך עד שמגיעים לנקודה אחת - זו הנקודה של העקומה המתאימה לפרמטר
t
{\displaystyle \scriptstyle t}
התמונה הבאה מראה את התהליך הזה עבור עקומת בזייר מעוקבת:
יש לשים לב כי נקודות הביניים שנבנו הן למעשה נקודות בקרה עבור שתי עקומות בזייר החדשות שנוצרו, שתיהן בדיוק מתואמות עם הקודמת. אלגוריתם זה לא רק מעריך את העקומה ב-
t
{\displaystyle \scriptstyle t}
t
{\displaystyle \scriptstyle t}
הפרשנות שניתנה לעיל תקפה לעקומת בזייר אי-אציונאליות. כדי להעריך עקומת בזייר רציונלית ב
R
n
{\displaystyle \scriptstyle \mathbf {R} ^{n}}
R
n
+
1
{\displaystyle \scriptstyle \mathbf {R} ^{n+1}}
{
(
x
i
,
y
i
,
z
i
)
}
{\displaystyle \scriptstyle \{(x_{i},y_{i},z_{i})\}}
{
w
i
}
{\displaystyle \scriptstyle \{w_{i}\}}
{
(
w
i
x
i
,
w
i
y
i
,
w
i
z
i
,
w
i
)
}
{\displaystyle \scriptstyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}}
אינטרפולציה ב
R
4
{\displaystyle \scriptstyle \mathbf {R} ^{4}}
מטריצת מעבר כלשהי.
באופן כללי, פעולות על עקומה רציונלית (או משטח) שוות ערך ל פעולות על עקומה לא-רציונלית במרחב פרויקטיבי . ייצוג זה כ"נקודות בקרה משוקללות" ומשקולות הוא לעיתים קרובות נוח בעת הערכת עקומות רציונליות.
![{\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb84d69bb346f499c657d7e0737dda3ee72535fa)
![{\displaystyle 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}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddb872182151fb849a91f142f00b0a7ecb6c0eed)
![{\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right){\mbox{ , }}\qquad t\in [t_{0},1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38ea4239f7425782fc773820c1c01f6450856354)
![{\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7841aeeff9c1b50c687890c1a35194fc036309a8)
![{\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fc49c852d0ddc38093382f5562bfd61cbfeb0fb)
![{\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b169ad3d55321750016c7bf014e46319f229c1f8)
![{\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/464a9fad7d1512dd399ade0d86684e1ba47e9fb2)
