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

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

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

Сплайны Катмулла-Рома имеют непрерывность C1, локальное управление и интерполяцию, но не лежат в выпуклой оболочке своих контрольных точек.

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

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

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

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

Вот как это работает: у вас есть многочлен n-го порядка, p(x), где 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. Затем у вас есть многочлен, который проходит через все точки, и теперь вы можете интерполировать между точками.

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

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

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

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

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

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

x _i ‹x _{i + 1}

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

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

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

https://github.com/johnjohndoe/PathInterpolation
Не стесняйтесь его разветвлять.

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

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

Дополнение

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

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