3次Bézierスプライン曲線の極値を求めたい。あるセグメントが
\begin{equation}
P_0 = (x_0, y_0),\ P_1 = (x_1, y_1),\ P_2 = (x_2, y_2),\ P_3 = (x_3, y_3)
\end{equation}
から定まるとする。
この時、セグメントは
\begin{equation}
\ell(t) = (1-t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1-t) P_2 + t^3 P_3,\ 0 \le t \le 1 \hspace{30pt} (1)
\end{equation}
で定まる。極値の候補としては、(1)の導函数を求めることで得られる。(1)を微分して、
\begin{equation}
\ell^{\prime}(t) = -3(t^2 -2t + 1) P_0 + 3(3t^2 - 4t + 1) P_1 -3t(3t - 2) P_2 + 3t^2 P_3
\end{equation}
を得る。$\ell^{\prime}(t) = 0$とおくことで、
\begin{equation}
(t^2 -2t + 1) P_0 - (3t^2 - 4t + 1) P_1 + t(3t - 2) P_2 - t^2 P_3 = 0
\end{equation}
となる。$t$について整理すると、
\begin{equation}
(P_0 - 3 P_1 + 3 P_2 - P_3) t^2 -2(P_0 - 2 P_1 + P_2) t + (P_0 - P_1) = 0 \hspace{30pt} (2)
\end{equation}
となる。2次方程式の解の公式から、
\begin{equation}
t = \frac{ P_0 -2 P_1 + P_2 \pm \sqrt{(P_0 -2 P_1 + P_2)^2 - (P_0 - P_1)(P_0 - 3 P_1 + 3 P_2 - P_3)} }{P_0 - 3 P_1 + 3 P_2 - P_3} \hspace{30pt} (3)
\end{equation}
を得る。これを$x$成分と$y$成分に分けて考えた場合に、[0, 1]に含まれる実数であれば、他の多少の条件と併せてセグメント上に極値が存在することが示されるだろう。
というのが数学的な観点からの理論上の計算になるが、コンピュータ上で素直に計算すると、浮動小数点が出てきてしまい丸め誤差に悩まされそうだ。コンピュータ上なら、コントロールポイントは整数座標を持っていると考えて良いのではないだろうか。数学的には格子点と言っても良いかもしれない。問題を整理すると、(2)式は、
\begin{equation}
a t^2 -2 b t + c = 0,\ a, b, c \in \mathbb{Z} \hspace{30pt} (2')
\end{equation}
と書ける。ここで、
\begin{equation}
a = P_0 - 3 P_1 + 3 P_2 - P_3,\ b = P_0 - 2 P_1 + P_2,\ c = P_0 - P_1
\end{equation}
である。正確には、その$x$成分或は$y$成分のみに着目した値である。
この時(3)式は、
\begin{equation}
t = \frac{ b \pm \sqrt{b^2 - ac} }{a} \hspace{30pt} (3')
\end{equation}
となる。
簡単のため、$a > 0$と$b^2 - ac \ge 0$を仮定する。これが[0, 1]に含まれることは以下と同値である。
\begin{equation}
-b \le \pm \sqrt{b^2 -ac} \le a - b
\end{equation}
この式から分かるように、符号に注意して両辺を2乗して比較すれば、整数同士の比較によって、セグメント上に極値(の候補)が存在するか否かを判定することができる。
ぶっちゃけ、FontForge's mathの「Finding maxima and minima of a spline」の内容を丁寧めに書いた程度の内容だが。
