点序列插值

Question

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

欢迎使用2D和3D解决方案。产生任意粒度点列表的解决方案以及为贝塞尔曲线生成控制点的解决方案也值得赞赏。

此外，看到一个迭代解决方案可以接近曲线的早期部分，因为它可以接收点，所以可以用它来绘制。

Answer 1

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

这PDF by Christopher Twigg有一个很好的简要介绍了样条的数学。最好的总结一句话就是：

的Catmull-ROM花键具有C1 连续性，局部控制和 插值，但没有在 处于其控制 点的凸包。

换一种说法，如果点表示向右急转弯，则样条线在向右转弯之前会左转（在该文档中有一个示例图片）。在这种情况下，在示例矩阵中使用他的tau参数可控制这些转弯的紧密程度。

这里是another example与一些可下载的DirectX代码。

Answer 2

你看过Unix spline命令吗？这可以被迫做你想做的事吗？

Answer 3

一种方法是Lagrange polynominal，这是一种产生将经过所有给定数据点的多项式的方法。

在我大学的第一年，我写了一个小工具来做到这一点在二维，你可以find it on this page，它被称为拉格朗日求解器。维基百科的页面也有一个示例实现。

工作原理是这样的：您有一个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。然后你有一个遍历所有点的多项式，现在你可以在这些点之间进行插值。

但请注意，这可能不适合您的目的，因为它不提供调整曲率等的方法 - 您无法改变一个解决方案。

Answer 4

不幸的是，拉格朗日或其他形式的多项式插值不适用于任意一组点。他们只能在一个维度上工作X

X _我 < X _{i + 1的}

对于arbitary点的集合，例如一个飞机飞行路径，其中每个点都是（经度，纬度）对，您最好使用当前经度纬度和速度对飞机旅程进行建模。通过调整飞机可以转弯的速度（角速度），取决于它与下一个航点的距离，您可以获得平滑的曲线。

由此产生的曲线不会在数学上显着，也不会给你更多的控制点。然而，不管路点的数量如何，该算法在计算上都是简单的，并且可以产生任意粒度的内插点列表。它也不要求您提前提供完整的一组点，您可以根据需要简单地将航点添加到该集的末尾。

Answer 5

有几种算法用于在一组点之间进行插值（和外插）。你应该检查出numerical recipes，它们还包括那些算法的C++实现。

Answer 6

谷歌“正交回归”。

鉴于最小二乘技术试图尽量减少拟合线和每个f（x）之间的垂直距离，正交回归最小化垂直距离。

补遗

在嘈杂数据的存在，古老RANSAC算法是值得检查过。

Answer 7

在3D图形世界中，NURBS很受欢迎。更多信息很容易搜索到。

Answer 8

你应该看看B-splines。它们比贝塞尔曲线的优势在于每个部分仅依赖于局部点。因此，移动一个点对远离曲线的部分没有影响，“远处”由样条曲线的参数决定。

Langrange多项式的问题是添加一个点可能会对曲线上看起来任意的部分产生极端影响;没有像上面描述的“地方性”。

Answer 9

我想出了同样的问题，并在前些日子与一些朋友一起实施。我喜欢在github上分享示例项目。

https://github.com/johnjohndoe/PathInterpolation
随意叉它。