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

Question

Учитывая произвольную последовательность точек в пространстве, как бы вы произвели плавную непрерывную интерполяцию между ними?

Приветствуются 2D и 3D решения.Также ценятся решения, которые создают список точек с произвольной степенью детализации, и решения, которые создают контрольные точки для кривых Безье.

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Икс_я < х_{я +1}

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

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

Answer 7

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

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

Answer 8

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

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

Приложение

При наличии зашумленных данных почтенный РАНСАК Алгоритм тоже стоит проверить.

Answer 9

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