» Интерполяция (нужна помощь)

Возникла необходимость интерполировать заданный набор координат в 3-х мерном пространстве (или хотя бы в 2-х мерном). Необходимось возникла именно в интерполяции а не в аппроксимации. Реально это плавная линия ПРОХОДЯЩАЯ через заданный набор точек (в 3-х или 2-х мерном пространстве).
Я нашел много статей по интерполяции но всюду были некоторые ограничения. Есть алгоритм интерполяции функции при котором входной набор точек должен быть упорядочен (по x) по возрастанию; можно использовать кривые Безье но они принадлежат к алгоритмам аппроксимации проходя лишь через первую и последнюю точки ; был неплохой алгоритм для замкнутого графика но он требовал последние три точки задавать такие же как первые .
Помогите пожалуйста. Действительно нужно, а нигде толком ничего найти не могу . Делают же простые векторные редакторы у которых ничего кроме плавной линии через все точки нету а исходники не найти

Используй полином Лагранжа или кубический сплайн дефекта 1. Если интересны подробности, сообщу.

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

Сплайн строится исходя из условий гладкости, т. е. непрерывности функции и ее первой производной. Сплайн - это кусочно-гладкая функция.

У меня есть исходники этого дела - реализованы мной в виде классов C++ с перегрузкой оператора (). Все отлажено и многократно использовано, если интересно - поделюсь.

Очень хотелось бы узнать подробности... Может где-то есть дока (в електронном виде) по этому делу? И на исходники не против взглянуть... Только не знаю как это организовать

Доки в электронном виде, увы, нет. Исходники я могу прислать по почте - там не более 100 кб. Мой адрес: <thechampion@yandex.ru>

Хорошая дока - учебник Вержбицкого по численным методам.

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

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

CamTracer
А в какой ящик писать? Мне бы всё пригодилось... А паскаль все равно можно на С++ переделать

Ребята!!! Ну кто-нибудь! Помогите пожалуйста...

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

В сборниках АЛГОРИТМЫ была программа интерполяции по методу Эйткина, то есть берётся интервал из 4 точек, по ним строится порабола, искомый результат ищется в иртервале между 2 и 3 точек, а на концах соответственно 1-2 и 3-4 интервалы.
Всех благ

Меня интересует двумерная интерполяция на регулярной сетке.
Может кто-дибо помочь готовым отлаженым решением?

Есть такая штука: БЧА НИВЦ МГУ. И там можно скачать много, много разных подпрограмм. В частности, для вычисления сглаживающего кубического сплайна, заданного на равномерной или неравномерной сетке. А потом по готовым параметрам сплайна, понятное дело, можно интерполировать. То, что нужно? Тогда смотреть здесь:

http://www.srcc.msu.su/num_anal/lib_na/cat/cat0.htm

ab171
Ну например интерполяция по n ближайшим точкам, веса точек обратно пропорциональны удалённости, подойдёт? (коорд. декартовы или полярные). На каком языке?

FuzzyLogic
Координаты декартовы. Язык - паскаль дельфийский.
Очень интересное решение.
Насколько оно апробировано на практике?

Добавлено:
XPEHOMETP
Да это оно. спасибо.
Но задача довольно тривиальная, потому хотелось готовое решение на паскале.

Так и надо было сказать: наворотов не нужно, чем проще, тем лучше... Тогда берем в руки очень ценную книжку: В.П.Дьяконов, "Справочник по расчетам на микрокалькуляторах". И смотрим в 5-й главе про интерполяцию функции одной переменной. Функция интерполируется полиномом, заданным на равномерной сетке из n точек. Там разные варианты есть, в зависимости от n. Например, для n = 3:

Последовательные значения х: Х(-1), Х(0), Х(+1)
Последовательные значения y: Y(-1), Y(0), Y(+1)
Нужно узнать Y для известного значения Х с помощью квадратичной интерполяции.
Вспомогательная переменная р = (Х-Х(0))/h
(h - понятное дело, шаг сетки по Х)
Получаем:
Y(Х) = 0.5*р*(р-1)*Y(-1) + (1-р*р)*Y(0) + 0.5*р*(р+1)*Y(+1)

Если 5 равноотстоящих узлов (от Х(-2) до Х(+2)) - будет интерполяция полиномом четвертой степени:

Y(Х) = (р*р-1)*р*(р-2)*Y(-2)/24 - (р*р-4)*р*(р-1)*Y(-1)/6 + (р*р-1)*(р*р-4)*Y(0)/4 + (р*р-4)*р*(р+1)*Y(+1)/6 + (р*р-1)*р*(р+2)*Y(+2)/24

Куда уж проще?

XPEHOMETP
интересует интерполяция функции двух переменных.
извините
не совсем представляю себе сплайны-поверхности, это какие-то параболоиды получаются?
Накрайняк сгодилась бы и линейная интерполяция, но непонятно как строить плоскость по четырем реперным точкам.

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

Надеюсь я внятгно излагаю?

Хорошо, есть функция Z(X,Y), заданная в узлах равномерной сетки. Определимся для начала с тем, считаем ли мы имеющиеся данные точными или мы думаем, что их надо подправить усреднением, подгонкой под теоретическую зависимость и т.п. Если они точные, можно через выбранные точки сетки провести некую поверхность, размерность которой зависит от числа взятых точек. Больше взяли точек - пишем уравнение поверхности с большим числом составляющих. Тогда интерполяция по плоскости ничем принципиально не отличается от интерполяции на линейной сетке.

Короче, берем ту же книжку Дьяконова и смотрим раздел про интерполяцию функции двух переменных. Для 4-х точек будет поверхность второго порядка; не фонтан, но в простых случаях сойдет. Точки такие: Z(0,0), Z(0,1), Z(1,0), Z(1,1) - это начальная точка и те, которые получены при сдвиге на один шаг по Х (он опять будет h) и Y (его обозначим как k). Кроме переменной р вводим еще аналогичного вида q:

q = (Y-Y(0))/k

Получаем:

Z(X,Y) = (1-p)*(1-q)*Z(0,0) + p*(1-q)*Z(1,0) + q*(1-p)*Z(0,1) + p*q*Z(1,1)

Чисто разностная схема второго порядка, никаких наворотов. Зато таким выбранным квадратиком можно при необходимости обежать всю поверхность.

Шесть точек - добавляется Z(0,-1), Z(-1,0) (похоже, предел для калькулятора, у Дьяконова более сложных вещей нет). Формула такая:

Z(X,Y) = 0.5*q*(q-1)*Z(0,-1) + 0.5*p*(p-1)*Z(-1,0) + (1+ p*q - p*p - q*q)*Z(0,0) + 0.5*p*(p - 2*q +1)*Z(1,0) + 0.5*q*(q - 2*p + 1)*Z(0,1) + p*q*Z(1,1)

До третьей степени не дотягивает, но точность повышается солидно.

XPEHOMETP
О! похоже на то что надо.
Но у меня по одной из осей неравномерный шаг сетки оказывается.

Первая формула похожа на то что предлагал FuzzyLogic, нет?

А есть ли книжка Дьяконова в электронном виде в Сети?

Так при 4-х точках без разницы, равномерный шаг или нет, потому что данные берутся только в пределах одного шага. Сдвинулись на клеточку - там уже шаг может быть свой. Вот при шести уже не пройдет. А на счет книжки в сети - не знаю, не встречал. Хотя и не искал специально.

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

Да. Спасибо! помог.
Думаю точности хватит.
Я автоматизирую процедуру приведения єкспериментальных данных по номогораммам.
Так, как раньше это делалось по графику на глазок, то выигрыш в точности будет обязательно.
О результатах внедрения напишу позже, по мере реализации. если интересно.

ab171

Цитата:

не совсем представляю себе сплайны-поверхности, это какие-то параболоиды получаются?

Ну вообще то там кривые третьего порядка. А согласно теории сплайн-функций (сам этими вещами занимался), сплайны дают наилучшую интерполяцию в классе функций W2_2, то есть дают функцию с минимальной энергией. Если не понятно - могу точнее пояснить.
Вообще сплайны - довольно простая вещь. Гораздо проще чем полиномы Лагранжа. Сейчас, правда, больше смотрят в сторону вейвлетов, наверно потому, что сплайны уже все изъезжены вдоль и поперек.
По поводу сплайнов на функциях двух переменных. Как мне объяснил один ОЧЕНЬ знающий в сплайнах (в самом деле знающий - один из ведущих спецов) человек - в многомерном случае лучше использовать аппарат B-сплайнов.
По многомерным сплайнам на вскидку нашел такую статью
http://www.fizteh.ru/02-07-90327/splain/splin/f_0r81
там вроде формулы есть. Но это не B-сплайны. Если интересно - поищу по ним отдельно. С ними все гораздо проще. Для B-сплайнов двумерная задача распадается на N одномерных задач - сплайны ортогональны по измерениям и не влияют друг на друга.

Mickey_from_nsk
Да, это было бы интересно.
Если не трудно - найди.


Цитата:

двумерная задача распадается на N одномерных задач

N=2 ?

ab171
Например, здесь
http://www.uran.donetsk.ua/~masters/2005/kita/tribrat/library/splines.htm
Кое что из B-сплайнов расписано. Правда часть формул в моих браузерах отсутствует.
Вот нашел нормальное описание, в т.ч. и двумерная интерполяция:
http://flanker.h1.ru/files/bsplines.z

Цитата:

N=2

Квак бы не квак , N - размерность сетки. В B-сплайнах надо координату x искать строя соответствующий B-сплайн по данной координате, координату y - по соотв. координате.

Mickey_from_nsk
Спасибо

Цитата:

http://flanker.h1.ru/files/bsplines.z

пример скомпилировался