点序列插值
给定空间中的任意点序列，如何在它们之间产生平滑的连续插值？
欢迎 2D 和 3D 解决方案。 生成任意粒度的点列表的解决方案以及生成贝塞尔曲线控制点的解决方案也受到赞赏。
另外，如果能看到一个迭代解决方案，可以在收到点时逼近曲线的早期部分，那就很酷了，这样您就可以用它来绘图。
Given an arbitrary sequence of points in space, how would you produce a smooth continuous interpolation between them?
2D and 3D solutions are welcome. Solutions that produce a list of points at arbitrary granularity and solutions that produce control points for bezier curves are also appreciated.
Also, it would be cool to see an iterative solution that could approximate early sections of the curve as it received the points, so you could draw with it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
Catmull-Rom 样条 保证通过所有控制点。 我发现这比尝试调整其他类型样条线的中间控制点更方便。
这个 Christopher Twigg 的 PDF 有一个很好的简短介绍到样条曲线的数学。 最好的概括句子是：
换句话说，如果这些点指示向右急剧弯曲，则样条线将在转向右侧之前向左倾斜（该文档中有一个示例图片）。 这些匝数的紧密度是可控的，在本例中使用示例矩阵中的 tau 参数。
这是另一个示例，其中包含一些可下载的 DirectX 代码。
The Catmull-Rom spline is guaranteed to pass through all the control points. I find this to be handier than trying to adjust intermediate control points for other types of splines.
This PDF by Christopher Twigg has a nice brief introduction to the mathematics of the spline. The best summary sentence is:
Said another way, if the points indicate a sharp bend to the right, the spline will bank left before turning to the right (there's an example picture in that document). The tightness of those turns in controllable, in this case using his tau parameter in the example matrix.
Here is another example with some downloadable DirectX code.
一种方法是拉格朗日多项式，这是一种生成多项式的方法，该多项式将遍历所有给定的数据点。
在大学第一年，我编写了一个小工具来以 2D 方式执行此操作，您可以找到在这个页面上，它被称为拉格朗日求解器。 维基百科的页面也有一个示例实现。
它的工作原理是这样的：你有一个 n 阶多项式，
p(x)，其中 n 是你拥有的点数。 它的形式为a_n x^n + a_(n-1) x^(n-1) + ...+ a_0，其中_是下标，^是力量。 然后将其转换为一组联立方程：将以上方程转换为增广矩阵，并求解系数
a_0 ... a_n。 然后你就有了一个遍历所有点的多项式，现在你可以在这些点之间进行插值。但请注意，这可能不适合您的目的，因为它无法提供调整曲率等的方法 - 您只能使用无法更改的单一解决方案。
One way is Lagrange polynominal, which is a method for producing a polynominal which will go through all given data points.
During my first year at university, I wrote a little tool to do this in 2D, and you can find it on this page, it is called Lagrange solver. Wikipedia's page also has a sample implementation.
How it works is thus: you have a n-order polynominal,
p(x), where n is the number of points you have. It has the forma_n x^n + a_(n-1) x^(n-1) + ...+ a_0, where_is subscript,^is power. You then turn this into a set of simultaneous equations:You convert the above into a augmented matrix, and solve for the coefficients
a_0 ... a_n. Then you have a polynomial which goes through all the points, and you can now interpolate between the points.Note however, this may not suit your purpose as it offers no way to adjust the curvature etc - you are stuck with a single solution that can not be changed.
您应该查看B-splines。 与贝塞尔曲线相比，它们的优势在于每个部分仅依赖于局部点。 因此，移动点对曲线中较远的部分没有影响，其中“较远”由样条线的参数确定。
朗朗日多项式的问题在于，添加一个点可能会对曲线上看似任意的部分产生极端影响； 不存在如上所述的“本地性”。
You should take a look at B-splines. Their advantage over Bezier curves is that each part is only dependent on local points. So moving a point has no effect on parts of the curve that are far away, where "far away" is determined by a parameter of the spline.
The problem with the Langrange polynomial is that adding a point can have extreme effects on seemingly arbitrary parts of the curve; there's no "localness" like described above.
你看过 Unix spline 命令吗？ 可以强迫你做你想做的事吗？
Have you looked at the Unix spline command? Can that be coerced into doing what you want?
有几种算法可以在任意（但最终的）点集之间进行插值（和外推）。 您应该查看数值食谱，它们还包括这些算法的 C++ 实现。
There are several algorithms for interpolating (and exrapolating) between an aribtrary (but final) set of points. You should check out numerical recipes, they also include C++ implementations of those algorithms.
不幸的是，拉格朗日或其他形式的多项式插值法不适用于任意一组点。 它们仅适用于一个维度的集合，例如 x
xi < xi+1
对于任意一组点，例如飞机飞行路径，其中每个点都是（经度，纬度）对，您最好简单地用当前经度和纬度对飞机的旅程进行建模; 纬度和速度。 通过根据飞机与下一个航路点的距离来调整飞机转弯的速率（角速度），您可以实现平滑的曲线。
生成的曲线在数学上没有意义，也不会为您提供贝塞尔曲线控制点。 然而，无论航路点的数量如何，该算法在计算上都很简单，并且可以产生任意粒度的插值点列表。 它也不需要您预先提供完整的点集，您可以根据需要简单地将航路点添加到该组的末尾。
Unfortunately the Lagrange or other forms of polynomial interpolation will not work on an arbitrary set of points. They only work on a set where in one dimension e.g. x
xi < xi+1
For an arbitary set of points, e.g. an aeroplane flight path, where each point is a (longitude, latitude) pair, you will be better off simply modelling the aeroplane's journey with current longitude & latitude and velocity. By adjusting the rate at which the aeroplane can turn (its angular velocity) depending on how close it is to the next waypoint, you can achieve a smooth curve.
The resulting curve would not be mathematically significant nor give you bezier control points. However the algorithm would be computationally simple regardless of the number of waypoints and could produce an interpolated list of points at arbitrary granularity. It would also not require you provide the complete set of points up front, you could simply add waypoints to the end of the set as required.
前几天我也遇到了同样的问题，并和一些朋友一起实现了它。 我喜欢在 github 上分享示例项目。
https://github.com/johnjohndoe/PathInterpolation
随意分叉它。
I came up with the same problem and implemented it with some friends the other day. I like to share the example project on github.
https://github.com/johnjohndoe/PathInterpolation
Feel free to fork it.
谷歌“正交回归”。
最小二乘技术试图最小化拟合线和每个 f(x) 之间的垂直距离，而正交回归则最小化垂直距离。
附录
在存在噪声数据的情况下，古老的RANSAC算法是也值得一看。
Google "orthogonal regression".
Whereas least-squares techniques try to minimize vertical distance between the fit line and each f(x), orthogonal regression minimizes the perpendicular distances.
Addendum
In the presence of noisy data, the venerable RANSAC algorithm is worth checking out too.
在 3D 图形领域，NURBS 很流行。 更多信息很容易通过谷歌搜索。
In the 3D graphics world, NURBS are popular. Further info is easily googled.