自己交差する3次ベジェ曲線の交差点を求める

式が欲しかっただけなので証明が適当なのは許してほしい。

こんな形のベジェ曲線について、交差点を求めたい。

3次ベジェ曲線の4つの制御点をそれぞれP_0 = (x_0, y_0),P_1 = (x_1, y_1),P_2 = (x_2, y_2),P_3 = (x_3, y_3)とする。

3次ベジェ曲線の式

C(t) = P_0(1 - t)^3 + 3 P_1 t(1 - t)^2 + 3 P_2 t^2(1 - t) + P_3 t^3 \\

から、x,y各座標について計算して、

\begin{align*} C_x(t) &= (-x_0 +3x_1 -3x_2 + x_3)t^3 + 3(x_0 -2x_1 + x_2)t^2 +3(-x_0 +x_1)t + x_0 \\ C_y(t) &=(-y_0 +3y_1 -3y_2 + y_3)t^3 + 3(y_0 -2y_1 + y_2)t^2 +3(-y_0 +y_1)t + y_0 \end{align*}

を得る。

\begin{align*} a_x &= -x_0 + 3. * x_1 - 3. * x_2 + x_3 \\ a_y &= -y_0 + 3. * y_1 - 3. * y_2 + y_3 \\ b_x &= 3. * (x_0 - 2. * x_1 + x_2) \\ b_y &= 3. * (y_0 - 2. * y_1 + y_2) \\ c_x &= 3. * (-x_0 + x_1) \\ c_y &= 3. * (-y_0 + y_1) \\ d_x &= x_0 \\ d_y &= y_0 \\ \end{align*}

とおくと、

\begin{align*} C_x(t) &= a_x t^3+ b_x t^2 + c_x t + d_x \\ C_y(t) &= a_y t^3+ b_y t^2 + c_y t + d_y \end{align*}

t, u (ただし t \neq u) について

C_x(t) = C_x(u), C_y(t) = C_y(u)

が (0, 1) の範囲で解をもつとき、曲線は自己交差する。

途中式を書くのが面倒なので結論から言うと、この連立方程式をガリガリ解くと

a_x(a_x b_y - b_x a_y)^2t^2 + a_x(a_x c_y - c_x a_y)(a_x b_y - b_x a_y)t + a_x(a_x c_y - c_x a_y)^2 - b_x(a_x c_y - c_x a_y)(a_x b_y - b_x a_y) + c_x(a_x b_y - b_x a_y)^2 = 0

となる。

v = a_x b_y - b_x a_y \\ w = a_x c_y - c_x a_y \\ a = a_x v^2 \\ b = a_x v w \\ c = a_x w^2- b_x v w + c_x v^2 \\

とすると、

a t^2 + b t + c = 0

の二次関数になるので、単純に解の公式が使える。

d = b^2 - 4ac

として、 a = 0 と d < 0 では実数解を持たない( a = 0のときa_x = 0または v = 0 なので b = 0 となる)ので、自己交差しない。
それ以外の場合

t = \frac{-b \pm \sqrt{d}}{2a}

が解となるが、 t <=0 または 1<= t のときは交差点が曲線の端点か外側（元のベジェ曲線の延長線上）にあるため自己交差しないとみなし、 0 < t < 1 の場合のみ利用する。
また、 d = 0 で t が重解を持つ時、曲線は尖点を持ち、 t がその位置を表す（はず）。

すっとばした途中式を書くか

\begin{align*} & C_x(t)=C_x(u) \\ & a_x t^3 + b_x t^2 + c_x t + d_x = a_x u^3 + b_x u^2 + c_x u + d_x \\ & a_x t^3 - a_x u^3 + b_x t^2 - b_x u^2 + c_x t - c_x u + d_x - d_x = 0 \\ & a_x (t^3 - u^3) + b_x (t^2 - u^2) + c_x (t - u) = 0 \\ & t \neq u のとき、 \\ & a_x(t^2 + tu + u^2) + b_x(t + u) + c_x = 0 \tag{1} \\ & 同様に、C_y(t)=C_y(u) を解いて、\\ & a_y(t^2 + tu + u^2) + b_y(t + u) + c_y = 0 \\ & a_x a_y(t^2 + tu + u^2) + b_x a_y(t + u) + c_x a_y = 0 \\ & a_x a_y(t^2 + tu + u^2) + a_x b_y(t + u) + a_x c_y = 0 \\ & (a_x b_y - b_x a_y)(t + u) + a_x c_y - c_x a_y = 0 \\ & v = a_x b_y - b_x a_y, \\ & w = a_x c_y - c_x a_y として、 \\ & v(t + u) + w = 0 \\ & v = 0 のとき、自己交差しない。 \\ & v \neq 0 のとき、 \\ & u = -\frac{w}{v} - t \\ & (1) 式に代入して、\\ & a_x\{t^2 + t(-\frac{w}{v} - t) + (-\frac{w}{v} - t)^2\} - b_x(\frac{w}{v}) + c_x = 0 \\ & 両辺にv^2を掛けて、 \\ & a_x \{- vwt + (w + vt)^2\} - b_x vw + c_x v^2 = 0 \\ & a_x (w^2 + vwt + v^2t^2) - b_x vw + c_x v^2= 0 \\ & a_x v^2 t^2 + a_x v w t + a_x w^2 - b_x v w + c_x v^2 = 0 \\ \end{align*}