目次

• ベジエ曲線とは
• 滑らかな曲線をベジエ曲線で近似する
  • JavaScriptによるコード例
• 差の評価

ベジエ曲線とは

ベジエ曲線とはWikipedia(英語版)によると(本当はちゃんとした文献を当たるべきなのだろうが)、\(n+1\) 個の点 \(x_0, x_1, \dots, x_n\) が与えられた時に\[
B(t)=\sum_{i=0}^{n}\binom{n}{i}t^i(1-t)^{n-i}x_i, \quad 0\le t\le 1
\]で定まる曲線らしい。始点 (\(t=0\)) は \(x_0\)、終点(\(t=1\))は \(x_n\) である。\(n\) のことを次数という。

(1次の場合は単なる線分なので置いておいて)よく使われるのは2次の場合と3次の場合である。それぞれ\begin{align*}
\mathit{quadratic B\acute{e}zier}(t)&=(1-t)^2x_0+2t(1-t)x_1+t^2x_2, \\
\mathit{cubic B\acute{e}zier}(t)&=(1-t)^3x_0+3t(1-t)^2x_1+3t^2(1-t)x_2+t^3x_3
\end{align*}で与えられる。

2次の場合は始点 \(x_0\) と終点 \(x_2\) の他に1個の制御点 \(x_1\)、3次の場合は始点 \(x_0\)、終点 \(x_3\) の他に2個の制御点 \(x_1\), \(x_2\) によって決まる。制御点は始点及び終点における接線を与えるためにある。ここではベジエ曲線についてはこれ以上突っ込んだ事は取り扱わない。

こういう、「制御点を与えて曲線を描く」のは、ドロー系の描画ソフトウエアを使ったことのある方はおなじみだろう。SVGやPostScriptなどのベクター画像形式でも、ベジエ曲線は基本的な描画対象である。

プログラミングに関して言うと、大抵のグラフィックAPIには2次か3次のベジエ曲線を描画するAPIがある。例えば、HTML5 Canvasの場合は

context.quadraticCurveTo(cpx, cpy, x, y) /* 2次 */
context.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, x, y) /* 3次 */

というAPIがあり、Cocoaの場合は

NSBezierPath
-(void)curveToPoint:(NSPoint)aPoint controlPoint1:(NSPoint1) controlPoint2:(NSPoint)controlPoint2 /* 3次 */

というAPIがある。いずれも始点を指定する引数がないが、これらのAPIを使った時の始点は「現在の点の位置」になる。つまり、最後の描画操作における終点か、あるいはmoveToなどのAPIを使って指定した点である。

滑らかな曲線をベジエ曲線で近似する

さて、滑らかな曲線 \(f\colon[0,1]\to\mathbf{R}^2\) をベジエ曲線で近似するということを考えよう。動機としては例えば、プログラミングで曲線を描きたい時に、大抵のグラフィックスAPIには任意の曲線を描画するようなAPIはないので(2次か3次の)ベジエ曲線を使って近似する事になる。2次か3次と書いたが、以後3次のベジエ曲線で近似する事を考える。

まず、曲線の全体を1個のベジエ曲線で近似することを考えよう。始点と終点は、もとの曲線のそれをそのまま使えば良い。制御点を決めるのに、始点と終点における微分を使うことにしよう。つまり、もとの曲線とベジエ曲線の微分が、始点と終点において一致するようにする。条件を式で書くとこうなる:\begin{align*}
B(0)&=f(0),&B'(0)&=f'(0), \\
B(1)&=f(1),&B'(1)&=f'(1).
\end{align*}この条件に従って \(x_0,\dots,x_3\) を決めてやると\begin{align*}
x_0&=f(0), \\
x_1&=f(0)+\frac{1}{3}f'(0), \\
x_2&=f(1)-\frac{1}{3}f'(1), \\
x_3&=f(1)
\end{align*}となる。定義域が \([0,1]\) の\(f\) に対して \(f'(0)\) や \(f'(1)\) を考えているが、適当にいい感じに処理する。

次に、描きたい曲線を \(N\) 等分して、それぞれの部分をベジエ曲線で近似することを考えよう。元の関数 \(f\) から、細分した関数 \(f^{(k)}\>(k=0,\dots,N-1)\) を以下のように作る。
\begin{align*}
f^{(0)}(t)&=f\Bigl(\frac{t}{N}\Bigr), \\
&\vdots \\
f^{(k)}(t)&=f\Bigl(\frac{t+k}{N}\Bigr), \\
&\vdots \\
f^{(N-1)}(t)&=f\Bigl(\frac{t+N-1}{N}\Bigr).
\end{align*}
このそれぞれの \(f^{(k)}\) をベジエ曲線で近似したものを、\[
B^{(k)}(t)=(1-t)^3x_0^{(k)}+3t(1-t)^2x_1^{(k)}+3t^2(1-t)x_2^{(k)}+t^3x_3^{(k)}
\]とする。それぞれの始点、終点、制御点は\begin{align*}
x_0^{(k)}&=f^{(k)}(0)=f\Bigl(\frac{k}{N}\Bigr), \\
x_1^{(k)}&=f^{(k)}(0)+\frac{1}{3}f^{(k)\prime}(0)=f\Bigl(\frac{k}{N}\Bigr)+\frac{1}{3N}f’\Bigl(\frac{k}{N}\Bigr), \\
x_2^{(k)}&=f^{(k)}(1)-\frac{1}{3}f^{(k)\prime}(1)=f\Bigl(\frac{k+1}{N}\Bigr)-\frac{1}{3N}f’\Bigl(\frac{k+1}{N}\Bigr), \\
x_3^{(k)}&=f^{(k)}(1)=f\Bigl(\frac{k+1}{N}\Bigr)
\end{align*}となる。

JavaScriptによるコード例

これらのことを踏まえると、関数 f によって与えられる曲線をベジエ曲線で近似するJavaScriptの疑似コードは次のようになる:

function f(t) {
  return {x: ..., y: ...};
}
function df(t) {
  return {x: ..., y: ...};
}
var last = null, lastd = null;
for (var j = 0; j <= N; ++j) {
  var p = f(j/N);
  var d = df(j/N);
  if (last === null) {
    context.moveTo(p.x, p.y);
  } else {
    var cp1x = last.x+lastd.x/(3*N);
    var cp1y = last.y+lastd.y/(3*N);
    var cp2x = p.x-d.x/(3*N);
    var cp2y = p.y-d.y/(3*N);
    context.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, p.x, p.y);
  }
  last = p;
  lastd = d;
}

どうせなので、実際にブラウザ上で動作するデモを載せておく。黒線が描きたい曲線、色付きの曲線がベジエ曲線による近似である。N=*のボタンを押すと制御点を表示する。

差の評価

このように近似した曲線と元々の与えられた曲線の差はどれくらいだろうか？曲線同士の差を表す量として、ここではsupノルム\[
\left\lVert B-f\right\rVert=\sup_{t\in[0,1]}\left\lVert B(t)-f(t)\right\rVert
\]を採用する。また、ベクトルのノルムは標準的なユークリッドノルムとする。以後、与えられた \(f\) は \(C^2\) 級とする。

まず、ベジエ曲線を表す式を整理する。\begin{align*} B(t)&=(1-t)^3f(0)+3t(1-t)^2\left(f(0)+\frac{1}{3}f'(0)\right)+3t^2(1-t)\left(f(1)-\frac{1}{3}f'(1)\right)+t^3f(1) \\ %&=(1-t)^2\left\{(1-t)f(0)+3t\left(f(0)+\frac{1}{3}f'(0)\right)\right\}+t^2\left\{3(1-t)\left(f(1)-\frac{1}{3}f'(1)\right)+tf(1)\right\} \\ %&=(1-t)^2\left\{(1+2t)f(0)+tf'(0)\right\}+t^2\left\{-(1-t)f'(1)+(3-2t)f(1)\right\} \\ %&=(1-t)^2(1+2t)f(0)+t(1-t)^2f'(0)+t^2\left\{-(1-t)f'(1)+(3-2t)f(1)\right\} \\ %&=f(0)+t^2(-3+2t)f(0)+t(1-2t+t^2)f'(0)+t^2\left\{-(1-t)f'(1)+(3-2t)f(1)\right\} \\ &\quad\vdots\quad(\text{中略}) \\
&=f(0)+tf'(0)+t^2\left\{-(2-t)f'(0)-(1-t)f'(1)+(3-2t)(f(1)-f(0))\right\}
\end{align*}ここで、平均値の定理を使いたいので、曲線の \(x\) 成分、\(y\) 成分を \(B=(B_0,B_1),\>f=(f_0,f_1)\) のように分けて考える。\begin{align*}
B_i(t)&=f_i(0)+tf_i'(0)+t^2\left\{-(2-t)f_i'(0)-(1-t)f_i'(1)+(3-2t)(f_i(1)-f_i(0))\right\} \\
&=f_i(0)+tf_i'(0)+t^2\left\{-(2-t)f_i'(0)-(1-t)f_i'(1)+(3-2t)f_i'(\theta_i)\right\} \quad (\theta_i\in(0,1))\\
&=f_i(0)+tf_i'(0)+t^2\left\{(2-t)(f_i'(\theta_i)-f_i'(0))+(1-t)(f_i'(\theta_i)-f_i'(1))\right\} \\
&=f_i(0)+tf_i'(0)+t^2\left\{(2-t)f_i^{\prime\prime}(\phi_i)\theta_i+(1-t)f_i^{\prime\prime}(\psi_i)(\theta_i-1)\right\} \quad (\phi_i\in(0,\theta_i),\psi_i\in(\theta_i,1))
\end{align*}では、\(B_i\) と \(f_i\) の差を考えよう。テイラーの定理で、\(f_i(t)\) が\[
f_i(t)=f_i(0)+tf_i'(0)+\frac{1}{2}t^2f_i^{\prime\prime}(\xi),\quad(\xi\in(0,t))
\]のように表されるとする。これを使うと、\begin{align*} \left\lvert B_i(t)-f_i(t) \right\rvert &=\left\lvert t^2\left\{(2-t)f_i^{\prime\prime}(\phi_i)\theta_i+(1-t)f_i^{\prime\prime}(\psi_i)(\theta_i-1)\right\}-\frac{1}{2}t^2f_i^{\prime\prime}(\xi) \right\rvert \\ %&=t^2\left\lvert \left\{(2-t)f_i^{\prime\prime}(\phi_i)\theta_i+(1-t)f_i^{\prime\prime}(\psi_i)(\theta_i-1)\right\}-\frac{1}{2}f_i^{\prime\prime}(\xi) \right\rvert \\ &\le t^2\left((2-t)\left\lvert f_i^{\prime\prime}(\phi_i)\theta_i \right\rvert+(1-t)\left\lvert f_i^{\prime\prime}(\psi_i)(\theta_i-1) \right\rvert+\frac{1}{2}\left\lvert f_i^{\prime\prime}(\xi) \right\rvert\right) \\ &\le t^2\left((2-t)\left\lvert f_i^{\prime\prime}(\phi_i)\right\rvert+(1-t)\left\lvert f_i^{\prime\prime}(\psi_i)\right\rvert+\frac{1}{2}\left\lvert f_i^{\prime\prime}(\xi) \right\rvert\right) \\ &\le t^2\left((2-t)+(1-t)+\frac{1}{2}\right)\sup_{t\in[0,1]}\left\lvert f_i^{\prime\prime}(t)\right\rvert \\ &= t^2\left(\frac{7}{2}-2t\right)\sup_{t\in[0,1]}\left\lvert f_i^{\prime\prime}(t)\right\rvert \\ &\le \frac{3}{2}\sup_{t\in[0,1]}\left\lvert f_i^{\prime\prime}(t)\right\rvert \end{align*}と評価できる。ここで、\(t^2\left(\frac{7}{2}-2t\right)\) の \(t\in[0,1]\) における最大値が \(\frac{3}{2}\) であることを使っている。

成分ごとの評価はできたので、全体の評価をしよう。\begin{align*}
\left\lVert B-f \right\rVert
&=\sup_{t\in[0,1]} \left\lVert B(t)-f(t) \right\rVert \\
&=\sup_{t\in[0,1]} \sqrt{\left\lvert B_0(t)-f_0(t) \right\rvert^2+\left\lvert B_1(t)-f_1(t) \right\rvert^2} \\
&\le\sqrt{\left\lVert B_0-f_0 \right\rVert^2+\left\lVert B_1-f_1 \right\rVert^2} \\
&\le\frac{3}{2}\sqrt{\left\lVert f_0^{\prime\prime} \right\rVert^2+\left\lVert f_1^{\prime\prime} \right\rVert^2} \\
&\le\frac{3}{\sqrt{2}}\left\lVert f^{\prime\prime} \right\rVert \\
\end{align*}これが、与えられた曲線を1個のベジエ曲線で近似した時の差の評価である。

次に、\(N\) 分割して近似した場合を考えよう。\[
f^{(k)\prime\prime}(t)=\frac{1}{N}f^{\prime\prime}\Bigl(\frac{t+k}{N}\Bigr)
\]に注意すると、\begin{align*}
\left\lVert B-f\right\rVert
&=\max_{k=0,\dots,N-1}\left\lVert B^{(k)}(t)-f^{(k)}(t)\right\rVert \\
&\le\max_{k=0,\dots,N-1}\frac{3}{\sqrt{2}}\left\lVert f^{(k)\prime\prime}\right\rVert \\
&=\frac{3}{\sqrt{2}}\max_{k=0,\dots,N-1}\sup_{t\in[0,1]}\left\lVert f^{(k)\prime\prime}(t)\right\rVert \\
&\le\frac{3}{\sqrt{2}}\max_{k=0,\dots,N-1}\sup_{t\in[0,1]}\frac{1}{N^2}\left\lVert f^{\prime\prime}\Bigl(\frac{t+k}{N}\Bigr)\right\rVert \\
&=\frac{3}{\sqrt{2}N^2}\sup_{t\in[0,1]}\left\lVert f^{\prime\prime}(t)\right\rVert \\
&=\frac{3}{\sqrt{2}N^2}\left\lVert f^{\prime\prime}\right\rVert
\end{align*}となる。要するに、評価に \(f\) の2階微分を使っているため、パラメーターを \(N\) 等分すると評価は \(\frac{1}{N^2}\) 倍になる。

まあもっと頑張ればもっといい評価が得られるのか知らないが、とりあえずはこんなもんだろう。その辺の文献とかをあたればこの辺の事も書いてあるのだろうが、この程度なら調べるよりも手を動かす方が早いと思った。

追記：評価の際に \(0\le t\le \frac{1}{2}\) と \(\frac{1}{2}\le t\le1\) を別々に考えて、後者を1のまわりでのテイラー展開で考えれば、成分ごとに考えた場合\[
\left\lvert B_i(t)-f_i(t) \right\rvert\le \frac{5}{8}\sup_{t\in[0,1]}\left\lvert f_i^{\prime\prime}(t)\right\rvert
\]という評価ができて、全体で\[
\left\lVert B-f \right\rVert\le\frac{5}{4\sqrt{2}}\left\lVert f^{\prime\prime} \right\rVert
\]となり、\(N\) 分割した場合は\[
\left\lVert B-f\right\rVert\le\frac{5}{4\sqrt{2}N^2}\left\lVert f^{\prime\prime}\right\rVert
\]という評価ができる。まあ本文に書いたものと定数倍しか変わらないが。（まあ3次のベジエ曲線で近似する時は \(f\) の1次の微分までしか考慮しないから、差が \(\left\lVert f^{\prime\prime}\right\rVert\) のオーダーになるのは当たり前か）