Интерполяция последовательности точек

Вы смотрели команду Unix сплайн? Можно ли заставить это делать то, что вы хотите?

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

На первом году учебы в университете я написал небольшой инструмент для этого в 2D, и вы можете найди это на этой странице, он называется решателем Лагранжа. На странице Википедии также есть образец реализации.

Вот как это работает: у вас есть полином p(x) порядка n, где n - количество набранных вами очков. Он имеет вид a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, где _ - нижний индекс, ^ - мощность. Затем вы превращаете это в систему одновременных уравнений:

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

Вы преобразовываете вышеуказанное в расширенную матрицу и решаете коэффициенты a_0 ... a_n. Затем у вас есть многочлен, который проходит через все точки, и теперь вы можете интерполировать между точками.

Однако обратите внимание, что это может не соответствовать вашим целям, поскольку не дает возможности отрегулировать кривизну и т. д. - вы застряли с одним решением, которое нельзя изменить.

К сожалению, полиномиальная интерполяция Лагранжа или другие формы не работают с произвольным набором точек. Они работают только на множестве, где в одном измерении, например. Икс

x_i <x_i+1

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

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

Существует несколько алгоритмов интерполяции (и исключения) между произвольным (но окончательным) набором точек. Вы должны проверить числовые рецепты, они также включают реализации этих алгоритмов на C++.

Погуглите "ортогональная регрессия".

В то время как методы наименьших квадратов пытаются минимизировать вертикальное расстояние между аппроксимирующей линией и каждым f (x), ортогональная регрессия минимизирует перпендикулярные расстояния.

Дополнение

При наличии зашумленных данных стоит попробовать и маститый алгоритм RANSAC.

В мире 3D-графики популярны NURBS. Дополнительную информацию легко найти в Google.

Шпонка Catmull-Rom гарантированно проходит через все контрольные точки. Я считаю, что это удобнее, чем пытаться настроить промежуточные контрольные точки для других типов шлицев.

Этот PDF Кристофер Твигг содержит хорошее краткое введение в математику сплайна. Лучшее итоговое предложение:

Catmull-Rom splines have C1 continuity, local control, and interpolation, but do not lie within the convex hull of their control points.

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

Вот другой пример с некоторым загружаемым кодом DirectX.

Вам следует взглянуть на B-шлицы. Их преимущество перед кривыми Безье состоит в том, что каждая часть зависит только от локальных точек. Таким образом, перемещение точки не влияет на удаленные части кривой, где «далеко» определяется параметром сплайна.

Проблема с полиномом Лангранжа состоит в том, что добавление точки может иметь экстремальные эффекты на кажущихся произвольными участках кривой; нет такой "локальности", как описано выше.

Я придумал ту же проблему и на днях реализовал ее с друзьями. Мне нравится делиться примером проекта на github.

https://github.com/johnjohndoe/PathInterpolation
Не стесняйтесь раскошелиться.