如何将贝塞尔曲线拟合到一组数据？

Question

我有一组数据点（我可以把它们简化一下），需要用一个贝塞尔曲线来拟合。我的目标是速度比准确度更重要，但拟合的效果要足够好，让人能看得出来。我还希望找到一个算法，尽量少用库（特别是NumPy）。

我看过几篇研究论文，但没有一篇提供足够的细节让我能完全实现。有开源的例子吗？

Answer 1

如果大部分数据都符合你的模型，你可以试试 RANSAC 这个方法。你可以随机选取4个点，然后用这些点来拟合一条贝塞尔曲线。至于要把这条曲线和其他所有点进行比较需要花费多少时间，我现在不太确定（这是RANSAC算法的一部分）。不过，这个过程是线性的，也就是说它的效率还不错，而且RANSAC的实现起来很简单（网上可能还有开源的算法可以用）。

Answer 2

很多回答中缺少的一点是，你可能不想只用一条三次贝塞尔曲线来拟合你的数据。更一般来说，你可能希望用一系列的三次贝塞尔曲线，也就是分段的三次贝塞尔拟合，来处理任意的数据集。

有一篇很不错的论文，早在1995年就写好了，里面还有MATLAB的代码，可以实现这个功能：

% Lane, Edward J. Fitting Data Using Piecewise G1 Cubic Bezier Curves.
% Thesis, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, 1995

http://www.dtic.mil/dtic/tr/fulltext/u2/a298091.pdf

要使用这个方法，至少需要指定节点点的数量，也就是优化程序用来进行拟合的数据点数量。你还可以选择具体的节点点，这样可以提高拟合的可靠性。论文中展示了一些比较复杂的例子。需要注意的是，Lane的方法保证了三次贝塞尔段之间的G1连续性（相邻切线向量的方向是相同的），也就是说连接处是光滑的。不过，曲率上可能会有不连续性（即二阶导数的方向变化）。

我已经重新实现了这段代码，并更新到了现代的MATLAB版本（R2015b）。如果你需要，可以联系我。

下面是一个例子，使用了三个节点点（由代码自动选择），拟合了两个三次贝塞尔段到一个Lissajous图形上。

Answer 3

我遇到了类似的问题，发现了一篇来自《Graphics Gems》（1990年）的文章，里面讲的是如何自动拟合数字曲线，特别是贝塞尔曲线的拟合。

此外，我还找到了这篇文章的源代码。

可惜的是，这段代码是用C语言写的，而我对C语言不太熟悉。而且，这个算法对我来说也比较难懂。我正在尝试把它翻译成C#代码。如果成功了，我会分享出来。

在和FitCurves.c同一个文件夹里的GGVecLib.c文件包含了一些基本的向量操作函数。

我还发现了一个类似的Stack Overflow问题，平滑手绘曲线。这个问题的认可回答提供了一个来自《Graphics Gems》的曲线拟合算法的C#代码。