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

数学の数値解析の分野において、ドゥ・カステルジャのアルゴリズムは、発明者のポール・ドゥ・カステルジャにちなんで名付けられた、ベルンシュタイン形式の多項式またはベジェ曲線を評価する再帰的な方法です。ドゥ・カステルジャのアルゴリズムは、任意のパラメータ値で単一のベジェ曲線を 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)^{ni}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 ,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)}.}$$

さらに、ベジェ曲線は点で、それぞれ制御点を持つ 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 _0を選択する場合、三角形スキームの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}^{(ni)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right)\!,\quad t\in [t_{0},1].}$$

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 の Bernstein 多項式です 。 $${\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  = 長さ(ベータ)
     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 関数は、De Casteljau のアルゴリズムを、De Casteljau によって最初に命名された制御点または極の配列に適用し、曲線の最初の点が 0、最後の点が 1 の間の指定された t で曲線上の点に到達するまで、それらを 1 つずつ減らします。

関数crlPtReduceDeCasteljau (ポイント、t ) {   
    retArr = [ points . slice () ]とします。      
	while (ポイント.長さ> 1 ) {    
        中間点を[]とします。   
		( i = 0とします; i + 1 <ポイント.長さ; ++ i ) {         
			ax = points [ i ][ 0 ]とします。   
			ay = points [ i ][ 1 ]とします。   
			bx = points [ i + 1 ][ 0 ]とします。   
			点[ i + 1 ][ 1 ]を次のように定義します。   
            // 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]],
       ]

以下にプロットされている点とそれらを結ぶ線分はどれですか

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

• Farin, Gerald E.; Hansford, Dianne (2000). The Essentials of CAGD . Natick, MA: AK Peters. ISBN 978-1-56881-123-9。

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