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

Question

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Вот как это работает: у вас есть полином 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

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

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

Answer 5

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

Answer 6

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

x _i i + 1

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

Добавление

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