خوارزم دوكاستلجو

لتكن كثيرة الحدود B في صورة بيرنستين من الدرجة n

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

حيث b هي متعددة الحدود لبيرنشتاين أساسية، تكون كثيرة الحدود عن نقطة t₀ قابلة للتقييم بفضل علاقة التكرار.

${\displaystyle \beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,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}$

حينئذ، يكون تقييم ${\displaystyle B}$ عند نقطة ${\displaystyle t_{0}}$ ممكناً في ${\displaystyle n}$ خطوة من الخوارزم. وتعطى النتيجة ${\displaystyle B(t_{0})}$ بالعلاقة:

${\displaystyle B(t_{0})=\beta _{0}^{(n)}.}$

بالإضافة لذلك، يمكن فصل منحنى بيزيه ${\displaystyle B}$عن نقطة ${\displaystyle t_{0}}$ إلى منحنيين بنقطتي تحكم متتاليتين:

${\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}$

${\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}$

المثال التالي يتضمن خوارزم كاستلجو بلغة هاسكل:

import Data.Array

deCasteljau::Array Int (Double,Double)->Double->(Double,Double)
deCasteljau controls t0=
 coefs!(0,n)
 where
   (c0,n)=bounds controls
   coefs=listArray ((0,0),(n,n)) $ map deCasteljau' [(i,j) | i<-[0..n], j<-[0..n]]

   deCasteljau' (i,0)
       | i>=c0 = controls!i 
       | otherwise = 0
   deCasteljau' (i,j) =
       let (x0,y0)=coefs!(i,j-1)
           (x1,y1)=coefs!(i+1, j-1)
       in ((1-t0)*x0 + t0*x1, (1-t0)*y0 + t0*y1)

عند تنفيذ الحسابات يدوياً سيكون من الأجدر تدوين المعاملات في مخطط مثلثي كما يلي

${\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₀ لتقييم كثيرة حدود بيرنستين، بإمكاننا استعمال قطري المخطط المثلثي لإنشاء قسمة كثيرة الحدود.

${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]}$

إلى

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

و

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

نرغب بتقييم كثيرة حدود بيرنستين من الدرجة 2 بمعاملات بيرنستين

${\displaystyle \beta _{0}^{(0)}=\beta _{0}}$

${\displaystyle \beta _{1}^{(0)}=\beta _{1}}$

${\displaystyle \beta _{2}^{(0)}=\beta _{2}}$

عند النقطة t₀.

نستهل المعاودة بـ

${\displaystyle \beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}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}}$

وبالتكرار الثاني يتوقف الاستدعاء الذاتي مع

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

وهي كثيرة الحدود المتوقعة من الدرجة  n.

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3

• منحنى بيزير
• مخطط هورنر
• خوارزم كلنشو

• بوابة خوارزميات
• بوابة رياضيات
• بوابة علم الحاسوب