Для произвольной последовательности точек в пространстве, как бы вы создали гладкую непрерывную интерполяцию между ними?
Предлагаются 2D и 3D решения. Решения, которые создают список точек при произвольной гранулярности и решениях, которые создают контрольные точки для кривых Безье, также оценены.
Кроме того, было бы здорово увидеть итерационное решение, которое могло бы приближать ранние участки кривой, когда оно получало точки, поэтому вы могли рисовать с ним.
сплайн Catmull-Rom будет проходить через все контрольные точки. Я считаю, что это более удобно, чем пытаться настроить промежуточные контрольные точки для других типов сплайнов.
Этот PDF от Christopher Twigg имеет приятное краткое введение в математику сплайна. Лучшее сводное предложение:
сплайны Catmull-Rom имеют C1 непрерывность, локальный контроль и интерполяции, но не лежат в пределах выпуклый корпус их контроля точек.
Говоря иначе, если точки указывают на резкий поворот вправо, сплайн уйдет влево до поворота вправо (там примерное изображение в этом документе). Жесткость этих поворотов контролируется, в этом случае используется его параметр tau в примерной матрице.
Вот еще один пример с некоторым загружаемым кодом 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 сплайн? Может ли это быть принуждено делать то, что вы хотите?
К сожалению, Лагранжа или другие формы полиномиальной интерполяции не будут работать на произвольном множестве точек. Они работают только на множестве, где в одном измерении, например. х
x i < х <суб > + 1суб >
Для сурового множества точек, например. траектория полета самолета, где каждая точка представляет собой пару (долгота, широта), вам будет проще просто моделировать путешествие в самолете с текущей долготой, широтой и скоростью. Регулируя скорость, с которой самолет может поворачиваться (его скорость angular) в зависимости от того, насколько близко к следующей путевой точке, вы можете достичь плавной кривой.
Результирующая кривая не будет математически значимой и не даст вам контрольных точек безье. Однако алгоритм был бы вычислительно прост независимо от количества путевых точек и мог бы производить интерполированный список точек при произвольной детализации. Также не требовалось бы, чтобы вы предоставили полный набор точек спереди, вы могли бы просто добавить путевые точки в конец набора по мере необходимости.
Существует несколько алгоритмов для интерполяции (и экстраполяции) между произвольным (но окончательным) набором точек. Вы должны проверить числовые рецепты, они также включают в себя реализации С++ этих алгоритмов.
Я столкнулся с той же проблемой и реализовал ее с некоторыми друзьями на днях. Мне нравится поделиться примером проекта с github.
https://github.com/johnjohndoe/PathInterpolation
Не стесняйтесь разветвлять его.
Google "ортогональная регрессия".
В то время как методы наименьших квадратов пытаются минимизировать вертикальное расстояние между линией подгонки и каждой f (x), ортогональная регрессия минимизирует перпендикулярные расстояния.
Добавление
При наличии шумных данных заслуживает внимания и почтенный алгоритм RANSAC.
В мире 3D-графики NURBS популярны. Дополнительная информация легко переводится в Google.