algorithm - 线的 3 维插值

Question

我有一个问题，我需要做一个样条曲线 - 找到一个可以通过一组 3D 点 (y,x,z) 平滑插值的函数。假设有一组 20 个点，每个点都在 R3 中，所以：

P1(10, 10, 10)
P2(11, 12, 14)
P3(12, 17, 11)
P4(13, 14, 20)
...
P20(29, 32, 43)

我想绘制一条包含这些点的平滑线并找到新的点，这些点以给定的 y 值（例如 ）放在上面P21(10.5, x, z)。这个问题在 2D 中对我来说非常明显，因为我可以使用例如拉格朗日插值。但无法真正找到 3D 线的解决方案。我的第一个猜测是为每个表面做单独的拉格朗日插值，所以：

//Lagrange for y, x surface
x=Lx(y)
//Lagrange for y, z surface
z=Lz(y)
//Finding point having y given
Pa(10, Lx(10), Lz(10))

那会合适吗？我将非常感谢在 3D 中找到插值函数的任何解决方案。任何更大维度的解决方案也会对我有所帮助。

谢谢你的时间。

标签： algorithminterpolation

Answer 1

当您说直线时，我假设您的意思是曲线（不一定是直线）。从问题中对拉格朗日插值的参考，我了解到对于您的需要，多项式插值就足够了（即使它可能导致龙格现象）。

3D 曲线的方便表示形式是参数形式（参见例如此处）作为元组(X(s), Y(s), Z(s))，其中s是一些参数，每个坐标是s（在您的情况下为多项式函数）的函数。给定si每个输入点的参数，曲线拟合问题简化为分别拟合(si, Xi)、(si, Yi)和的三个二维问题(si, Zi)。

但是，要使其正常工作，您需要si对输入点进行合适的参数化。在您建议的问题中，Yi可以作为这样的参数化。如果Yi确实是一个合适的参数化，那么你很幸运，你的工作已经完成。您拥有这些功能X(y), Z(y)（Lx(y)并且Lz(y)在您的问题中），并且可以在任何 y 值处评估它们。

但是，在许多情况下，y 不是 3D 的合适参数化。特别是，如果(Yi, Xi)-values 或(Yi, Zi)-values 不是单调的，Yi则它不能用作参数化。

由于您对点进行了排序，因此您可以使用统一的参数化（s0=0, s1=1...等），这肯定是单调的。在样条拟合中常用的一种优选方法是弦长参数化。在这里，参数化由有序点之间的距离的累积长度定义（s0=0, s1=|p1-p0|, s2 = s1+|p2-p1|...等）。这种参数化可能会给你一个更好的拟合。这些参数化也扩展到更高维度的曲线。

参数曲线的一般困难在于，虽然它们使您能够沿曲线密集采样点，但在曲线上找到与给定y0值对应的点需要一个逆问题。在您的情况下，它需要找到根Y(s)=y0，然后将根s插入X(s)and Z(s)。然而，这是无法避免的，因为例如可能有多个点对应于给定的 y 值。您可以使用二分法或Newton-Raphson等寻根方法来解决问题。

最后一点，您可能更喜欢使用 B 样条插值（即分段多项式），它比高次多项式插值具有一些更可取的属性（参见此处或任何 B 样条教科书，例如“The NURBs Book”）。Python 的 scipy 库还具有样条拟合功能（例如，请参阅此SO 答案）。