ベジェ曲線の長さを求める

背景

趣味でアプリを作ってるときにベジェ曲線の長さが必要になりました．ベジェ曲線用のクラスは用意されているものの，長さは自分で計算する必要がありました．色々調べたので記事にまとめることにします．この記事はこのページを参考に執筆しました．

ベジェ曲線とは

CGの分野で曲線はベジェ曲線を用いて表されることが多いです．

イラレのペンツールで書ける曲線はベジェ曲線です．

下のページではベジェ曲線がわかりやすく紹介されています．解説用のアニメーションが非常にわかりやすいです．

postd.cc

ベジェ曲線の数学的表現

3次ベジェ曲線上の点を媒介変数 $t, 0 \leq t \leq 1$ を用いて $P(t)$ と表すことにします．
このときの始点，制御点１，制御点２，終点を $P_0, P_1, P_2, P_3$ とすれば， $P(t) = (1-t)^3P_0 + 3t(1-t)^2 P_1 + 3t^2(1-t) P_2 + t^3 P_3$ と書けます．

各点の $x$ 座標， $y$ 座標を $P(t).x$ ， $P(t).y$ と書くことにします．構造体のイメージです．

このあとの計算のために $P(t)$ のかっこを展開して $t$ の次数で整理しておきます．係数を $A, B,C,D$ とすれば，

\begin{align}P(t) &= (-P_0+3P_1-3P_2+P_3)t^3 + (3P_0-6P_1+3P_2)t^2 + (-3P_0 + 3P_1)t + (P_0) \\ &= At^3 + Bt^2 + Ct + D \end{align}

となります．

ここで注意してほしいのは，この関数は $x$ ， $y$ についてそれぞれ成り立っています．すなわち，

$P(t).x = (A.x)t^3 + (B.x)t^2 + (C.x)t + D.x$

$P(t).y = (A.y)t^3 + (B.y)t^2 + (C.y)t + D.y$

ということです．

曲線の長さの求め方

一般に，曲線が媒介変数 $t$ で $x = f(t), y = g(t)$ とと表現されているとき，区間 $\alpha \leq t \leq \beta$ の曲線の長さは

$\displaystyle{ L = \int_{\alpha}^{\beta} \sqrt{\left( \frac{dx}{dt} \right)^2 + \left(\frac{dy}{dt} \right)^2} dt }$

で求められます．

先のベジェ曲線にあてはめれば，

$\displaystyle{ \frac{dx}{dt} = \frac{d}{dt}P(t).x }$

$\displaystyle{ \frac{dy}{dt} = \frac{d}{dt}P(t).y }$

です．

まずは $\displaystyle{ \frac{dx}{dt}}$ と $\displaystyle{ \frac{dy}{dt} }$ を求めるために $P(t)$ を微分してみます．

$\displaystyle{ \frac{d}{dt}P(t) = 3At^2 + 2Bt + C }$

これを２乗すると，

$\displaystyle{ \left( \frac{d}{dt}P(t) \right)^2 = 9At^4 + 12ABt^3 + (6AC + 4B^2)t^2 + 4BCt + C}$

求めたいベジェ曲線の長さを $L$ とすると，

\begin{align} L &= \int_{0}^{1} \sqrt{\left( \frac{dx}{dt} \right)^2 + \left(\frac{dy}{dt} \right)^2} dt. \\ &= \int_{0}^{1} \sqrt{\left( \frac{d}{dt}P(t).x \right)^2 + \left(\frac{d}{dt}P(t).y \right)^2} dt \\ &= \int_{0}^{1} \sqrt{(9(A.x)t^4 +...) + (9(A.y)t^4 + ...)} dt \end{align}

原始関数を求めるのは難しそうです．

であるならば近似解を求める作戦でいきましょう．

この分野には疎いのですが，調べてみたかんじでは数値積分とか数値解析がキーワードのようです．

今回はオイラー法とルンゲクッタ法，シンプソン法を試しました．

ルンゲクッタ法のなかでも４次ルンゲクッタ法と３次ルンゲクッタ法を試しました．

後でわかったことだが，オイラー法とルンゲクッタ法は常微分方程式の近似解を求める手法でした．

Python + matplotlibでベジェ曲線を描く

普段から使い慣れてるPythonでまずはベジェ曲線を描いてみる．

matplotlibの機能だけではベジェ曲線が描けなかったのでモジュールを追加した．

pypi.org

pipでインストールできます．

始点，制御点１，制御点２，終点が

\begin{align*}P_0 &= (0.0,0.0)\\P_1& = (0.5, 3.0)\\ P_2 &= (10.0, -2.0)\\P_3& = (12.0, 4.0)\end{align*}

であるときの３次ベジェ曲線がこちらです．

f:id:ryosukeeeee:20181201190234j:plain

手法を比較する

手法を比較・評価するときの基準となる"正解"を決めましょう．

自分なりに考えた結果，ベジェ曲線を細かく区切り，その極小区間を直線で近似して三平方の定理で長さを求め，その和を"正解"としました．

シンプソン法（Simpson's rule），オイラー法（Euler method），３次ルンゲクッタ法（3rd-order Runge-Kutta method），４次ルンゲクッタ法（4th-order Runge-Kutta method）を，分割数を10から100まで5ずつ増やして比較してみました．

f:id:ryosukeeeee:20181201190232j:plain