ドゥ・カステルジョーのアルゴリズム

Method to evaluate polynomials in Bernstein form

数学の数値解析分野において、ドゥ・カステルジョのアルゴリズムは、発明者ポール・ドゥ・カステルジョにちなんで名付けられた、ベルンシュタイン形式の多項式またはベジェ曲線を評価するための再帰的手法である。ドゥ・カステルジョのアルゴリズムは、任意のパラメータ値で1つのベジェ曲線を2つのベジェ曲線に分割するためにも使用できる。

このアルゴリズムは、多項式を直接評価する場合と比較して数値的に安定している^[1]。このアルゴリズムの計算量は である。ここで、dは次元数、nは制御点の数である。より高速な代替手段も存在する^{[2] [3]。} ${\displaystyle O(dn^{2})}$

意味

ベジェ曲線（次数、制御点）は、バーンスタイン形式で次のように表すことができます。ここで はバーンスタイン基底多項式です。点 における曲線は、再帰関係で評価できます。 ${\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)^{n-i}t^{i}.}$$ ${\displaystyle t_{0}}$ $${\displaystyle {\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 ,n-j,\ \ 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)}.}$$

さらに、ベジェ曲線は点で、それぞれ制御点を持つ 2 つの曲線に分割できます。 ${\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}}}$$

幾何学的解釈

De Casteljau のアルゴリズムの幾何学的解釈は簡単です。

• 制御点を持つベジェ曲線を考えてみましょう。連続する点を結ぶことで、曲線の制御多角形を作成します。 ${\displaystyle P_{0},\dots ,P_{n}}$
• 次に、この多角形の各線分を比率で分割し、得られた点を結びます。こうすることで、線分が1つ少ない新しい多角形が得られます。 ${\displaystyle t:(1-t)}$
• 単一の点に到達するまでこのプロセスを繰り返します。これが、パラメータに対応する曲線の点です。 ${\displaystyle t}$

次の図は、3 次ベジェ曲線に対するこのプロセスを示しています。

構築された中間点は、実際には2つの新しいベジェ曲線の制御点であり、どちらも以前の曲線と完全に一致していることに注意してください。このアルゴリズムは、 における曲線を評価するだけでなく、 において曲線を2つの部分に分割し、2つの部分曲線の方程式をベジェ形式で提供します。 ${\displaystyle t}$ ${\displaystyle t}$

上記の解釈は、非有理ベジェ曲線にも適用できます。 における有理ベジェ曲線を評価するには、点を に投影します。例えば、3次元の曲線では、制御点と重みが重み付き制御点 に投影されます。その後、アルゴリズムは通常どおり で補間を行います。結果として得られる4次元の点は、の透視分割を用いて3次元空間に投影し直すことができます。 ${\displaystyle \mathbf {R} ^{n}}$ ${\displaystyle \mathbf {R} ^{n+1}}$ ${\displaystyle \{(x_{i},y_{i},z_{i})\}}$ ${\displaystyle \{w_{i}\}}$ ${\displaystyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}}$ ${\displaystyle \mathbf {R} ^{4}}$

一般に、有理曲線（または曲面）上の演算は、射影空間における非有理曲線上の演算と等価です。「重み付き制御点」と重みによるこの表現は、有理曲線を評価する際にしばしば便利です。

表記

手計算で計算する場合、係数を三角形の形で書き出すと便利です。バーンスタイン多項式を評価するために点t ₀を選択する場合、三角形の形の2つの対角線を使用して多項式の分割を構築し、 $${\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}}}$$ $${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]}$$ $${\displaystyle 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}]}$$ $${\displaystyle 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次ベジェ曲線

3次ベジェ曲線

4次ベジェ曲線

n + 1 個の制御点P _iを持つ3 次元空間でn次ベジェ曲線を評価する場合、ベジェ曲線を 3 つの別々の方程式に分割し、De Casteljau のアルゴリズムを使用して個別に評価します。 $${\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}}}$$

例

点t ₀におけるバーンスタイン係数を使用して、2次バーンスタイン多項式を評価します。 $${\displaystyle {\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}}$$

再帰は で開始し、2 回目の反復で再帰は で停止します。これは、期待される次数 2のバーンスタイン多項式です。 $${\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}}}$$

実装

以下は、さまざまなプログラミング言語での De Casteljau アルゴリズムの実装例です。

ハスケル

deCasteljau :: Double -> [( Double , Double )] -> ( Double , Double )        ドゥカステルジョt [ b ] = b    deCasteljau t係数= deCasteljau t減少       どこ 削減= zipWith ( lerpP t ) coefs (末尾の係数)        lerpP t ( x0 , y0 ) ( x1 , y1 ) = ( lerp t x0 x1 , lerp t y0 y1 )               線形代数t a b = t * b + ( 1 - t ) * a             

パイソン

def de_casteljau ( t : float , coefs : list [ float ]) -> float :       """ド・カステルジョのアルゴリズム。""" beta  =  coefs.copy () # このリストの値は上書きされます  n  =  len (ベータ)  j が 範囲( 1 ,  n )の場合:  k が 範囲( n  -  j )の場合: ベータ[ k ]  = ベータ[ k ]  *  ( 1  -  t )  + ベータ[ k  +  1 ]  *  t リターン ベータ[ 0 ]

ジャワ

パブリックdouble deCasteljau ( double t , double []係数) {       double [] beta =係数;    int n =ベータ.長さ;    ( int i = 1 ; i < n ; i ++ )の場合{          ( int j = 0 ; j < ( n - i ) ; j ++ ) {            ベータ[ j ] =ベータ[ j ] * ( 1 - t ) +ベータ[ j + 1 ] * t ;             } } beta [ 0 ]を返す。 }

JavaScriptのコード例

次のJavaScript関数は、De Casteljauのアルゴリズムを、De Casteljauによって最初に命名された制御点または極の配列に適用し、指定されたtの曲線上の点に到達するまで、それらを1つずつ減らします。曲線の最初の点は0で、最後の点は1です。

関数crlPtReduceDeCasteljau (ポイント, t ) {    retArr = [ points . slice () ]とします。      while (ポイント.長さ> 1 ) {     中間点を[]とします。   for ( let i = 0 ; i + 1 < points . length ; ++ i ) {         ax = points [ i ][ 0 ]とします。   ay = points [ i ][ 1 ]とします。   bx = points [ i + 1 ][ 0 ]とします。   ポイント[ i + 1 ][ 1 ]をby =とします。    // a * (1-t) + b * t = a + (b - a) * t中点。プッシュ（[ax + ( bx - ax ) * t 、      ay + ( by - ay ) * t 、      ]);} retArr . push (中間点) ポイント=中点;  }retArrを返します。 }

例えば、

varポール= [ [ 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 ]] ]                           

これにより、以下にプロットされる点と線分が生成されます。

隣接する点に線形補間を再帰的に適用して得られる中間線分

参照

• ベジェ曲線
• ド・ブールのアルゴリズム
• 単項式形式で多項式を評価するためのホーナースキーム
• チェビシェフ形式の多項式を評価するクレンショウアルゴリズム

参考文献

1. Delgado, J.; Mainar, E.; Peña, JM (2023-10-01). 「de Casteljau型アルゴリズムとBernstein表現の精度について」. Computer Aided Geometric Design . 106 102243. doi : 10.1016/j.cagd.2023.102243 . ISSN  0167-8396.
2. Woźny, Paweł; Chudy, Filip (2020-01-01). 「ベジェ曲線を評価するための線形時間幾何学アルゴリズム」. Computer-Aided Design . 118 102760. arXiv : 1803.06843 . doi :10.1016/j.cad.2019.102760. ISSN  0010-4485.
3. Fuda, Chiara; Ramanantoanina, Andriamahenina; Hormann, Kai (2024). 「有理ベジェ曲線を評価するためのアルゴリズムの包括的な比較」. Dolomites Research Notes on approximation . 17 (9/2024): 56– 78. doi :10.14658/PUPJ-DRNA-2024-3-9. ISSN  2035-6803.

• ファリン、ジェラルド・E.、ハンスフォード、ダイアン（2000年）『CAGDのエッセンス』ネイティック、マサチューセッツ州：AKピーターズ社、ISBN 978-1-56881-123-9。

外部リンク

• ベジェ曲線の区分線形近似 - 再帰を停止するタイミングを決定する基準を含む、ドゥ・カステルジョのアルゴリズムの説明
• ベジェ曲線とピカソ – 3次ベジェ曲線に適用されたドゥ・カステルジョーのアルゴリズムの説明と図解
• de Casteljau のアルゴリズム – 実装ヘルプとアルゴリズムのインタラクティブなデモンストレーション

Retrieved from "https://en.wikipedia.org/w/index.php?title=De_Casteljau%27s_algorithm&oldid=1321323744"