C# 一种简单的贝塞尔拟合算法

前两天实现了一项功能,在一端进行书写,在另一端还原笔迹。由于两端的开发平台和绘图引擎不一致,书写端的笔迹很平滑,而另一端还原出来的笔迹为折线。为了使两端保持一致的效果,需要在还原端对笔迹进行贝塞尔拟合。本文将首先介绍贝塞尔曲线的基本原理及公式推导,然后提出一种简单的二次贝塞尔近似拟合算法,并用 C# 编程实现之。
C# 一种简单的贝塞尔拟合算法-LMLPHP
C# 一种简单的贝塞尔拟合算法-LMLPHP

贝塞尔曲线

相信大家都或多或少了解过贝塞尔曲线,此处就不再赘述,仅仅介绍其原理及推导。

C# 一种简单的贝塞尔拟合算法-LMLPHP

如上图所示,对于平面上的两个点 P0 和 P1,假设另一点 B 匀速地从 P0 点运动到 P1 点,则有 B 点在 t 时刻的坐标公式:

C# 一种简单的贝塞尔拟合算法-LMLPHP

将 B 点在各个时刻的坐标依次连接起来所形成的线,就是所谓的贝塞尔曲线。此公式表示的是一次贝塞尔曲线,也称为线性贝塞尔曲线。

二次贝塞尔曲线

C# 一种简单的贝塞尔拟合算法-LMLPHP

同样地,对于平面上的三个点 P0、P1 和 P2 ,假设 P0P1 之间有个点 B1 匀速地从 P0 运动到 P1 ,P1P2 之间有个点 B2 匀速地从 P1 运动到 P2,则有:

C# 一种简单的贝塞尔拟合算法-LMLPHP
C# 一种简单的贝塞尔拟合算法-LMLPHP

假设另一点 B 匀速地从 B1 运动到 B2,则有 B 点的坐标公式:

C# 一种简单的贝塞尔拟合算法-LMLPHP

将 B1 和 B2 的坐标公式代入上面的表达式,整理后得到 B 点的坐标公式:

C# 一种简单的贝塞尔拟合算法-LMLPHP

B 点在各个时刻的坐标所连成的曲线即为二次贝塞尔曲线,其中 P0 和 P2 称为 数据点,P1 称为 控制点

简单的二次拟合算法

C# 一种简单的贝塞尔拟合算法-LMLPHP

有了上面的基本原理的理解,我们回到问题的解决。对于较为稀疏的三个点 P1、P2 和 P3,如果直接顺次相连,会呈现出折线,所以需要进行贝塞尔插值,使其平滑。如果按照标准的贝塞尔曲线算法,P1 和 P2 应该为数据点,并且需要为这两个数据点寻找控制点。但是此处采用了近似的拟合算法,首先计算出 P2 和 P3 的中点,并以此点和 P1 点为数据点,然后以 P2 点为控制点,由此来确定一条二次贝塞尔曲线。虽然最终生成的贝塞尔曲线未能通过所有的真实数据点,但是整条曲线的形态能和另一端保持一致,并且位置也不会存在较大偏差。

/// <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);
}

效果图

C# 一种简单的贝塞尔拟合算法-LMLPHP
C# 一种简单的贝塞尔拟合算法-LMLPHP

附:高次贝塞尔曲线

下面展示一些高阶贝塞尔曲线的原理图和公式,此处不做推导,感兴趣的可以参照上面的二次曲线的推导方法自行演算。

  • 三次贝塞尔曲线

C# 一种简单的贝塞尔拟合算法-LMLPHP
C# 一种简单的贝塞尔拟合算法-LMLPHP

  • 四次贝塞尔曲线

C# 一种简单的贝塞尔拟合算法-LMLPHP

  • 五次贝塞尔曲线

C# 一种简单的贝塞尔拟合算法-LMLPHP

参考资料

10-06 10:32