有限點位擬合光滑曲線：二次拋物線、B樣條與三次參數樣條 C++ 實現詳解

有限點位擬合光滑曲線：三大經典算法 C++ 實現詳解

在圖形學、CAD、數據可視化等領域，如何用有限離散點構造光滑曲線是核心課題。本文深度解析三種經典插值算法——二次拋物線法、二次 B樣條法、三次參數樣條法——並提供可直接移植的 C++ 參考實現，助你根據精度與性能需求選型。

算法對比速覽

1. 二次拋物線法

原理：以四個鄰近控制點構造一段三次參數曲線，通過端點處的虛擬點複製（p[0]=p[1], p[n+1]=p[n]）處理邊界。參數 t ∈ [0, 0.5]，步長 0.5/k，每段插入 k-1 個點。

基函數：

a = 4t² - t - 4t³
b = 1 - 10t² + 12t³
c = t + 8t² - 12t³
d = 4t³ - 2t²

關鍵代碼片段：

void paowuxian(int *x, int *y, int n, unsigned int k) {
    // 邊界虛擬點
    *x = *(x+1); *y = *(y+1);
    *(x+n+1) = *(x+n); *(y+n+1) = *(y+n);

    float t = 0.5f / k;
    moveto(*(x+1), *(y+1));
    for (int i = 0; i < n-1; ++i) {
        for (int j = 1; j < k; ++j) {
            float t1 = j * t, t2 = t1*t1, t3 = t2*t1;
            float a = 4*t2 - t1 - 4*t3;
            float b = 1 - 10*t2 + 12*t3;
            float c = t1 + 8*t2 - 12*t3;
            float d = 4*t3 - 2*t2;
            float tx = a*x[i] + b*x[i+1] + c*x[i+2] + d*x[i+3];
            float ty = a*y[i] + b*y[i+1] + c*y[i+2] + d*y[i+3];
            lineto(tx, ty);
        }
    }
    lineto(*(x+n), *(y+n));  // 收尾
}

2. 二次 B樣條法

原理：均勻二次 B樣條，每段由三個控制點決定，具備局部修改特性。曲線不經過控制點，但逼近控制多邊形。起點取前兩點中點，參數 t ∈ [0, 1]，步長 1/k。

基函數：

a = (t² - 2t + 1) / 2
b = t - t² + 0.5
c = t² / 2

關鍵代碼片段：

void byangtiao(int *x, int *y, int n, unsigned int k) {
    *x = *(x+1); *y = *(y+1);
    *(x+n+1) = *(x+n); *(y+n+1) = *(y+n);

    float t = 1.0f / k;
    moveto((x[0]+x[1])/2.0f, (y[0]+y[1])/2.0f);
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j < k; ++j) {
            float t1 = j * t, t2 = t1*t1;
            float a = (t2 - 2*t1 + 1) * 0.5f;
            float b = t1 - t2 + 0.5f;
            float c = t2 * 0.5f;
            float tx = a*x[i] + b*x[i+1] + c*x[i+2];
            float ty = a*y[i] + b*y[i+1] + c*y[i+2];
            lineto(tx, ty);
        }
    }
}

3. 三次參數樣條法

原理：作者註釋「好像叫三次參數樣條法」，實為三次 Cardinal Spline / Catmull-Rom 變體。同樣使用四點支撐，但參數域 t ∈ [0, 0.5]，基函數與二次拋物線法完全一致，僅數據結構改為 int p[][2] 並額外增加 D 偏移量（可能用於多曲線疊加）。

關鍵差異：

• 輸入為二維陣列 p[n+2][2]，便於向量化運算
• moveto(p[1][0], p[1][1]+D) 引入垂直偏移
• lineto(x, y, 15) 攜帶顏色/屬性參數

工程落地建議

1. 邊界處理：三種算法均採用「端點複製」法，簡單但可能產生邊界彎曲；生產環境建議改用「鏡像延拓」或「自然樣條」邊界條件。
2. 參數化改進：採用 弦長參數化 或 百度參數化 替代等距參數，可顯著改善點分布不均時的曲線質量。
3. 數值穩定性：單精度 float 足夠屏幕繪圖；科學計算建議升級 double 並引入 Eigen / GLM 矩陣庫。
4. 現代化重構：將算法封裝為 CurveFitter 抽象基類，派生 QuadraticParabolic、QuadraticBSpline、CubicParametricSpline，配合 std::vector<Point2f> 與範基 for 循環，消除裸指針與手動索引。

掌握這三種算法的數學本質與代碼結構，你就能在「精度、速度、局部控制」三角權衡中做出最佳選擇，並輕鬆擴展至 NURBS、Subdivision 等高階曲線表示。