3次ベジェ曲線の制御点を求める

はじめに

最初は、従来の棒グラフ形式のスペクトラム表示を滑らかな曲線で繋ぎたいと考えていました。「呼吸」するようなエフェクトの方がより自然に見えるからです。

以前、最小二乗法による曲線フィッティングを試しましたが、結論としては、最小二乗法ではこの問題を解決できません：

最小二乗法による曲線フィッティング：すべての散布点を均等に2つの部分に分けるような直線またはn次曲線、を求めることができます。
ベジェ曲線：各散布点を滑らかに通り抜ける曲線を求めることができます。

1. 問題の再定義

3次ベジェ曲線には2つの制御点が必要です（下図参照）：

[caption id="attachment_751" align="alignnone" width="360"] 3次ベジェ曲線[/caption]

（図中のP1, P2が制御点です）

Audio APIを通じて各散布点（スペクトラムの各バーの頂点）を取得できますが、難点は2つの制御点を求めることです。適当に決めてしまうと、効果は非常に悪くなります。

2. ソリューション

経験則に基づいたソリューションを見つけました。厳密な数学的根拠はありませんが、実際の効果は完璧です。具体的な手順は以下の通りです：

制御点が(x1,y1)と(x2,y2)の間にあると仮定します。最初の点と最後の点は、それぞれ曲線パス上の前の点と次の点です。
中点を求めます。
各中点を結ぶ線の長さを求めます。
中点を結ぶ線の長さの比率を求めます（平行移動前のp2, p3の位置を決定するために使用します）。
p2を平行移動させます。
p3を平行移動させます。
[オプション] 制御点と頂点の間の距離を微調整します。値が大きいほど曲線は平坦になります。

詳細については、Interpolation with Bezier Curves A very simple method of smoothing polygons をご覧ください。

滑らかな効果については、簡書：Android手書き最適化-より滑らかな署名効果の実現を参照してください。

3. JavaScriptで3次ベジェ曲線の制御点を求める

オリジナル版はJava実装ですが、筆者が簡単に修正・カプセル化しました。以下の通りです：

window.Bezier = {
    /**
     * 制御点の座標を取得
     * @param  {Array} arr 4つの点の座標配列
     * @param  {Float} smooth_value [0, 1] 滑らかさ
     *   p1 前の点
     *   p2 左端点
     *   P3 右端点
     *   p4 次の点
     * @return {Array}     2つの点の座標配列
     */
    getControlPoints: function(arr, smooth_value) {
        var x0 = arr[0].x, y0 = arr[0].y;
        var x1 = arr[1].x, y1 = arr[1].y;
        var x2 = arr[2].x, y2 = arr[2].y;
        var x3 = arr[3].x, y3 = arr[3].y;

        // Assume we need to calculate the control
        // points between (x1,y1) and (x2,y2).
        // Then x0,y0 - the previous vertex,
        //      x3,y3 - the next one.
        // 1. 制御点が(x1,y1)と(x2,y2)の間にあると仮定します。最初の点と最後の点は、それぞれ曲線パス上の前の点と次の点です。

        // 2. 中点を求める
        var xc1 = (x0 + x1) / 2.0;
        var yc1 = (y0 + y1) / 2.0;
        var xc2 = (x1 + x2) / 2.0;
        var yc2 = (y1 + y2) / 2.0;
        var xc3 = (x2 + x3) / 2.0;
        var yc3 = (y2 + y3) / 2.0;

        // 3. 各中点を結ぶ線の長さを求める
        var len1 = Math.sqrt((x1-x0) * (x1-x0) + (y1-y0) * (y1-y0));
        var len2 = Math.sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
        var len3 = Math.sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2));

        // 4. 中点を結ぶ線の長さの比率を求める（平行移動前のp2, p3の位置を決定するために使用）
        var k1 = len1 / (len1 + len2);
        var k2 = len2 / (len2 + len3);

        // 5. p2を平行移動
        var xm1 = xc1 + (xc2 - xc1) * k1;
        var ym1 = yc1 + (yc2 - yc1) * k1;

        // 6. p3を平行移動
        var xm2 = xc2 + (xc3 - xc2) * k2;
        var ym2 = yc2 + (yc3 - yc2) * k2;

        // Resulting control points. Here smooth_value is mentioned
        // above coefficient K whose value should be in range [0...1].
        // 7. 制御点と頂点の間の距離を微調整、大きいほど曲線は平坦になる
        var ctrl1_x = xm1 + (xc2 - xm1) * smooth_value + x1 - xm1;
        var ctrl1_y = ym1 + (yc2 - ym1) * smooth_value + y1 - ym1;

        var ctrl2_x = xm2 + (xc2 - xm2) * smooth_value + x2 - xm2;
        var ctrl2_y = ym2 + (yc2 - ym2) * smooth_value + y2 - ym2;

        return [{x: ctrl1_x, y: ctrl1_y}, {x: ctrl2_x, y: ctrl2_y}];
    }
};

コメントは十分に詳しく書いたつもりです。前述の Interpolation with Bezier Curves A very simple method of smoothing polygons と併せて理解を深めてください。

4. 効果のスクリーンショット

[caption id="attachment_752" align="alignnone" width="794"] ベジェ曲線の効果[/caption]

滑らかな効果が非常に良く、計算量も少ないため、リアルタイム描画のニーズを満たすことができます（元のプロジェクトはAndroidの手書き署名です）。

参考資料

gcacace/android-signaturepad：オリジナルプロジェクト