نمایش مبدأ برای پیش‌نویس:De Casteljau's algorithm

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

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

== تعریف ==
منحنی Bézier ''B'' (درجه ''n'' ، با نقاط کنترل) <math>\beta_0, \ldots, \beta_n</math> ) را می توان به صورت زیر به صورت برنشتاین نوشت:

: <math>B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t) </math> ،

جایی که ''b'' یک [[چندجمله‌ای‌های برنشتاین|چند جمله ای مبتنی برنشتاین است]]

: <math> b_{i,n}(t) = {n \choose i}(1-t)^{n-i}t^i</math> .

منحنی در نقطه ''t'' <sub>0 را</sub> می توان با [[رابطه بازگشتی]] ارزیابی کرد

: <math>\beta_i^{(0)} := \beta_i \mbox{, } i=0,\ldots,n</math>
: <math>\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</math>

سپس ، ارزیابی از <math>B</math> در نقطه <math>t_0</math> را می توان در ارزیابی کرد <math>\binom{n}{2}</math> عملیات نتیجه <math>B(t_0)</math> از رابطه زیر بدست می آید:

: <math>B(t_0)=\beta_0^{(n)}.</math>

علاوه بر این ، منحنی بزیر <math>B</math> می تواند در نقطه <math>t_0</math> به دو منحنی ،با نقاط کنترل مربوطه تقسیم شود:

: <math>\beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)}</math>
: <math>\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}</math>

== اجرای نمونه ==
در اینجا مثالی از پیاده سازی الگوریتم De Casteljau در [[هسکل (زبان برنامه‌نویسی)|هاسکل آورده شده است]] :<syntaxhighlight lang="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
</syntaxhighlight>

== یادداشت ==
هنگام انجام محاسبه با دست ، مفید است که ضرایب را در یک طرح مثلث به صورت زیر بنویسید:

: <math>
\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}
</math>

هنگام انتخاب نقطه ''t'' <sub>0</sub> برای ارزیابی چند جمله ای برنشتاین می توان از دو مورب طرح مثلث برای ساخت تقسیم چند جمله ای استفاده کرد

: <math>B(t) = \sum_{i=0}^n \beta_i^{(0)} b_{i,n}(t) \mbox{, } \qquad t \in [0,1]</math>

به

: <math>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]</math>

و

: <math>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]</math>

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

: <math>\beta_0^{(0)} = \beta_0</math>
: <math>\beta_1^{(0)} = \beta_1</math>
: <math>\beta_2^{(0)} = \beta_2</math>

در نقطه ''t'' <sub>0</sub> .

بازگشت را با عبارات زیر شروع می کنیم

: <math>\beta_0^{(1)} = \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 = \beta_0(1-t_0) + \beta_1 t_0</math>
: <math>\beta_1^{(1)} = \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 = \beta_1(1-t_0) + \beta_2 t_0</math>

و با تکرار دوم بازگشت متوقف می شود با:

: <math> 
\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}
</math>

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

== منحنی بزیر ==
[[پرونده:Bézier_2_big.gif|چپ|بندانگشتی| منحنی Bézier]]
هنگام ارزیابی منحنی بزیر از درجه ''n'' در فضای 3 بعدی با <math>n+1</math> نقاط کنترل '''P''' <sub>''i''</sub>

: <math>\mathbf{B}(t) = \sum_{i=0}^{n} \mathbf{P}_i b_{i,n}(t) \mbox{, } t \in [0,1]</math>

با

: <math>\mathbf{P}_i := 
\begin{pmatrix} 
x_i \\ 
y_i \\
z_i 
\end{pmatrix}
</math> .

منحنی بزیر را به سه معادله جداگانه تقسیم می کنیم

: <math>B_1(t) = \sum_{i=0}^{n} x_i b_{i,n}(t) \mbox{, } t \in [0,1]</math>
: <math>B_2(t) = \sum_{i=0}^{n} y_i b_{i,n}(t) \mbox{, } t \in [0,1]</math>
: <math>B_3(t) = \sum_{i=0}^{n} z_i b_{i,n}(t) \mbox{, } t \in [0,1]</math>

که ما به صورت جداگانه با استفاده از الگوریتم De Casteljau ارزیابی می کنیم.

== تفسیر هندسی ==
تفسیر هندسی الگوریتم De Casteljau ساده است.

* یک منحنی بزیر با نقاط کنترل را در نظر بگیرید <math>\scriptstyle P_0,...,P_n</math> . با اتصال نقاط متوالی چند ضلعی کنترل منحنی ایجاد می کنیم.
* اکنون هر بخش خط از این چند ضلعی را با نسبت تقسیم کنید <math>\scriptstyle t : (1-t)</math> و امتیازاتی که بدست آوردید را بهم متصل کنید. با این روش به چند ضلعی جدید می رسید که دارای یک بخش کمتر است.
* این فرآیند را تا رسیدن به نقطه واحد تکرار کنید - این نقطه منحنی مربوط به پارامتر است <math>\scriptstyle t</math> .

تصویر زیر این روند را برای یک منحنی مکعب بزیر نشان می دهد:

[[File:DeCasteljau1.svg]]

توجه داشته باشید که نقاط میانی که ساخته شده اند در واقع نقاط کنترل دو منحنی جدید بزیر هستند ، هر دو دقیقاً با یک منحنی قدیمی مطابقت دارند. این الگوریتم نه تنها منحنی را در ارزیابی می کند <math>\scriptstyle t</math> ، اما منحنی را به دو قسمت تقسیم می کند <math>\scriptstyle t</math> ، و معادلات دو زیر منحنی را به صورت بزیر فراهم می کند.

تفسیری که در بالا ارائه شد برای یک منحنی غیر منطقی بزیر معتبر است. برای ارزیابی منحنی بیزیر منطقی در <math>\scriptstyle \mathbf{R}^n</math> ، ما ممکن است نقطه را به <math>\scriptstyle \mathbf{R}^{n+1}</math> ؛ به عنوان مثال ، یک منحنی در سه بعد ممکن است نقاط کنترل خود را داشته باشد <math>\scriptstyle \{(x_i, y_i, z_i)\}</math> و وزن <math>\scriptstyle \{w_i\}</math> پیش بینی شده به نقاط کنترل وزنی <math>\scriptstyle \{(w_ix_i, w_iy_i, w_iz_i, w_i)\}</math> . سپس الگوریتم مطابق معمول پیش می رود و در آن مداخله می کند <math>\scriptstyle \mathbf{R}^4</math> . نقاط چهار بعدی حاصل ممکن است با یک شکاف چشم انداز به سه فضا برگردانده شود.

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

== 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.  {{شابک|1-56881-123-3}}

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

* [http://hcklbrrfnn.wordpress.com/2012/08/20/piecewise-linear-approximation-of-bezier-curves/ تقریب خطی منحنی های Bézier] - شرح الگوریتم De Casteljau ، از جمله یک معیار برای تعیین زمان متوقف کردن جمع کردن <sup class="noprint Inline-Template" data-ve-ignore="true" style="white-space:nowrap;">&#x5B; ''<nowiki><span title="similar to recussion (November 2019)">بررسی املا</span></nowiki>'' &#x5D;</sup>
* [http://jeremykun.com/2013/05/11/bezier-curves-and-picasso/ منحنی های Bezier و Picasso] - شرح و تصویر الگوریتم De Casteljau اعمال شده در منحنی های Bézier مکعب.