интерполяция кубическими сплайнами или Акима сплайн

[anpoit00]

Помогите пожалуйста разобраться с интерполяцией!

заданы точки в табличной форме $[x y]$, необходимо найти промежуточные точки.
Попробовал интерполяцию кубическими сплайнами но там в нормальной форме
необходимо выполнение условия возростания $x$. Кроме того метод не работает если $x(i)$ и $x(i+1)$ равны.
Есть ли модифицированный метод так что-бы небыло этих ограничений? Тот же вопрос касаемо Акима сплайна, ведь как-то же делают.
Не очень хочется интерполировать с помощью безье кривых в параметрической форме.

Спасибо

[ИСН]

Одно из двух: Вы интерполируете либо функцию $y(x)$, либо не функцию $y(x)$.
В первом случае $x(i)$ и $x(i+1)$ не могут быть равны.
А во втором - какое у Вас моральное право уклоняться от использования Безье?

[anpoit00]

Возьмем к примеру элипс. У него значение $x$ не монотонно восрастающее. Но как-то в mathlab сделано же http://www.mathworks.ch/ch/help/matlab/ref/spline.html.

[profrotter]

Используйте параметрическое задание кривой. Считайте, что у вас не одна таблица, а две таблицы: $x(i)$ и $y(i)$, где аргумент функций $t$ изменяется дискретно с шагом 1 от нуля до номера последнего отсчёта, принимая значения $i$. Интерполируйте любым понравившемся вам методом эти функции, получив интерполирующие функции $x(t)$ и $y(t)$, а график стройте как геометрическое место точек с координатами $x(t),y(t)$.

[_Ivana]

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

[Алексей К.]

anpoit00 в сообщении #738217 писал(а):

Возьмем к примеру эл(л)ипс.

profrotter в сообщении #738233 писал(а):

Считайте, что у вас не одна таблица, а две таблицы: $x(i)$ и $y(i)$, где аргумент функций $t$ изменяется дискретно с шагом 1 от нуля до номера последнего отсчёта, принимая значения $i$. И

Это не очень хорошо, когда речь идёт о геометрических объектах. При интерполировании кривых рекомендуется вместо $i$ (номера) в качестве параметра $t$ брать длину кривой. Последняя, естественно, неизвестна, но в качестве приближения берётся накопленная длина ломаной, проведённой через заданные узлы интерполяции. Типа

$$t_0=0,\quad t_i=t_{i-1}+\sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2}.$$

[profrotter]

Алексей К. в сообщении #738512 писал(а):

При интерполировании кривых рекомендуется вместо $i$ (номера) в качестве параметра $t$ брать длину кривой.

Почему?

[_Ivana]

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

[Алексей К.]

profrotter в сообщении #738543 писал(а):

Почему?

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

1. Начнём с того, что разные наборы $t_i$ дают разные сплайны. И, стало быть, вопрос просто достоин обдумывания.

2. Рекомендацию использовать накопленную длину хорды (вот! по этому ключевому слову я и сыщу, наверное, --- что я когда-то писал на эту тему на форуме) я где-то очень давно вычитал. Для себя придумал следующее обоснование. Всё же мы при построении сплайна приравниваем производные по тэ в узлах интерполяции. И такой подход делает это приравние более осмысленным. Да, такой выбор параметра делает его близким к натуральному.

3. Для себя придумал ещё одну фулечку. Строго говоря, мы должны ещё откуда-то взять граничные условия на производные. Всякие трюки типа понижения порядка сплайна на концах и др. заточены на то, чтобы не думать о граничных условиях, что иногда уместно. Но в примере с той же спиралью Корню мне известны наклоны касательных на концах, $\theta_0$ и $\theta_n$, и грех их не использовать для повышения точности интерполяции. Если я считаю параметр близким к натуральному, то кусочные полиномы кубического сплайна можно считать близкими к разложению $[x(t),y(t)]$ в ряд Тейлора, а в качестве производных на концах тогда осмыслены $x'(0)=\cos\theta_0,\,y'(0)=\sin\theta_0, x'(t_n)=\ldots$.

4. Все эти соображения уместны только в том случае, если икс и игрек одинакового (геометрического) происхождения. Если этот эллипс произошёл от какого-то "фазового портрета" (забыл, что это такое), и указывает допустимую связь тока и напряжения, или метров и секунд, то выписанная выше длина хорды бессмысленна. Но тогда в задаче скорее всего существует какой-то коэффициент, параметр, позволяющий осмыслить и это.

_Ivana в сообщении #738548 писал(а):

Судя по всему, процесс должен быть сходящимся.

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

-- 20 июн 2013, 16:14:28 --

Нашёл:

Алексей К. в сообщении #189236 писал(а):

Я уже пел эту арию в сообщении #164828.

[_Ivana]

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

[Алексей К.]

А смысл?
Мне в этом "движении" видится некая условность.
Взяли кривую с натуральной параметризацией, перепараметризовали её, получили "другое движение" по той же кривой...

_Ivana в сообщении #738764 писал(а):

к любому наперед заданному непрерывному монотонному закону изменения скорости движения

А немонотонно можно? Типа если я сначала бежал по кривой, потом закурил и медленно пошёл. А потом вообще стоял 5 минут, с ментом разбирался за курение в 11 метрах от вершины кривой. А потом дальше пошёл.

[_Ivana]

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

[мат-ламер]

Цитата:

интерполяция кубическими сплайнами или Акима сплайн

А что за Акима сплайн? Слышал про временные ряды типа ARIMA.

[_Ivana]

Имеется в виду сплайн Акимы, который придумал японец Хироши Акима во второй половине прошлого века. В данной теме упомянут скорее всего случайно

[Алексей К.]

profrotter в сообщении #738543 писал(а):

Почему?

Я сделал картинки на тему.
Делать из них image для форума не стал: в gsview их можно увеличить, подставить свои узлы интерполяции, и проч. Под Линуксом ---
gv -media=A3 Cornu_dxdy.ps.
Само оно здесь.
Типа смотреть лучше на A3 (что-то у меня не получилось задать её по умолчанию, кушать захотелось).

На первой страничке иллюстрируется эффект равномерности значений параметра при НЕравномерной длине кусков.
Сам раньше такого не видел: "разогнавшись" (по терминологии _Ivana) на длинном куске ([-210;115]), оно при переходе на короткий ([115;135]) не смогло затормозить и устроило загогулину на сплайне (красная кривулька внизу).

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

На третьей странице показан результат интерполяции с более приличным выбором узлов интерполяции (чем кривее, тем чаще).

Заменив строку типа
/SS [-660 -610 -490 -410 -320 -210 115 135 250 380 430 470 510 552 615 660] def
можно вставить свой массив точек на кривой (это значения длины на спирали Корню, ноль в точке перегиба).