डी 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},\ \ i=0,\ldots ,n$

$\beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0},\ \ i=0,\ldots ,n-j,\ \ 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)}$

उदाहरण कार्यान्वयन

हास्केल (प्रोग्रामिंग भाषा) में डी कैस्टेलजौ के एल्गोरिदम का उदाहरण कार्यान्वयन यहां दिया गया है:

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

पायथन (प्रोग्रामिंग भाषा) में डी कैस्टेलजौ के एल्गोरिथ्म का एक उदाहरण कार्यान्वयन:

def de_casteljau(t, coefs):
    beta = [c for c in coefs] # values in this list are overridden
    n = len(beta)
    for j in range(1, n):
        for k in range(n - j):
            beta[k] = beta[k] * (1 - t) + beta[k + 1] * t
    return beta[0]

जावास्क्रिप्ट में डी कैस्टेलजौ के एल्गोरिथ्म का एक उदाहरण कार्यान्वयन:

इंटरमीडिएट लाइन सेगमेंट आसन्न बिंदुओं पर रैखिक इंटरपोलेशन को पुनरावर्ती रूप से लागू करके प्राप्त किया जाता है।

// Example: lerp(0.5, 0.0, 1.0) == 0.5
let lerp = (t, p1, p2) => (1 - t) * p1 + t * p2;

// Example: reduce(0.5, ...[0.0, 1.0, 2.0, 3.0]) == [0.5, 1.5, 2.5]
let reduce = (t, p1, p2, ...ps) => ps.length > 0
    ? [lerp(t, p1, p2), ...reduce(t, p2, ...ps)]
    : [lerp(t, p1, p2)];

// Example: deCasteljau(0.5, [0.0, 1.0, 2.0, 3.0]) == 1.5
let deCasteljau = (t, ps) => ps.length > 1
    ? deCasteljau(t, reduce(t, ...ps))
    : ps[0];

टिप्पणियाँ

When doing the calculation by hand it is useful to write down the coefficients in a triangle scheme as

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

When choosing a point t₀ to evaluate a Bernstein polynomial we can use the two diagonals of the triangle scheme to construct a division of the polynomial

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

into

$B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right)\!,\quad t\in [0,t_{0}]$

and

$B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right)\!,\quad t\in [t_{0},1].$

उदाहरण

हम बर्नस्टीन गुणांकों के साथ डिग्री 2 के बर्नस्टीन बहुपद का मूल्यांकन करना चाहते हैं

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

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

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

बिंदु पर टी₀.

हम रिकर्सन के साथ शुरू करते हैं

$\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 का अपेक्षित बर्नस्टीन बहुपद है।

बेजियर वक्र

एक बेजियर वक्र

n + 1 नियंत्रण बिंदु 'P' के साथ 3-आयामी अंतरिक्ष में डिग्री n के बेज़ियर वक्र का मूल्यांकन करते समय_i

$\mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ 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),\ t\in [0,1]$

$B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t),\ t\in [0,1]$

$B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t),\ t\in [0,1]$

जिसका हम व्यक्तिगत रूप से De Casteljau's कलन विधि का उपयोग करके मूल्यांकन करते हैं।

ज्यामितीय व्याख्या

De Casteljau के एल्गोरिथम की ज्यामितीय व्याख्या सीधी है।

• नियंत्रण बिंदुओं के साथ बेज़ियर वक्र पर विचार करें $P_{0},...,P_{n}$. लगातार बिंदुओं को जोड़ने से हम वक्र का नियंत्रण बहुभुज बनाते हैं।
• अब इस बहुभुज के प्रत्येक रेखाखंड को अनुपात के साथ उपविभाजित करें $t:(1-t)$ और आपको प्राप्त होने वाले बिंदुओं को कनेक्ट करें। इस तरह आप एक कम खंड वाले नए बहुभुज पर पहुंचते हैं।
• प्रक्रिया को तब तक दोहराएं जब तक कि आप एकल बिंदु पर न पहुंच जाएं - यह पैरामीटर के संगत वक्र का बिंदु है $t$.

निम्न चित्र घन बेज़ियर वक्र के लिए इस प्रक्रिया को दिखाता है:

ध्यान दें कि निर्मित किए गए मध्यवर्ती बिंदु वास्तव में दो नए बेज़ियर वक्र के लिए नियंत्रण बिंदु हैं, दोनों बिल्कुल पुराने के साथ मेल खाते हैं। यह एल्गोरिथ्म न केवल वक्र का मूल्यांकन करता है $t$, लेकिन वक्र को दो टुकड़ों में विभाजित करता है $t$, और बेजियर रूप में दो उप-वक्रों के समीकरण प्रदान करता है।

ऊपर दी गई व्याख्या गैर-तर्कसंगत बेजियर वक्र के लिए मान्य है। में एक तर्कसंगत बेज़ियर वक्र का मूल्यांकन करने के लिए $\mathbf {R} ^{n}$, हम बिंदु को प्रोजेक्ट कर सकते हैं $\mathbf {R} ^{n+1}$; उदाहरण के लिए, तीन आयामों में एक वक्र के अपने नियंत्रण बिंदु हो सकते हैं $\{(x_{i},y_{i},z_{i})\}$ और वजन $\{w_{i}\}$ भारित नियंत्रण बिंदुओं के लिए अनुमानित $\{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$. एल्गोरिथ्म तब सामान्य रूप से आगे बढ़ता है, इसमें प्रक्षेपित होता है $\mathbf {R} ^{4}$. परिणामी चार-आयामी बिंदुओं को परिप्रेक्ष्य विभाजन के साथ तीन-अंतरिक्ष में वापस प्रक्षेपित किया जा सकता है।

सामान्य तौर पर, एक परिमेय वक्र (या सतह) पर संचालन प्रक्षेपी स्थान में एक गैर-तर्कसंगत वक्र पर संचालन के बराबर होता है। तर्कसंगत घटता का मूल्यांकन करते समय भारित नियंत्रण बिंदु और भार के रूप में यह प्रतिनिधित्व अक्सर सुविधाजनक होता है।

यह भी देखें

• बेज़ियर कर्व्स
• डी बूर का एल्गोरिदम
• एकपदी रूप में बहुपदों का मूल्यांकन करने के लिए हॉर्नर योजना
• चेबिशेव रूप में बहुपदों का मूल्यांकन करने के लिए क्लेंशॉ एल्गोरिथम

संदर्भ

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

बाहरी संबंध

• Piecewise linear approximation of Bézier curves – description of De Casteljau's algorithm, including a criterion to determine when to stop the recursion
• Bezier Curves and Picasso — Description and illustration of De Casteljau's algorithm applied to cubic Bézier curves.
• de Casteljau's algorithm - Implementation help and interactive demonstration of the algorithm.