math - 点序列插值

Question

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

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

此外，看到一个迭代解决方案可以在接收点时近似曲线的早期部分，这将是很酷的，因此您可以使用它进行绘制。

score 9 · Accepted Answer

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

Christopher Twigg的这个PDF对样条的数学进行了很好的简要介绍。最好的总结句是：

Catmull-Rom 样条具有 C1 连续性、局部控制和插值，但不位于其控制点的凸包内。

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

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

score 3 · Accepted Answer

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

在我大学的第一年，我写了一个小工具来做这个 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。然后你有一个通过所有点的多项式，你现在可以在点之间进行插值。

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

score 2 · Accepted Answer

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

朗朗日多项式的问题在于，添加一个点会对曲线的看似任意部分产生极端影响。没有如上所述的“本地性”。

score 1 · Accepted Answer

1

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

于 2008-09-20T08:34:02.193 回答

score 1 · Accepted Answer

不幸的是，拉格朗日或其他形式的多项式插值不适用于任意一组点。它们只适用于一个维度的集合，例如 x

x _i < x _i+1

对于任意一组点，例如飞机飞行路径，其中每个点都是（经度，纬度）对，您最好简单地使用当前经度和纬度以及速度对飞机的旅程进行建模。通过根据飞机与下一个航路点的距离来调整飞机可以转弯的速度（角速度），您可以获得平滑的曲线。

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

score 1 · Accepted Answer

有几种算法可以在任意（但最终的）点集之间进行插值（和推断）。您应该查看数值配方，它们还包括这些算法的 C++ 实现。

score 1 · Accepted Answer

我想出了同样的问题，并在前几天和一些朋友一起实现了它。我喜欢在 github 上分享示例项目。

路径插值截图

score 0 · Accepted Answer

谷歌“正交回归”。

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

附录

在存在噪声数据的情况下，古老的RANSAC算法也值得一试。

score 0 · Accepted Answer

0

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

于 2008-09-24T02:15:13.053 回答

9 回答 9