任意の点とBezier曲線とで最小となる長さ(距離)を求める

任意の点\(Z\)とBezier曲線\(\mathrm{Bezier}(t)\)とで最小となる長さ\(L\)(距離)を求める

3次のベジェ曲線(媒介変数\(t\)表示)

任意の点\(Z\)とBezier曲線\(\mathrm{Bezier}(t)\)との長さ\(L\)

$$\begin{eqnarray} \mathrm{Anchor}_0&=&(a, p)\;\cdots\;通過点 \\\mathrm{Handle}_0&=&(b, q)\;\cdots\;制御点 \\\mathrm{Handle}_1&=&(c, r)\;\cdots\;制御点 \\\mathrm{Anchor}_1&=&(d, s)\;\cdots\;通過点 \\\mathrm{Bezier}(t|\mathrm{Anchor}_0,\mathrm{Handle}_0,\mathrm{Handle}_1,\mathrm{Anchor}_1)&=&\left(X(t|a,b,c,d),Y(t|p,q,r,s)\right)\; t\in[0,1] \\&&\;\cdots\;3次のベジェ曲線 \end{eqnarray}$$ $$\begin{eqnarray} \\X(t|a,b,c,d)&=&a(1-t)^3+3b(1-t)^2t+3c(1-t)t^2+d\;t^3 \\&=&a(1-3t+3t^2-t^3)+3b(t-2t^2+t^3)+3c(t^2-t^3)+d\;t^3 \\&=&a+3(-a+b)t+3(a-2b+c)t^2+(-a+3b-3c+d)t^3 \\&=&A+3Bt+3Ct^2+Dt^3 \;\cdots\;A=a, B=-a+b, C=a-2b+c, D=-a+3b-3c+d \\&=&X(t|A,B,C,D) \\Y(t|p,q,r,s)&=&p(1-t)^3+3q(1-t)^2t+3r(1-t)t^2+st^3 \\&=&a+3(-p+q)t+3(p-2q+r)t^2+(-p+3q-3r+s)t^3 \\&=&P+3Qt+3Rt^2+St^3 \;\cdots\;P=p, Q=-p+q, R=p-2q+r, S=-p+3q-3r+s \\&=&Y(t|P,Q,R,S) \end{eqnarray}$$

3次のベジェ曲線の\(X(t), Y(t)\)の微分

$$\begin{eqnarray} \\\frac{\mathrm{d}}{\mathrm{d}t}X(t) &=&3B+6Ct+3Dt^2 \\&=&3\left(B+2Ct+Dt^2\right) \\\frac{\mathrm{d}}{\mathrm{d}t}Y(t) &=&3Q+6Rt+3St^2 \\&=&3\left(Q+2Rt+St^2\right) \end{eqnarray}$$

任意の点\(Z\)からベジェ曲線の\(X(t), Y(t)\)の距離

$$\begin{eqnarray} \\Z&=&(z_x, z_y)\;\cdots\;任意の点 \\L&=&\sqrt{\left(X(t|a,b,c,d)-z_x\right)^2+\left(Y(t|p,q,r,s)-z_y\right)^2}\;\cdots\;任意の点zとBezier曲線との距離 \end{eqnarray}$$ \(Z=(0,0)\)になるように\(z_x,z_y\)だけ，\(a,b,c,d,p,q,r,s\)を平行移動する．距離は変わらないので\(L\)． $$\begin{eqnarray} \\L&=&\sqrt{X^2(t|a-z_x,b-z_x,c-z_x,d-z_x)+Y^2(t|p-z_y,q-z_y,r-z_y,s-z_y)} \end{eqnarray}$$ 平行移動後の係数を改めて\(a^\prime=a-z_x,b^\prime=b-z_x,c^\prime=c-z_x,d^\prime=d-z_x,p^\prime=p-z_y,q^\prime=q-z_y,r^\prime~r-z_y,s=s^\prime-z_y\)と定義し直して計算を続ける． $$\begin{eqnarray} \\L&=&\sqrt{\left(X(t|a^\prime,b^\prime,c^\prime,d^\prime)\right)^2+\left(Y(t|p^\prime,q^\prime,r^\prime,s^\prime)\right)^2} \\&=&\sqrt{\left(X(t|A^\prime,B^\prime,C^\prime,D^\prime)\right)^2+\left(Y(t|P^\prime,Q^\prime,R^\prime,S^\prime)\right)^2} \\&&\;\cdots\; A^\prime=a^\prime ,B^\prime=-a^\prime+b^\prime ,C^\prime=a^\prime-2b^\prime+c^\prime ,D^\prime=-a^\prime+3b^\prime-3c^\prime+d^\prime \\&&\;\cdots\; P^\prime=p^\prime ,Q^\prime=-p^\prime+q^\prime ,R^\prime=p^\prime-2q^\prime+r^\prime ,S^\prime=-p^\prime+3q^\prime-3r^\prime+s^\prime \end{eqnarray}$$

\(L\)を極値とする\(t\)を求める

$$\begin{eqnarray} \frac{\mathrm{d}}{\mathrm{d}t}L&=&0\;\cdots\;Lの微分が0となるtが，Lの極値．その中で最小の距離Lとなるものを探す． \end{eqnarray}$$ $$\begin{eqnarray} \frac{\mathrm{d}}{\mathrm{d}t}L&=&\frac{1}{2}\left(X^2(t)+Y^2(t)\right)^{-\frac{1}{2}} \left\{ \frac{\mathrm{d}}{\mathrm{d}t}\left(X^2(t)+Y^2(t)\right) \right\} \\&=&\frac{1}{2}\left(X^2(t)+Y^2(t)\right)^{-\frac{1}{2}} \left\{ \left(\frac{\mathrm{d}}{\mathrm{d}t}X^2(t)\right) +\left(\frac{\mathrm{d}}{\mathrm{d}t}Y^2(t)\right) \right\} \\&=&\frac{1}{2}\left(X^2(t)+Y^2(t)\right)^{-\frac{1}{2}} \left\{ 2X(t)\left(\frac{\mathrm{d}}{\mathrm{d}t}X(t)\right) +2Y(t)\left(\frac{\mathrm{d}}{\mathrm{d}t}Y(t)\right) \right\} \\&=&\frac{X(t)\left(\frac{\mathrm{d}}{\mathrm{d}t}X(t)\right) +Y(t)\left(\frac{\mathrm{d}}{\mathrm{d}t}Y(t)\right)}{\sqrt{X^2(t)+Y^2(t)}} \;\cdots\;分母は常に0以上なので，0となる場合を除けば，分子だけ考えればよい． \end{eqnarray}$$ $$\begin{eqnarray} \\0&=&X(t)\left(\frac{\mathrm{d}}{\mathrm{d}t}X(t)\right) +Y(t)\left(\frac{\mathrm{d}}{\mathrm{d}t}Y(t)\right) \\&=& \left(A^\prime+3B^\prime t+3C^\prime t^2+D^\prime t^3\right) \cdot 3\left(B^\prime+2C^\prime t+D^\prime t^2\right) +\left(P^\prime+3Q^\prime t+3R^\prime t^2+S^\prime t^3\right) \cdot 3\left(Q^\prime+2R^\prime t+S^\prime t^2\right) \\&=&3\left\{ \left(A^\prime+3B^\prime t+3C^\prime t^2+D^\prime t^3\right) \left(B^\prime+2C^\prime t+D^\prime t^2\right) +\left(P^\prime+3Q^\prime t+3R^\prime t^2+S^\prime t^3\right) \left(Q^\prime+2R^\prime t+S^\prime t^2\right) \right\} \\0&=&\left(A^\prime+3B^\prime t+3C^\prime t^2+D^\prime t^3\right) \left(B^\prime+2C^\prime t+D^\prime t^2\right) +\left(P^\prime+3Q^\prime t+3R^\prime t^2+S^\prime t^3\right) \left(Q^\prime+2R^\prime t+S^\prime t^2\right)\;\cdots\;両辺3で割った．左辺は0なので割っても変わらない． \\&=& A^\prime \left(B^\prime+2C^\prime t+D^\prime t^2\right) +3B^\prime t\left(B^\prime+2C^\prime t+D^\prime t^2\right) +3C^\prime t^2\left(B^\prime+2C^\prime t+D^\prime t^2\right) +D^\prime t^3\left(B^\prime+2C^\prime t+D^\prime t^2\right) \\&&+P^\prime \left(Q^\prime+2R^\prime t+S^\prime t^2\right) +3Q^\prime t\left(Q^\prime+2R^\prime t+S^\prime t^2\right) +3R^\prime t^2\left(Q^\prime+2R^\prime t+S^\prime t^2\right) +S^\prime t^3\left(Q^\prime+2R^\prime t+S^\prime t^2\right) \\&=& A^\prime B^\prime+2A^\prime C^\prime t+A^\prime D^\prime t^2 +3{B^{\prime}}^2 t+6B^\prime C^\prime t^2+3B^\prime D^\prime t^3 +3B^\prime C^\prime t^2+ 6{C^{\prime}}^2 t^3+ 3C^\prime D^\prime t^4 +B^\prime D^\prime t^3+2C^\prime D^\prime t^4+{D^{\prime}}^2 t^5 \\&& +P^\prime Q^\prime+2P^\prime R^\prime t+P^\prime S^\prime t^2 +3{Q^{\prime}}^2 t+6Q^\prime R^\prime t^2+3Q^\prime S^\prime t^3 +3Q^\prime R^\prime t^2+ 6{R^{\prime}}^2 t^3+ 3R^\prime S^\prime t^4 +Q^\prime S^\prime t^3+2R^\prime S^\prime t^4+{S^{\prime}}^2 t^5 \\&=& A^\prime B^\prime +\left(2A^\prime C^\prime+3{B^{\prime}}^2\right)t +\left(A^\prime D^\prime+9B^\prime C^\prime\right)t^2 +\left(4B^\prime D^\prime+ 6{C^{\prime}}^2 \right)t^3 +5C^\prime D^\prime t^4 +{D^{\prime}}^2 t^5 \\&& +P^\prime Q^\prime +\left(2P^\prime R^\prime+3{Q^{\prime}}^2\right)t +\left(P^\prime S^\prime+9Q^\prime R^\prime\right)t^2 +\left(4Q^\prime S^\prime+ 6{R^{\prime}}^2\right)t^3 +5R^\prime S^\prime t^4 +{S^{\prime}}^2 t^5 \\&=& A^{\prime\prime} +B^{\prime\prime}t +C^{\prime\prime}t^2 +D^{\prime\prime}t^3 +E^{\prime\prime}t^4 +F^{\prime\prime}t^5 \\&& +P^{\prime\prime} +Q^{\prime\prime}t +R^{\prime\prime}t^2 +S^{\prime\prime}t^3 +T^{\prime\prime}t^4 +U^{\prime\prime}t^5 \\&&\;\cdots\;A^{\prime\prime}=A^\prime B^\prime ,B^{\prime\prime}=2A^\prime C^\prime+3{B^{\prime}}^2 ,C^{\prime\prime}=A^\prime D^\prime+9B^\prime C^\prime ,D^{\prime\prime}=4B^\prime D^\prime+ 6{C^{\prime}}^2 ,E^{\prime\prime}=5C^\prime D^\prime ,F^{\prime\prime}={D^{\prime}}^2 \\&&\;\cdots\;P^{\prime\prime}=P^\prime Q^\prime ,Q^{\prime\prime}=2P^\prime R^\prime+3{Q^{\prime}}^2 ,R^{\prime\prime}=P^\prime S^\prime+9Q^\prime R^\prime ,S^{\prime\prime}=4Q^\prime S^\prime+ 6{R^{\prime}}^2 ,T^{\prime\prime}=5R^\prime S^\prime ,U^{\prime\prime}={S^{\prime}}^2 \\&=&\left(A^{\prime\prime}+P^{\prime\prime}\right) +\left(B^{\prime\prime}+Q^{\prime\prime}\right)t +\left(C^{\prime\prime}+R^{\prime\prime}\right)t^2 +\left(D^{\prime\prime}+S^{\prime\prime}\right)t^3 +\left(E^{\prime\prime}+T^{\prime\prime}\right)t^4 +\left(F^{\prime\prime}+U^{\prime\prime}\right)t^5 \\&=&\alpha_0+\alpha_1 t+\alpha_2 t^2+\alpha_3 t^3+\alpha_4 t^4+\alpha_5 t^5 \\&&\;\cdots\;\alpha_0=A^{\prime\prime}+P^{\prime\prime}=A^\prime B^\prime+P^\prime Q^\prime \\&&\;\cdots\;\alpha_1=B^{\prime\prime}+Q^{\prime\prime} =2A^\prime C^\prime+3{B^{\prime}}^2 +2P^\prime R^\prime+3{Q^{\prime}}^2 \\&&\;\cdots\;\alpha_2=C^{\prime\prime}+R^{\prime\prime} =A^\prime D^\prime+9B^\prime C^\prime+P^\prime S^\prime+9Q^\prime R^\prime \\&&\;\cdots\;\alpha_3=D^{\prime\prime}+S^{\prime\prime} =4B^\prime D^\prime+ 6{C^{\prime}}^2 +4Q^\prime S^\prime+ 6{R^{\prime}}^2 \\&&\;\cdots\;\alpha_4=E^{\prime\prime}+T^{\prime\prime} =5C^\prime D^\prime+5R^\prime S^\prime \\&&\;\cdots\;\alpha_5=F^{\prime\prime}+U^{\prime\prime}\ ={D^{\prime}}^2+{S^{\prime}}^2 \\\; \\&&\;\cdots\; A^\prime=a^\prime ,\;B^\prime=-a^\prime+b^\prime ,\;C^\prime=a^\prime-2b^\prime+c^\prime ,\;D^\prime=-a^\prime+3b^\prime-3c^\prime+d^\prime \\&&\;\cdots\; P^\prime=p^\prime ,\;Q^\prime=-p^\prime+q^\prime ,\;R^\prime=p^\prime-2q^\prime+r^\prime ,\;S^\prime=-p^\prime+3q^\prime-3r^\prime+s^\prime \\\; \\&&\;\cdots\;a^\prime=a-z_x,\;b^\prime=b-z_x,\;c^\prime=c-z_x,\;d^\prime=d-z_x \\&&\;\cdots\;p^\prime=p-z_y,\;q^\prime=q-z_y,\;r^\prime~r-z_y,\;s=s^\prime-z_y \end{eqnarray}$$
\(t\)を求めるには この5次方程式を解けばよいが，5次ということで数値計算で解く等が必要．
解は5つあるわけだが，その内実数であるものを選ぶ．
また，\(t\in[0, 1]\)であるので，\(t\lt0\)なら\(t=0\)，\(t\gt1\)なら\(t=1\)とする．
この式は任意点からBezier曲線上の各点へ引いた線分の中で，接線とが直角に交わる時の点を求める方程式に等しい．

最小となる\(L\)を求める

得られた\(t\)は\(L\)を極値とするものなので，その中でも\(L\)が最小となるものを採用する．