给定空间中任意点的序列，如何在它们之间产生平滑的连续插值？

欢迎使用2D和3D解决方案。还可以理解产生任意粒度的点列表的解决方案和产生贝塞尔曲线的控制点的解决方案。

同样，看到一个迭代的解决方案可以很酷，因为它可以在接收点时近似曲线的早期部分，因此我们可以使用它进行绘制。

解决方案

我们是否看过Unix spline命令？可以强迫这样做吗？

一种方法是拉格朗日多项式，这是一种生成将遍历所有给定数据点的多项式的方法。

在大学的第一年，我写了一个小工具来用2D进行此操作，我们可以在此页面上找到它，称为Lagrange求解器。维基百科的页面上也有一个示例实现。

因此它是如何工作的：我们有一个n阶多项式" p(x)"，其中n是我们拥有的点数。它的形式为" a_n x ^ n + a_(n-1)x ^(n-1)+ ... + a_0"，其中_是下标，^是幂。然后，将其转换为一组联立方程：

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

我们将上述内容转换为扩充矩阵，然后求解系数" a_0 ... a_n"。然后，我们拥有一个遍历所有点的多项式，现在可以在这些点之间进行插值。

但是请注意，这可能不适合目的，因为它无法调节曲率，因此我们只能使用无法更改的单一解决方案。

不幸的是，Lagrange或者其他形式的多项式插值将不适用于任意点集。它们只能在一个维度上工作的集合，例如X

xi <xi + 1

对于任意点集，例如如果飞机的飞行路径中的每个点都是一个(经度，纬度)对，那么使用当前的经度，纬度和速度对飞机的航程建模就更好了。通过根据飞机与下一个航路点的接近程度来调整飞机的转弯速率(其角速度)，我们可以获得平滑的曲线。

所得的曲线在数学上不会有任何意义，也不会给我们贝塞尔曲线的控制点。但是，无论航路点有多少，该算法在计算上都非常简单，并且可以以任意粒度生成一个插值点列表。它还不需要我们预先提供完整的点集，我们可以根据需要简单地将航点添加到该点集的末尾。

有几种算法可以在一个点集(但最终)的点集之间进行插值(和归零)。我们应该查看数字配方，它们还包括这些算法的C ++实现。

Google"正交回归"。

最小二乘技术试图使拟合线和每个f(x)之间的垂直距离最小，而正交回归则使垂直距离最小。

附录

在存在嘈杂数据的情况下，值得纪念的RANSAC算法也值得一试。

在3D图形世界中，NURBS很流行。进一步的信息很容易被谷歌搜索。

Catmull-Rom样条曲线可以保证通过所有控制点。我发现这比尝试为其他类型的样条曲线调整中间控制点更方便。

克里斯托弗·特维格(Christopher Twigg)撰写的PDF对花键的数学作了很好的简要介绍。最好的总结句是：

Catmull-Rom splines have C1
  continuity, local control, and
  interpolation, but do not lie within
  the convex hull of their control
  points.

换句话说，如果这些点指示向右弯曲，则样条线将在向右转向之前向左倾斜(该文档中有示例图片)。这些匝的紧密度是可控制的，在这种情况下，使用示例矩阵中的tau参数。

这是带有一些可下载的DirectX代码的另一个示例。

我们应该看一下B样条曲线。与贝塞尔曲线相比，它们的优势在于每个零件仅取决于局部点。因此，移动点对曲线的远处没有影响，在远处，"远处"由样条曲线的参数确定。

Langrange多项式的问题在于，添加一个点可能会对曲线上看似任意的部分产生极大的影响。没有如上所述的"局部性"。