الگوریتم De Casteljau's

در زمینه ریاضی آنالیز عددی ، الگوریتم De Casteljau یک روش بازگشتی برای ارزیابی چند جمله ای ها در فرم برنشتاین یا منحنی های بزیه است که به نام مخترع آن Paul de Casteljau نامگذاری شده است. الگوریتم De Casteljau را همچنین می توان برای تقسیم منحنی بزیه به دو منحنی بزیه در مقدار پارامتر دلخواه استفاده کرد.

اگرچه این الگوریتم در مقایسه با رویکرد مستقیم برای بیشتر معماری ها کندتر است ، اما از نظر عددی پایدارتر است .

تعریف

منحنی بزیه B (درجه n ، با نقاط کنترل) $\beta _{0},\ldots ,\beta _{n}$ ) را می توان به صورت زیر به صورت برنشتاین نوشت:

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

جایی که b یک چند جمله ای مبتنی برنشتاین است

$b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}$ .

منحنی در نقطه 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}$ را می توان با ${\binom {n}{2}}$ارزیابی کرد. نتیجه $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 در زبان هاسکل آورده شده است :

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 _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right){\mbox{, }}\qquad t\in [t_{0},1]$

مثال

ما می خواهیم چند جمله ای برنشتاین درجه 2 را با ضرایب برنشتاین ارزیابی کنیم

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

که انتظار می رود چند جمله ای درجه 2 برنشتاین باشد

منحنی بزیر

منحنی Bézier

هنگام ارزیابی منحنی بزیر از درجه n در فضای 3 بعدی با $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_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$ . سپس الگوریتم مطابق معمول پیش می رود و در آن مداخله می کند $\scriptstyle \mathbf {R} ^{4}$ . نقاط چهار بعدی حاصل ممکن است با یک شکاف چشم انداز به سه فضا برگردانده شود.

به طور کلی ، عملیات روی یک منحنی منطقی (یا سطح) معادل عملیات روی یک منحنی غیر منطقی در یک فضای فرافکنی است . این بازنمایی به عنوان "نقاط کنترل وزنی" و وزن اغلب هنگام ارزیابی منحنی های منطقی راحت است.

See also

• Bézier curves
• De Boor's algorithm
• Horner scheme to evaluate polynomials in monomial form
• Clenshaw algorithm to evaluate polynomials in Chebyshev form

References

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. شابک ‎۱−۵۶۸۸۱−۱۲۳−۳

لینک های خارجی

• تقریب خطی منحنی های Bézier - شرح الگوریتم De Casteljau ، از جمله یک معیار برای تعیین زمان متوقف کردن جمع کردن 
• منحنی های Bezier و Picasso - شرح و تصویر الگوریتم De Casteljau اعمال شده در منحنی های Bézier مکعب.

This article "الگوریتم De Casteljau's" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:الگوریتم De Casteljau's. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• C.mmp
• محسن میرزایی (بازیگر)
• سامی تلمکانی
• آزاده عباس زاده فلاح
• زین‌العابدین فرهادی
• دروازه ناتمام
• یاسمن معاوی

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• الگوریتم De Casteljau's in English