Как плавно интерполировать между точками в двухмерном пространстве?

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

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

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

Любая идея приветствуется.


interpolation math spline graphics curve
person Kabuto    schedule 15.07.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Похоже, вам нужен интерполирующий полином. Есть несколько способов приспособить его. Попробуйте прочитать это

http://en.wikipedia.org/wiki/Polynomial_interpolation#Constructing_the_interpolation_polynomial

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

http://en.wikipedia.org/wiki/Least_squares#Linear_least_squares

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

В качестве альтернативы вы можете интерполировать с помощью сплайнов непараметрическим способом, не связанным с контрольными точками.

http://en.wikipedia.org/wiki/Spline_interpolation

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

Как и в случае со всеми проблемами аппроксимации, трудно дать окончательный ответ, не увидев данных (и их количества). В конечном счете, если у вас есть большое количество данных, базовая полиномиальная интерполяция вам не подойдет, как если бы у вас есть 1000 точек для интерполяции, вам нужен полином 999 градусов.

person mathematician1975    schedule 15.07.2012

arrow_upward
0
arrow_downward

Здесь не избежать «сложной» математики. И это не так уж и сложно.

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

Вы можете попробовать использовать приближенные методы. «Метод наименьших квадратов» и его модификации - одни из самых простых и удобных в реализации.

person Community    schedule 20.07.2012