Добрый день. бьюсь с такой алгоритмической задачей:
Задан случайный массив точек в пространстве, т.е. коррдинат X, Y, Z, плюс начальный вектор движения, больше ничего. Требуется интерполировать по ним график (т. е. провести условный летающий объект через все точки), желательно с непрерывностью до второй производной. Мое видение возможных подходов:

1) Введение четвёртой независимой переменной, например времени, и интерполяция отдельно функций x(t), y(t), z(t). Подробно не прорабатывал, но так как время прохождения точек неизвестно (более того, это время нужно найти в ходе решения), предполагаю что данный метод мне не подходит.

2) Интерполяция двух координат от третьей, например y(x) и z(x). Пробовал реализовать, в соответствующих плоскостях YOX и ZOX получаются гладкие кривые, но построенная по ним трехмерная кривая имеет в некоторых точка изломы (возможно в некоторых точках они просто видимы невооруженным глазом, а на самом деле присутствуют везде и данный подход совсем не подходит для задачи построения гладкой траектории).

Вообщем я в замешательстве. Какой из подходов стоит развивать, есть ли другие варианты решения?

Можно наделить точку массой и дать ей реактивный двигатель с заданным ускорением. И пусть летит с постоянной скоростью. Тогда движение от одной точки к другой - задача в одной плоскости. При таких условиях у неё должно быть вменяемое решение.

Видимо, есть еще какой-то критерий оптимизации траектории. (?)
Если нет, то наверное, можно выбирать тройки точек, строить по ним плоскость и в этой плоскости строить сплайн.
А можно соединить все точки прямыми, а потом найти уравнения сглаживающие углы.

Заданный модуль скорости (постоянный, или меняющийся от точки к точке), гладкость до второй производной, ну и условия реализма - ограничение на крутизну виражей, более-менее логичные траектории а не кривые с петлями.

Сплайны по тройкам точек - звучит логично, только предполагаю трудности в их стыковке, ведь две соседние плоскости вполне могут быть скажем перпендикулярны друг другу.

Уравнения сглаживающие углы - если допустить прохождение не через точки, а примерно рядом, то вроде возможно достаточно простое решение. В ином случае с ходу сложно придумать.

Вот движение между точками под действием заданного поперечного ускорения (которое корректировало бы направление движения, но не изменяло модуль скорости) меня заинтересовало. К несчастью физика мне дается хуже чем математика, поэтому пока раздумываю над решением

Сообщение отредактировал Jack_of_Shadows - Mar 2 2012, 21:31

Мне кажется подойдет сплайновая интерполяция. По крайней мере она обеспечивает ваше условие на счет непрерывности до второй производной.

Если речь идет именно о траектории (моделирование полета физического тела), то тут надо задаваться массой тела, тягой маршевых двигателей и тягой двигателей поворота и моментом инерции тела... эти параметры внесут граничные условия в математическую модель. А вот как для такой модели решить задачу минимизации времени проходжения траектории это надо ещё думать...

Вроде как вырисовываются 3 независимых уравнения движения mx''=Fx, my""=Fy, mz''=Fz
Для которых даны начальные координаты x0,y0,z0, и начальные скорости vx0, vy0, vz0.
Нужно найти силы (не зависящие от времени) при которых траектория пройдет
через координаты x1,y1,z1, и получть аналитический вид траектории.

Если такая задача решится, у вас на руках аналитическое решение, для которого
только и надо будет подставлять координаты и скорости в точке n
и отрисовывать кривульки до точки n+1.

Чутье подсказывает, что задача решается.

Хотя, я бы предпочел сплайны для "скользящих" плоскостей. 2 предыдущих точки + 1 последующая.

Спасибо всем за советы, задача в общих чертах решилась, осталось на нее навешивать дополнительные плюшки. Рассматривал движение точки под поперечным ускорением, массу и силу вводить не пришлось, оперировал исключительно скоростью, ускорением и вызванным ими прирощением координаты. Вектор скорости под действием ускорения плавно поворачивался в сторону цели, и когда угол между скоростью и направлением на цель становился меньше порога, ускорение отключалось. Решил задачу сперва для плоскости, увидел что при переходе к пространству я зароюсь с геометрией, и схитрил: на каждом отрезке строил плоскость, заданную вектором входной скорости и самим отрезком, работал с ней, потом пересчитывал обратно к трехмерным координатам.

От изначальной навязчивой идеи интерполировать траекторию теми же сплайнами пришлось отказаться, математика все таки слишком далеко от логики полёта реального объекта, имеющего скорость, инерцию, ограниченные перегрузки

Симпатично :-)
Кстати, в отдельных случаях точка может пролетать мимо цели и делать большую петлю. Если это нежелательно, то, возможно, нужно увеличивать ускорение или даже ставить его в зависимость от расстояния от начальной точки до конечной.

Да, если расстояние слишком маленькое начинает нарезать круги пока по таймауту не вылетит. Пока единственное очевидное решение этой проблемы (с учетом что максимальное ускорение превышать нельзя) это вводить между близкими точками промежуточую на некотором расстоянии от обоих, так чтобы получившиеся отрезки беспроблемно проходились. На днях планирую добраться до этого.

Мне кажется, это не даст решения в большинстве случаев. Примеры придумать несложно. Если петли нежелательны, то для близких точек ускорение нужно увеличивать. В противном случае придётся решать задачу оптимизации траектории в целом (через все точки), и эта задача в общем случае может и не иметь решения (примеры, я думаю, также несложно придумать).
Кстати, движение с постоянным поперечным ускорением - это движение по окружности. Соответственно, ускорение обратно пропорционально радиусу кривизны :-)
Центростремительное ускорение

Даже с моим небольшим знанием физики про центростремительное ускорение я знаю А вообще там изначально фигурировало требование непрерывной второй производной, поэтому пришлось допилить алгоритм так, чтобы ускорение появлялось не скачком, а начинало постепенно нарастать до максимума, а потом убывать. Затем, раз пошла такая пьянка, добавил и продольное ускорение, чтобы от точки к точке можно было менять скорость объекта (естественно тоже нарастающее постепенно). В итоге траектории получились уже совсем не окружные.

Слишком близкие точки конечно самое тяжелое место. Превысить максимальное ускорение - никак нельзя, рушится реализм.

Сообщение отредактировал Jack_of_Shadows - Mar 14 2012, 19:33