ド・カステリョのアルゴリズム（ベジェ曲線）
ド・カステリョのアルゴリズムと呼ばれるベジェ曲線のアルゴリズムを理解してみよう。
De Casteljauのアルゴリズム
平面内の点 $\mathbf{P}_{0,0}$, $\mathbf{P}_{1,0}$, $\cdots$ , $\mathbf{P}_{n,0}$ をとる. $0 \leqq t \leqq 1$ を固定する.
$1 \leqq j \leqq n$, $0 \leqq i \leqq n-j$ について漸化式
$\mathbf{P}_{i, j}(t) = (1-t) \mathbf{P}_{i, j-1}(t) + t \mathbf{P}_{i+1, j-1}(t)$
によって $\mathbf{P}_{0, n}(t)$ を定める. $\mathbf{P}_{i,0}(t)=\mathbf{P}_{i,0}$ とする.
$\mathbf{P}_{0,n}(t)$ の $0 \leqq t \leqq 1$ の範囲における軌跡は $n$ 次ベジェ曲線となる.
解説.
$n$ 次ベジェ曲線を定める方程式の定義は次の式だった.
$\displaystyle \sum_{k=0}^{n} {}_n \mathrm{C}_k (1-t)^{n-k}t^k \mathbf{P}_{k,0}$
ここで, 便宜上, $b_{k,j}(t) = {}_j \mathrm{C}_k (1-t)^{j-k}t^k$ とする.
$j$ に関して, $\mathbf{P}_{i, j}(t)$ $\displaystyle =\sum_{k=i}^{i+j} b_{k-i,j} \mathbf{P}_{k,0}$ となることを仮定して, $j+1$ のときも, この形になることを示す.
実際に, $j=1$ のときは,
$\mathbf{P}_{i, 1}(t)$ $= (1-t) \mathbf{P}_{i, 0} + t \mathbf{P}_{i+1, 0}$ $=b_{0,1}\mathbf{P}_{i, 0} + b_{1,1}\mathbf{P}_{i+1, 0}$ $=b_{0,j}\mathbf{P}_{i, 0} + b_{1,j}\mathbf{P}_{i+1, 0}$
となり, 仮定を満たす.
$j+1$ のとき, $\mathbf{P}_{i, j+1}(t)$ を計算する.
$\mathbf{P}_{i, j+1}(t)$ $= (1-t) \mathbf{P}_{i, j} (t)+ t \mathbf{P}_{i+1, j}(t)$
であり, $\mathbf{P}_{i, j}(t)$ と $\mathbf{P}_{i+1, j}(t)$ について仮定を適用する.
$\displaystyle \mathbf{P}_{i, j}(t)=\sum_{k=i}^{i+j} b_{k-i,j} \mathbf{P}_{k,0}$
$\displaystyle \mathbf{P}_{i+1, j}(t) = \sum_{k=i+1}^{(i+1)+j} b_{k-(i+1),j} \mathbf{P}_{k,0}$
$(1-t) \mathbf{P}_{i, j} (t)+ t \mathbf{P}_{i+1, j}(t)$
$\displaystyle =(1-t)\sum_{k=i}^{i+j} b_{k-i,j} \mathbf{P}_{k,0}$ $\displaystyle +t\sum_{k=i+1}^{(i+1)+j} b_{k-(i+1),j} \mathbf{P}_{k,0}$
この式は
$(1-t)b_{0,j} \mathbf{P}_{i,0}$ $\displaystyle +\sum_{k=i+1}^{i+j} ((1-t)b_{k-i,j}+tb_{k-(i+1),j}) \mathbf{P}_{k,0}$ $\displaystyle + tb_{j,j} \mathbf{P}_{i+j+1,0}$
のように変形できる.
$b_{k-i,j}$ $\displaystyle = {}_j \mathrm{C}_{k-i}(1-t)^{j+i-k}t^{k-i}$
$b_{k-(i+1),j}$ $\displaystyle = {}_j \mathrm{C}_{k-i-1}(1-t)^{j+i-k+1}t^{k-i-1}$
また, ${}_j \mathrm{C}_{k-i} + {}_j \mathrm{C}_{k-i-1}$ $= {}_{j+1} \mathrm{C}_{k-i}$ であることを使えば,
$(1-t)b_{k-i,j}+tb_{k-(i+1),j}$ $=b_{k-i, j+1}$
が得られる. よって,
$\mathbf{P}_{i, j+1}(t)$ $=(1-t)b_{0,j} \mathbf{P}_{i,0}$ $\displaystyle +\sum_{k=i+1}^{i+j}b_{k-i, j+1} \mathbf{P}_{k,0}$ $\displaystyle + tb_{j,j} \mathbf{P}_{i+j+1,0}$
となる.
$(1-t)b_{0,j}=b_{0,j+1}$
$tb_{j,j}=b_{j+1,j+1}$
であり,
$\mathbf{P}_{i, j+1}(t)$ $=b_{0,j+1}\mathbf{P}_{i, 0}$ $\displaystyle +\sum_{k=i+1}^{i+j}b_{k-i, j+1} \mathbf{P}_{k,0}$ $\displaystyle + b_{j+1,j+1} \mathbf{P}_{i+j+1,0}$ $\displaystyle =\sum_{k=i}^{i+j+1}b_{k-i, j+1} \mathbf{P}_{k,0}$
を得る. したがって,
$\mathbf{P}_{i, j+1}(t)$ $\displaystyle =\sum_{k=i}^{i+(j+1)}b_{k-i, j+1} \mathbf{P}_{k,0}$
となり, $j+1$ のときも仮定が正しいことが示された.
ゆえに, $j=n$, $i=0$ のときを考えれば,
$\mathbf{P}_{0, n}(t)$ $\displaystyle =\sum_{k=0}^{n}b_{k, n} \mathbf{P}_{k,0}$ $\displaystyle =\sum_{k=0}^{n}{}_n \mathrm{C}_k (1-t)^{n-k}t^k \mathbf{P}_{k,0}$
となり, 漸化式で得られる $\mathbf{P}_{0, n}(t)$ の軌跡は $n$ 次ベジェ曲線であることが分かった.
$\mathbf{P}_{0,0}$, $\mathbf{P}_{1,0}$, $\mathbf{P}_{2,0}$ の3点をとります。
$j=1$ のとき,
$\mathbf{P}_{0,1}$ $=(1-t)\mathbf{P}_{0,0}$ $+t\mathbf{P}_{1,0}$,
$\mathbf{P}_{1,1}$ $=(1-t)\mathbf{P}_{1,0}$ $+t\mathbf{P}_{2,0}$
です。
$j=2$ のとき,
$\mathbf{P}_{2,0}$ $=(1-t)\mathbf{P}_{0,1}$ $+t\mathbf{P}_{1,1}$ $=(1-t)^2\mathbf{P}_{0,0}$ $+2t(1-t)\mathbf{P}_{1,0}$ $+t^2\mathbf{P}_{0,2}$
で, $2$ 次のベジェ曲線になっています。
