一種簡單的貝塞爾擬合算法

mediatv 2021-12-06

展開全文

前兩天實現了一項功能，在一端進行書寫，在另一端還原筆跡。由于兩端的開發(fā)平臺和繪圖引擎不一致，書寫端的筆跡很平滑，而另一端還原出來的筆跡為折線。為了使兩端保持一致的效果，需要在還原端對筆跡進行貝塞爾擬合。本文將首先介紹貝塞爾曲線的基本原理及公式推導，然后提出一種簡單的二次貝塞爾近似擬合算法，并用 C# 編程實現之。

貝塞爾曲線

相信大家都或多或少了解過貝塞爾曲線，此處就不再贅述，僅僅介紹其原理及推導。

如上圖所示，對于平面上的兩個點 P0 和 P1，假設另一點 B 勻速地從 P0 點運動到 P1 點，則有 B 點在 t 時刻的坐標公式：

將 B 點在各個時刻的坐標依次連接起來所形成的線，就是所謂的貝塞爾曲線。此公式表示的是一次貝塞爾曲線，也稱為線性貝塞爾曲線。

二次貝塞爾曲線

同樣地，對于平面上的三個點 P0、P1 和 P2 ，假設 P0P1 之間有個點 B1 勻速地從 P0 運動到 P1 ，P1P2 之間有個點 B2 勻速地從 P1 運動到 P2，則有：

假設另一點 B 勻速地從 B1 運動到 B2，則有 B 點的坐標公式：

將 B1 和 B2 的坐標公式代入上面的表達式，整理后得到 B 點的坐標公式：

B 點在各個時刻的坐標所連成的曲線即為二次貝塞爾曲線，其中 P0 和 P2 稱為 數據點，P1 稱為 控制點 。

簡單的二次擬合算法

有了上面的基本原理的理解，我們回到問題的解決。對于較為稀疏的三個點 P1、P2 和 P3，如果直接順次相連，會呈現出折線，所以需要進行貝塞爾插值，使其平滑。如果按照標準的貝塞爾曲線算法，P1 和 P2 應該為數據點，并且需要為這兩個數據點尋找控制點。但是此處采用了近似的擬合算法，首先計算出 P2 和 P3 的中點，并以此點和 P1 點為數據點，然后以 P2 點為控制點，由此來確定一條二次貝塞爾曲線。雖然最終生成的貝塞爾曲線未能通過所有的真實數據點，但是整條曲線的形態(tài)能和另一端保持一致，并且位置也不會存在較大偏差。

/// <summary>
/// 計算兩點之間的二次貝塞爾曲線點集。
/// </summary>
private IList<Point> CalculateBezierPoints(Point begin, Point handle, Point end)
{
    // 根據兩點之間的距離來確定曲線上的點數，進而確定 t 的步長（步長越小，精度越高）
    var bx = begin.X;
    var by = begin.Y;
    var ex = end.X;
    var ey = end.Y;
    var hx = handle.X;
    var hy = handle.Y;

    var bhDis = Math.Sqrt((bx - hx) * (bx - hx) + (by - hy) * (by - hy));
    var ehDis = Math.Sqrt((ex - hx) * (ex - hx) + (ey - hy) * (ey - hy));

    var distance = bhDis + ehDis;
    var count = distance / 40;

    if (count < 2)
    {
        count = 2;
    }

    // 確定步長，并計算曲線上的點集
    var step = 1.0 / count;
    var points = new List<Point>();

    var t = 0.0; // t∈[0,1]
    for (var i = 0; i < count; i++)
    {
        points.Add(GetBezierPointByT(begin, handle, end, t));
        t += step;
    }

    return points;
}

/// <summary>
/// 根據二次貝塞爾曲線的公式，計算各個時刻的坐標值。
/// </summary>
private Point GetBezierPointByT(Point begin, Point handle, Point end, double t)
{
    var pow = Math.Pow(1 - t, 2);

    // B = (1-t)^2*P0 + 2t(1-t)P1 + t^2*P2 , t∈[0,1]
    var x = pow * begin.X + 2 * t * (1 - t) * handle.X + t * t * end.X;
    var y = pow * begin.Y + 2 * t * (1 - t) * handle.Y + t * t * end.Y;

    return new Point(x, y);
}

private void Usage()
{
    var start = point1;
    var end = new Point((point2.X + point3.X) / 2, (point2.Y + point3.Y) / 2);
    
    var points = CalculateBezierPoints(start, point2, end);
}