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

في مجال التحليل العددي الرياضي ، تُعدّ خوارزمية دي كاستيلجو طريقةً تكراريةً لتقييم كثيرات الحدود في صيغة برنشتاين أو منحنيات بيزير ، وقد سُمّيت نسبةً إلى مخترعها بول دي كاستيلجو . كما يُمكن استخدام خوارزمية دي كاستيلجو لتقسيم منحنى بيزير واحد إلى منحنيين عند قيمة مُعامل اختيارية.

تتميز الخوارزمية بالاستقرار العددي ^{[ 1 ]} عند مقارنتها بالتقييم المباشر لكثيرات الحدود. ويبلغ التعقيد الحسابي لهذه الخوارزمية${\displaystyle O(dn^{2})}$حيث يمثل d عدد الأبعاد، و n عدد نقاط التحكم. توجد بدائل أسرع. ^{[ 2 ] [ 3 ]}

منحنى بيزير${\displaystyle B}$(درجة)${\displaystyle n}$، مع نقاط تحكم${\displaystyle \beta _{0},\ldots ,\beta _{n}}$يمكن كتابة ) بصيغة برنشتاين على النحو التالي $${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),}$$ أين${\displaystyle b}$هي متعددة حدود أساس برنشتاين$${\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{ni}t^{i}.}$$ المنحنى عند النقطة${\displaystyle t_{0}}$يمكن تقييمها باستخدام علاقة التكرار$$\begin{aligned}\beta_{i}^{(0)}&:=\beta_{i},&&i=0,\ldots,n\\\beta_{i}^{(j)}&:=\beta_{i}^{(j-1)}(1-t_{0})+\beta_{i+1}^{(j-1)}t_{0},&&i=0,\ldots,nj,\ \ j=1,\ldots,n\end{aligned}}}$$

ثم تقييم${\displaystyle B}$عند النقطة${\displaystyle t_{0}}$يمكن تقييمها في${\textstyle {\binom {n}{2}}}$العمليات. النتيجة${\displaystyle B(t_{0})}$يُعطى بواسطة $${\displaystyle B(t_{0})=\beta _{0}^{(n)}.}$$

علاوة على ذلك، منحنى بيزير${\displaystyle B}$يمكن تقسيمها عند نقطة${\displaystyle t_{0}}$إلى منحنيين مع نقاط تحكم خاصة بهما: $${\displaystyle {\begin{aligned}&\beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}\\[1ex]&\beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}\end{aligned}}}$$

منحنى بيزير من الدرجة الثانية

منحنى بيزير من الدرجة الثالثة

منحنى بيزير من الدرجة الرابعة

عند تقييم منحنى بيزير من الدرجة n في فضاء ثلاثي الأبعاد مع n + 1 نقطة تحكم P _i$${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]}$$ مع $${\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},}$$ نقسم منحنى بيزير إلى ثلاث معادلات منفصلة $${\displaystyle {\begin{aligned}B_{1}(t)&=\sum _{i=0}^{n}x_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{2}(t)&=\sum _{i=0}^{n}y_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{3}(t)&=\sum _{i=0}^{n}z_{i}b_{i,n}(t),&t\in [0,1]\end{aligned}}}$$ والتي نقوم بتقييمها بشكل فردي باستخدام خوارزمية دي كاستيلجو.

نريد حساب قيمة متعددة حدود برنشتاين من الدرجة الثانية بمعاملات برنشتاين $${\displaystyle {\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}}$$ عند النقطة t ₀ .

نبدأ التكرار بـ $${\displaystyle {\begin{aligned}\beta _{0}^{(1)}&&=&&\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}&&=&&\beta _{0}(1-t_{0})+\beta _{1}t_{0}\\[1ex]\beta _{1}^{(1)}&&=&&\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}&&=&&\beta _{1}(1-t_{0})+\beta _{2}t_{0}\end{aligned}}}$$ ومع التكرار الثاني، يتوقف التكرار مع $${\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}}}$$ وهو متعدد الحدود المتوقع لبرنشتاين من الدرجة الثانية . 

فيما يلي أمثلة على تطبيقات خوارزمية دي كاستيلجو في لغات برمجة مختلفة.

deCasteljau :: Double -> [( Double , Double )] -> ( Double , Double )deCasteljau t [ b ] = bمعاملات دي كاستيلجو t = دي كاستيلجو t المخفضةأينتم تقليلها = 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

def de_casteljau ( t : float , coefs : list [ float ]) -> float :"""خوارزمية دي كاستيلجاو."""beta = coefs.copy () # يتم استبدال القيم في هذه القائمةn = len ( beta )for j in range ( 1 , n ):لكل k في النطاق ( n - j ):بيتا [ ك ] = بيتا [ ك ] * ( 1 - ت ) + بيتا [ ك + 1 ] * تإرجاع بيتا [ 0 ]

دالة عامة مزدوجة deCasteljau ( مزدوجة t ، مزدوجة [] معاملات ) {double [] beta = المعاملات ؛int n = beta . length ;for ( int i = 1 ; i < n ; i ++ ) {for ( int j = 0 ; j < ( n - i ); j ++ ) {beta [ j ] = beta [ j ] * ( 1 - t ) + beta [ j + 1 ] * t ;}}أعد بيتا [ 0 ] ؛}

مثال برمجي بلغة جافا سكريبت

تُطبّق دالة جافا سكريبت التالية خوارزمية دي كاستيلجو على مصفوفة من نقاط التحكم أو الأقطاب ، كما سماها دي كاستيلجو في الأصل، لتقليصها واحدة تلو الأخرى حتى الوصول إلى نقطة في المنحنى عند قيمة زمنية معينة t، حيث تكون القيمة 0 للنقطة الأولى من المنحنى و1 للنقطة الأخيرة.

دالة crlPtReduceDeCasteljau ( نقاط ، t ) {let retArr = [ points . slice () ];بينما ( طول النقاط > 1 ) {​let midpoints = [];for ( let i = 0 ; i + 1 < points.length ; ++ i ) {​​let ax = points [ i ][ 0 ];let ay = points [ i ][ 1 ];let bx = points [ i + 1 ][ 0 ];let by = points [ i + 1 ][ 1 ];// a * (1-t) + b * t = a + (b - a) * tنقاط المنتصف . دفع ([ax + ( bx - ax ) * t ,ay + ( by - ay ) * t ,]);}retArr.push ( midpoints )​​النقاط = نقاط المنتصف ؛}أعد retArr ؛}

على سبيل المثال،

أقطاب فار = [ [ 0 , 128 ], [ 128 , 0 ], [ 256 , 0 ], [ 384 , 128 ] ] crlPtReduceDeCasteljau ( أقطاب , .5 )

يُعيد المصفوفة

[ [ [ 0 , 128 ], [ 128 , 0 ], [ 256 , 0 ], [ 384 , 128 ] ], [ [ 64 , 64 ], [ 192 , 0 ], [ 320 , 64 ] ], [ [ 128 , 32 ], [ 256 , 32 ]], [ [ 192 , 32 ]] ]

مما ينتج عنه النقاط والقطاعات الموضحة أدناه:

• منحنى بيزير
• خوارزمية دي بور
• مخطط هورنر لتقييم كثيرات الحدود في شكل أحادي الحد
• خوارزمية كلينشو لتقييم كثيرات الحدود في شكل تشيبيشيف

• فارين، جيرالد إي.؛ هانسفورد، ديان (2000). أساسيات تصميم الرعاية الصحية بمساعدة الحاسوب . ناتيك، ماساتشوستس: إيه كيه بيترز. رقم ISBN 978-1-56881-123-9.

• التقريب الخطي القطعي لمنحنيات بيزير – وصف لخوارزمية دي كاستيلجو، بما في ذلك معيار لتحديد متى يتم إيقاف التكرار
• منحنيات بيزير وبيكاسو – وصف وتوضيح لخوارزمية دي كاستيلجو المطبقة على منحنيات بيزير المكعبة
• خوارزمية دي كاستيلجو – مساعدة في التنفيذ وعرض توضيحي تفاعلي للخوارزمية