最小平方距离将三次贝塞尔曲线拟合到一组点的算法

Question

有一些关于将贝塞尔曲线拟合到数据的已回答的问题，但我正在寻找一种算法而不是现成的解决方案。我可以根据其他要求实现一些东西。

输入：一小组二维数据点，十几个左右；预定义的贝塞尔曲线端点。

输出：具有指定端点的平面三次贝塞尔曲线，可最小化到数据点的均方距离。

我的想法：计算数据点到参数化贝塞尔曲线的平方距离；对参数 t 求导；计算导数为 0 时的距离；将所有数据点相加；对自由控制点求导数；优化一下。

问题所在：当您计算从一个点到三次贝塞尔曲线的平方距离的导数时，您会得到一个五次方程。对此没有解析解，因此您必须进行牛顿-拉夫森迭代才能获得数值解。因此，当您将到所有数据点的距离相加并优化自由贝塞尔控制点时，您必须使用无梯度算法进行数值优化，这往往很慢。这是可行的，但会花费更多必要的计算时间。使运行时问题变得更糟的是，该问题需要解决数百万条贝塞尔曲线，每条曲线都拟合十几个自己的数据点。如果每个贝塞尔曲线都需要围绕另一个数值优化进行数值优化，这将使解决方案慢得令人无法接受。

因此，我正在寻找一种相当快、最好是解析贝塞尔曲线拟合的解决方案。如果不可能找到精确的解，那么可以使用相当快的数值解。

Answer 1

简单的方法。只需使用梯度下降来求解控制点，同时也求解最近点的位置。

你得到了

start_point, end_point, data_points

。对

c1, c2, t

提出一些半合理的猜测，其中

c1

和

c2

是控制点，

t[i]

是贝塞尔曲线上与

data_points[i]

相当接近的点的参数。现在使用梯度下降来最小化误差平方和。