点序列插值

题

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

欢迎2D和3D解决方案。我们也非常感谢以任意粒度生成点列表的解决方案以及为贝塞尔曲线生成控制点的解决方案。

另外，看到一个迭代解决方案可以在接收到点时接近曲线的早期部分，这很酷，所以你可以用它绘制。

解决方案

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

这个由Christopher Twigg撰写的PDF 有一个很好地简要介绍了样条的数学。最好的总结句子是：

Catmull-Rom样条曲线有C1 连续性，本地控制和插值，但不要在于他们控制的凸壳分。

换句话说，如果这些点指示向右急转弯，则样条将向左转，然后向右转（在该文档中有一个示例图片）。这些转动的紧密性可以控制，在这种情况下使用示例矩阵中的tau参数。

以下是另一个示例，其中包含一些可下载的DirectX代码。

其他提示

一种方法是拉格朗日多项式，这是一种产生多项式的方法通过所有给定的数据点。

在大学的第一年，我写了一个小工具来做2D，你可以在此页面上找到它，它被称为拉格朗日解算器。维基百科的页面也有一个示例实现。

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

但是请注意，这可能不适合您的目的，因为它无法调整曲率等 - 您只能使用无法更改的单个解决方案。

您应该查看 B样条。它们优于贝塞尔曲线的优势在于每个部分仅依赖于局部点。因此，移动一个点对远离的曲线部分没有影响，其中<！>“远离<！>”;由样条曲线的参数确定。

Langrange多项式的问题在于，添加一个点会对看似任意曲线的部分产生极大的影响;没有<！> quot; localness <！> quot;如上所述。

你看过Unix spline 命令吗？可以强制做你想做的事吗？

有一些算法可以在aribtrary（但最终）点之间进行插值（和exrapolating）。您应该查看数字配方，它们还包括这些算法的C ++实现。

不幸的是，拉格朗日或其他形式的多项式插值不适用于任意一组点。它们仅适用于一维中的一组，例如X

x _i <！> lt; X <子> i + 1的

对于一组任意点，例如一个飞机飞行路径，每个点都是（经度，纬度）对，你最好用当前经度<！>放大器模拟飞机的旅程;纬度和速度。通过调整飞机转弯的速度（其角速度）取决于它与下一个航点的接近程度，您可以获得平滑的曲线。

得到的曲线在数学上不重要，也不会给你更好的控制点。然而，无论路点的数量如何，该算法在计算上都是简单的，并且可以以任意粒度产生内插的点列表。它也不需要你提前提供完整的点集，你可以根据需要简单地将路标添加到集合的末尾。

我想出了同样的问题，并且前几天与一些朋友实施了。我想在github上分享示例项目。

Google <！>“正交回归<！>”;

尽管最小二乘法技术试图使拟合线与每个f（x）之间的垂直距离最小化，但正交回归可以最小化垂直距离。

<强>附录

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

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

许可以下： CC-BY-SA 和归因