求三次貝茲曲線的控制點

寫在前面

最初是想要把傳統的長條頻譜圖做成平滑曲線連接的，「呼吸」效果應該會更自然

之前試過了最小平方法曲線擬合，結論是最小平方法曲線擬合不能解決這個問題：

最小平方法曲線擬合：可以求出一條直線/n 次曲線，把所有散點均勻地分為兩部分
貝茲曲線：可以求出一條曲線平滑穿過各個散點

一. 問題重述

三次貝茲曲線需要 2 個控制點，如下圖：

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

（圖中的 P1, P2 是控制點）

透過 Audio API 可以獲取各個散點（長條頻譜圖的各個柱子的頂端），而難點就是求 2 個控制點，隨便定是肯定不行的，效果會非常差

二. 解決方案

找到了一個基於經驗實踐的解決方案，沒有嚴格的數學依據，但實際效果很完美，具體步驟如下：

假設控制點在 (x1,y1) 和 (x2,y2) 之間，第一個點和最後一個點分別是曲線路徑上的上一個點和下一個點
求中點
求各中點連線長度
求中點連線長度比例（用來確定平移前 p2, p3 的位置）
平移 p2
平移 p3
[可選]微調控制點與頂點之間的距離，越大曲線越平直

平滑的效果可以看簡書：Android 手寫優化-更為平滑的簽名效果實現

三. JavaScript 求三次貝茲曲線的控制點

原版是 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)之间，第一个点和最后一个点分别是曲线路径上的上一个点 and 下一个点

        // 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 理解

四. 效果截圖

[caption id="attachment_752" align="alignnone" width="794"] 貝茲曲線效果[/caption]

平滑效果很不錯，而且計算量小，能夠滿足即時繪圖的需要（原專案是 Android 手寫簽名）

參考資料

gcacace/android-signaturepad：原專案