在已知的缺失时间间隔之间插值3D坐标 [英] Interpolating 3D Coordinates between known missing time intervals
问题描述
数据是空间中的路径。我有3D位置数据（x，y，z）和记录位置点的时间。
The data is a Path in space. I have 3D location data (x,y,z) and the time the location point was recorded.
x，y和z坐标是某些东西的点位置穿越3D空间。时间值是记录每个点的时间（从0开始）。
The x ,y, and z coordinates are the point locations of something traveling through 3D Space. The time values is the time (beginning at 0) that each point was recorded.
x y z time(s)
0.1 2.2 3.3 0
2.4 2.4 4.2 0.3
4.5 2.5 1.8 0.6
I最终会错过一些录音事件。 （这是已知的并被接受为真）并且数据流将以不同的时间间隔继续：
I will eventually miss some recording events. (this is known and accepted as true) And the data stream will continue at a different time interval:
x y z time(s)
0.1 2.2 3.3 0
2.4 2.4 4.2 0.3
//missing x,y,z data point at time 0.6
//missing x,y,z data point at time 0.9
4.5 2.5 1.8 1.2
...
...
请注意数据已简化。我的目标是在已知的丢失时间内插入缺失的3D点。我已经研究了各种插值技术，但我不完全确定哪种插值方法适合我的问题。
Please note the data was simplified. My goal is to interpolate the missing 3D points at the known missing times. I have looked into various interpolating techniques but I am not entirely sure which interpolation method is suited for my problem.
1）有人可以简洁地解释这是什么问题吗？我的数学非常生疏，我不确定如何正确描述它，这导致我研究可能不适合的插值技术。
1) Can someone succinctly explain the kind of problem this is? My math is extremely rusty and I am not sure how to properly describe it, which leads me to investigating interpolation techniques that may not be properly suited.
2）更新1 由于我没有使用3D空间中的网格，因此不应在此处应用Tricubic插值。我正在研究一个轨迹。我找到了一个 Apache math3 commons中的Tricubic Interpolation实现，但我不确定这是否是我需要的。如果你查看它所采用的参数，它需要一个我不确定的double [] [] [] fval矩阵。
2) Update 1 Tricubic Interpolation should not apply here since I am not working with a grid in 3D space. I am working with a trajectory. I have found a Tricubic Interpolation implementation in the Apache math3 commons, however I am not sure if this is what I need. If you look at the arguments it takes, it takes a double[][][] fval matrix that I am not sure about.
3）如果不是最适合的话Java，插入这些数据的最佳工具是什么？
3) If not best suited for Java, what is the best tool to interpolate this data?
更新2 - 有关Spectre解决方案的问题
在您的编辑中，您提供以下有关匹配关节点的首次推导的提示：
In your edit you provide the following tip regarding "matching first derivations of joint points":
让我们定义 t = < -2，+ 2> 并像这样对控制点进行采样（实际上它不会影响系数幅度，包括 -1,0,1 将缓解方程式很多）：
let define our t=<-2,+2> and sample the control point like this (does not really matter how it will just affect the coefficients magnitude and including -1,0,1 will ease up the equations a lot):
p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3
现在假设我们想要插入区间 t =< 0,1> 上的所有点，以便 p2之间的所有点和 p3 。并且我们想要连续的分段曲线，因此关节点上的第一个推导应该匹配。我们在左侧还有一个控制点，所以第二个推导也可以匹配：
now let assume we want to interpolate all the points on the interval t=<0,1> so all points between p2 and p3. And we want continuous piecewise curve so first derivations on joint points should match. We got one more control point on the left side so the second derivation can match there too:
p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
= 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
= 0.5*(p0+p4)-p1+p2-p3
希望我在第二次推导中没有犯任何愚蠢的错误。现在只需用已知控制点替换 p（t）并形成方程组并计算 a0，a1，a2，a3，a4 代数来自 p0，p1，p2，p3，p4 。
Hope I did not make any silly mistake in the second derivation. Now just substitute p(t) with known control points and form system of equations and compute a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4.
1）你是什么意思联合积分？
2）去哪里
p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
来自？它们是否与 p（0）= p2 和 p（1）= p3 有关？它们可以是你选择的任何东西吗？
come from? Do they in any way relate to p(0) = p2 and p(1) = p3 ? Can they be anything you chose ?
它可以重写为 p'（0）= 0.5 *（（p（3）-p （0））+（p（0）-p（-1））正确吗？我不清楚为什么要这样做。甚至为什么它可以完成
It can be re written as p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1)) correct? It is not clear to me why this is being done. Or even why it can be done
2b）类似的问题
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
= 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
= 0.5*(p0+p4)-p1+p2-p3
但我假设澄清问题2）将减轻我对2b）的模糊性，因为我不知道等式来自何处。
but I am assuming that clarifying question 2) will alleviate my ambiguity for 2b) because I have no idea where the equation came from either.
接下来是非常直接的，那么它只是方程组
What follows is pretty straight forward,then it's just systems of equations
推荐答案
因为你的数据很可能只是一些平滑的曲线采样点我会使用这样的三次插值多项式：
As your data are most likely just some smooth curve sampled points I would use cubic interpolation polynomial like this:
- Piecewise linear integer curve interpolation in C#/Unity3D
曲线属性是通过所有控制点（ t = { - 1,0，+ 1，+ 2} ）并且内部控制点的方向（第一推导）是平稳地加入的摊位边的平均值（类似于 Bezier cubics）。
Curve properties are such that it goes through all control points (t={-1,0,+1,+2}) and the direction (1st derivation) at inner control points is average of booth sides to join smoothly (similar to Bezier cubics).
算法是这样的：
-
在丢失点之前取2点而在之后取2点
让我们称之为 p0，p1，p2，p3 理想情况下，它们应该是时间等距的...并按时间排序。
lets call them p0,p1,p2,p3 they should be ideally time equidistant ones ... and ordered by time.
为每个轴计算4个系数
d1=0.5*(p2.x-p0.x);
d2=0.5*(p3.x-p1.x);
ax0=p1.x;
ax1=d1;
ax2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2;
ax3=d1+d2+(2.0*(-p2.x+p1.x));
d1=0.5*(p2.y-p0.y);
d2=0.5*(p3.y-p1.y);
ay0=p1.y;
ay1=d1;
ay2=(3.0*(p2.y-p1.y))-(2.0*d1)-d2;
ay3=d1+d2+(2.0*(-p2.y+p1.y));
d1=0.5*(p2.z-p0.z);
d2=0.5*(p3.z-p1.z);
az0=p1.z;
az1=d1;
az2=(3.0*(p2.z-p1.z))-(2.0*d1)-d2;
az3=d1+d2+(2.0*(-p2.z+p1.z));
设置参数 t =< 0,1> ; 对应于缺少时间的值
set parameter t=<0,1> to value corresponding to missing time
所以如果你选择点 p0，p1，p2， p3 时间 t0，t1，t2，t3 然后缺少的时间 tm 对应于参数：
so if you chose points p0,p1,p2,p3 with times t0,t1,t2,t3 then the missing time tm corresponds to parameter:
t = (tm-t1)/(t2-t1);
计算缺失点。
x=ax0+ax1*t+ax2*t*t+ax3*t*t*t
y=ay0+ay1*t+ay2*t*t+ay3*t*t*t
z=az0+az1*t+az2*t*t+az3*t*t*t
如果通过推导类似的方程式或拟合，这可能会使用更高阶的多项式。另请看一下：
You can use polynomials of higher order if this is not enough by deriving similar equations or fitting. Also take a look at this:
- How can i produce multi point linear interpolation?
[Edit1]构建自己的多项式
您的评论的答案在 [edit2] 立方体和catmull样条曲线对图像的影响，这也与上面的链接有关。要以类似的方式制作4度插值多项式，你将得到5个点（p0，p1，p2，p3，p4）和方程式：
The answer to your comment is in [edit2] of Impact of cubic and catmull splines on image which is also linked in previous link above. To make 4th degree interpolation polynomial in similar manner you will have 5 points (p0,p1,p2,p3,p4) and equations:
p(t)= a0 + a1*t + a2*t*t + a3*t*t*t + a4*t*t*t*t
p'(t) = a1 + 2*a2*t + 3*a3*t*t + 4*a4*t*t*t
p''(t) = 2*a2 + 6*a3*t +12*a4*t*t
定义我们的 t =< -2，+ 2> 并像这样对控制点进行采样（它实际上不会影响系数幅度，包括 -1,0， 1 将缓解方程式很多）：
let define our t=<-2,+2> and sample the control point like this (does not really matter how it will just affect the coefficients magnitude and including -1,0,1 will ease up the equations a lot):
p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3
p( 2) = p4
现在假设我们想要插入区间 t =< 0,1> 的所有点，所以所有 p2 和 p3 之间的分数。并且我们想要连续的分段曲线，因此关节点上的第一个推导应该匹配。我们在左侧还有一个控制点，所以第二个推导也可以匹配：
now let assume we want to interpolate all the points on the interval t=<0,1> so all points between p2 and p3. And we want continuous piecewise curve so first derivations on joint points should match. We got one more control point on the left side so the second derivation can match there too:
p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
= 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
= 0.5*(p0+p4)-p1+p2-p3
希望我在第二次推导中没有犯任何愚蠢的错误。现在只需用已知控制点替换 p（t）并形成方程组并计算 a0，a1，a2，a3，a4 代数来自 p0，p1，p2，p3，p4 。提示使用 t = 0，t = + 1 和 t = -1 因此您将获得这些的线性方程式。例如：
Hope I did not make any silly mistake in the second derivation. Now just substitute p(t) with known control points and form system of equations and compute a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4. Hint use t=0,t=+1 and t=-1 so you will get linear equations for those. For example:
p( 0) = p2 = a0 + a1*0 + a2*0*0 + a3*0*0*0 + a4*0*0*0*0
p2 = a0
As你可以看到 a0 计算得非常简单，可以用于推导：
As you can see a0 is computed really simply the same can be used for derivations:
p'(0) = 0.5*(p3-p1) = a1 + 2*a2*0 + 3*a3*0*0 + 4*a4*0*0*0
p''(0)= 0.5*(p0+p4)-p1+p2-p3 = 2*a2 + 6*a3*0 +12*a4*0*0
-------------------------------------------------------------------
0.5*(p3-p1) = a1
0.5*(p0+p4)-p1+p2-p3 = 2*a2
-------------------------------------------------------------------
0.5*(p3-p1) = a1
0.25*(p0+p4)-0.5*(p1+p2-p3) = a2
-------------------------------------------------------------------
现在使用 t = + 1 和 t = -1 并计算 a3，a4 。您可以设置关节点派生以满足您的特定需求（不仅仅是从左侧和右侧推导的平均值），而是形成像您这样的连续曲线，这是最好的（根据我的经验）。
Now use t=+1 and t=-1 and compute the a3,a4. You can set the joint point derivations to meet your specific needs (not just average of derivation from left and right) but to form continuous curve like yours is this the best (from my experience).
这篇关于在已知的缺失时间间隔之间插值3D坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
