Интерполяция трехмерных координат между известными пропущенными временными интервалами

Question

Данные - это Путь в пространстве. У меня есть данные 3D-местоположения (x,y,z) и время, когда была зарегистрирована точка местоположения.

Координаты x, y и z являются точечными местоположениями чего-либо, путешествующего в трехмерном пространстве. Значения времени - это время (начиная с 0), когда каждая точка была записана.

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

Я в конечном итоге пропущу некоторые записи событий. (это известно и принимается как истина) И поток данных будет продолжаться в другом интервале времени:

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

Обратите внимание, что данные были упрощены. Моя цель состоит в том, чтобы интерполировать недостающие трехмерные точки в известные моменты пропущенного времени. Я рассмотрел различные методы интерполяции, но я не совсем уверен, какой метод интерполяции подходит для моей проблемы.

1) Может кто-то кратко объяснить, что это за проблема? Моя математика очень ржавая, и я не уверен, как правильно ее описать, что приводит меня к исследованию методов интерполяции, которые могут не подходить.

2) Обновление 1 Трикубическая интерполяция здесь не должна применяться, поскольку я не работаю с сеткой в ​​трехмерном пространстве. Я работаю с траекторией. Я нашел реализацию Tricubic Interpolation в общем Apache math3, однако я не уверен, что это то, что мне нужно. Если вы посмотрите на аргументы, которые он принимает, он принимает двойную [][][] матрицу fval, в которой я не уверен.

3) Если не лучше всего подходит для Java, что является лучшим инструментом для интерполяции этих данных?

Обновление 2 - Вопрос относительно решения Spectre

В своем редактировании вы предоставляете следующий совет относительно "сопоставления первых производных точек соединения":

давайте определим наш t=<-2,+2> и выборки контрольной точки, как это (на самом деле не имеет значения, как это будет влиять на величину коэффициентов и в том числе -1,0,1 значительно упростит уравнения)

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

теперь давайте предположим, что мы хотим интерполировать все точки на интервале t=<0,1> так что все точки между p2 а также p3, И мы хотим, чтобы сплошная кусочная кривая, чтобы первые отведения по точкам соединения должны совпадать. У нас есть еще одна контрольная точка на левой стороне, так что второй деривация может там совпадать:

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,

1) Что вы подразумеваете под joint points?

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? Могут ли они быть чем-то, что вы выбрали?

Это можно переписать как p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1)) правильный? Мне не понятно, почему это делается. Или даже почему это можно сделать

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), потому что я понятия не имею, откуда пришло уравнение.

То, что следует, довольно просто, тогда это просто системы уравнений

Answer 1

Поскольку ваши данные, скорее всего, представляют собой просто точки выборки с гладкой кривой, я бы использовал полином кубической интерполяции, например:

• Кусочно-линейная целочисленная интерполяция в C#/Unity3D

Свойства кривой таковы, что она проходит через все контрольные точки (t={-1,0,+1,+2}) и направление (1-й вывод) во внутренних контрольных точках является средним из сторон стенда, которые должны плавно соединяться (аналогично кубикам Безье).

Алгоритм такой:

1. взять 2 очка до пропущенного очка и 2 после

   давайте позвоним им p0,p1,p2,p3 в идеале они должны быть равноудалены от времени... и упорядочены по времени.

2. вычислить 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));
   

3. установить параметр t=<0,1> оценить соответствующее пропущенному времени

   так что если вы выбрали очки p0,p1,p2,p3 со временем t0,t1,t2,t3 тогда пропущенное время tm соответствует параметру:

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

4. вычислить недостающую точку.

   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
   

Вы можете использовать многочлены более высокого порядка, если этого недостаточно, выводя аналогичные уравнения или подгонку. Также взгляните на это:

• Как я могу произвести многоточечную линейную интерполяцию?

[Edit1] построение собственного полинома

Ответ на ваш комментарий находится в [edit2] раздела Воздействие кубических и катмулловых сплайнов на изображение, которое также связано в предыдущей ссылке выше. Чтобы сделать интерполяционный полином 4-й степени аналогичным образом, у вас будет 5 баллов (p0,p1,p2,p3,p4) и уравнения:

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 значительно упростит уравнения)

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

теперь давайте предположим, что мы хотим интерполировать все точки на интервале t=<0,1> так что все точки между p2 а также p3, И мы хотим, чтобы сплошная кусочная кривая, чтобы первые отведения на стыках точек совпадали У нас есть еще одна контрольная точка на левой стороне, так что второй деривация может там совпадать:

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 так что вы получите линейные уравнения для тех. Например:

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

Как вы видете a0 вычисляется действительно просто, то же самое можно использовать для дериваций:

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, Вы можете установить точки деривации в соответствии с вашими конкретными потребностями (не только среднее значение деривации слева и справа), но и сформировать непрерывную кривую, подобную вашей, - это лучше всего (из моего опыта).