Interpolation of three-dimensional coordinates between known missing time intervals

Question

Data is a path in space. I have 3D location data (x, y, z) and the time at which the location point was recorded.

The x, y, and z coordinates are the location points of something traveling through 3D space. The time values ​​are the time (starting from 0) that is recorded at each point.

xyz 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 will eventually skip some entries. (this is known and accepted as true) And the data stream will continue with a different time interval:

 xyz 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 ... ... 

Please note that the data has been simplified. My goal is to interpolate the missing 3D points at known missed moments. I have studied various interpolation methods, but I'm not quite sure which interpolation method is suitable for my problem.

1) Can someone briefly explain the problem? My math is extremely rusty, and I’m not sure how to describe it correctly, which forces me to investigate interpolation methods that may be incorrectly selected.

2) Update 1 . Triccubic interpolation should not be applied here, since I do not work with a grid in three-dimensional space. I work with a trajectory. I found an implementation of Tricubic Interpolation in Apache math3 communities, however I'm not sure if this is what I need. If you look at the arguments that it takes, it takes a double matrix [] [] [] fval, which I'm not sure about.

3) If not suitable for Java, the best tool to interpolate this data?

Update 2 - Specter Solution Question

In your editing, you give the following advice regarding "matching the first conclusions of the sovlocal points":

let's define our t=<-2,+2> and try such a control point (it doesn’t really matter how it affects only the magnitude of the coefficients and including -1,0,1 will greatly simplify the equations):

 p(-2) = p0 p(-1) = p1 p( 0) = p2 p( 1) = p3 

Now suppose we want to interpolate all the points on the interval t=<0,1> , so that all the points are between p2 and p3 . And we want a continuous piecewise curve, so the first derivations at the sovlocal points must coincide. We have another control point on the left side, so the second output may also be the same:

 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 

I hope I did not make a stupid mistake in the second derivation. Now simply replace p(t) with the known control points and form a system of equations and calculate a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4 .

1) What do you mean by joint points ?

2) Where

 p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1) p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2) 

have come? Are they in any way related to p(0) = p2 and p(1) = p3 ? Can they be anyone?

It can be written as p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1)) correct? I don’t understand why this is done. Or even why it is can do

2b) A similar question for

 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 

but I suppose that clarifying question 2) will ease my ambiguity for 2b), because I have no idea where the equation came from.

What follows is pretty straightforward, then it's just a system of equations

Answer 1

Since your data is most likely just smooth curve points, I would use a cubic interpolation polynomial:

• Inner linear integral interpolation curve in C # / Unity3D

The properties of the curves are such that they pass through all the control points ( t={-1,0,+1,+2} ), and the direction (1st output) in the internal control points is the average for the sides of the stand to smoothly connect ( like bezier cubes).

Algo is as follows:

• take 2 points before the missing point and 2 after

  allows you to call them p0,p1,p2,p3 , they must be perfectly equidistant in time ... and ordered in time.

• calculate 4 coefficients for each axis

   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)); 

• set the parameter t=<0,1> for the value corresponding to the missing time

  therefore, if you chose points p0,p1,p2,p3 with time t0,t1,t2,t3 , then the missing time tm corresponds to the parameter:

   t = (tm-t1)/(t2-t1); 

• calculate the missing point.

   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 higher order polynomials if that is not enough by deriving similar equations or fitting. Also take a look at this:

• How can I create multipoint linear interpolation?

[Edit1] building your own polynomial

The answer to your comment is in [edit2] of The influence of cubic and cat splines on the image , which is also linked in the previous link above. In order to make 4th degree polynomial interpolation in a similar way, you will have 5 points (p0,p1,p2,p3,p4) and the 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 

let's define our t=<-2,+2> and try a control point similar to this one (it doesn't really matter how it just -1,0,1 magnitude of the coefficients and including -1,0,1 will greatly simplify the equations):

 p(-2) = p0 p(-1) = p1 p( 0) = p2 p( 1) = p3 p( 2) = p4 

Now suppose we want to interpolate all the points on the interval t=<0,1> , so that all the points are between p2 and p3 . And we want a continuous piecewise curve, so the first derivations at the sovlocal points must coincide. We have another control point on the left side, so the second output may also be the same:

 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 

I hope I did not make a stupid mistake in the second derivation. Now we simply replace p(t) with the known control points and form a system of equations and calculate a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4 . Hint, use t=0,t=+1 and t=-1 to get linear equations for them. For instance:

 p( 0) = p2 = a0 + a1*0 + a2*0*0 + a3*0*0*0 + a4*0*0*0*0 p2 = a0 

As you can see, a0 calculated really just as it 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 ------------------------------------------------------------------- 

Now use t=+1 and t=-1 and calculate a3,a4 . You can set the divisions of the essential points according to your specific needs (and not just the average of the derivations of the left and right), but for the formation of a continuous curve, such as yours, this is the best (in my experience).