Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/modif/byvshy.doc Дата изменения: Mon May 24 15:32:03 2004 Дата индексирования: Mon Oct 1 20:51:43 2012 Кодировка: koi8-r

В этом документе изложены несколько примеров построения кубических
сплайнов.
Задачи решались программой DebugCalculation, написанной на Microsoft Visual
С++ 6.0. Исходный текст программы и exe - файл в виде zip архива помещены
здесь: http://www.srcc.msu.su/num_anal/lib_na/modif/spline.zip


Задача 0

Задача построения интерполяционного кубического сплайна для сеточной
функции Y(Xi) , i = 1, 2, ..., N . Условие задачи изложено здесь:
http://www.srcc.msu.su/num_anal/lib_na/cat/i/iis4r.htm.

Решение этой задачи программой DebugCalculation:

[pic]



Задача 1

Через точки, произвольным образом лежащие на плоскости, нужно провести
гладкую кривую с использованием кубических сплайнов. Каждой точке (Xi,Yi)
1<=i<=N присвоен индекс i, который определяет последовательность
прохождения кривой через точки. Задачу можно решить построением
параметрической функции (X(t),Y(t)), где X(ti)= Xi, Y(ti)= Yi .

Для каждой компоненты функции X(t) и Y(t) строится кубический сплайн:

X(t) = Xi + cx1 i ( t - ti ) + cx2 i ( t - ti )2 + cx3 i ( t - ti )3 ,
t ? [ti, ti + 1] , i = 1, 2, ..., N - 1 ;

Y(t) = Yi + cy1 i ( t - ti ) + cy2 i ( t - ti )2 + cy3 i ( t - ti )3 ,
t ? [ti, ti + 1] , i = 1, 2, ..., N - 1 .

Здесь cx1 i , cx2 i, cx3 i - коэффициенты сплайна по X,
cy1 i , cy2 i, cy3 i - коэффициенты сплайна по Y.

Сеточное разбиение параметра t должно удовлетворять условию ti + 1 > ti . В
примере, который реализован в программе DebugCalculation, выбраны два
разбиения - равномерное и неравномерное.

В равномерном разбиении шаг разбиения задается равным 1:
ti = i, i = 0, 1, ..., N - 1

В неравномерном разбиении шаг равен расстоянию между соседними точками на
плоскости (Xi,Yi) и (Xi+1,Yi+1):

ti = S Ri, где (Ri)2 = (Xi + 1 - Xi)2 + (Yi + 1 - Yi)2 , i = 0, 1, ..., N
- 1.

Решение задачи 1 показано на рисунке:

[pic]

Видно, что кривые, построенные с использованием равномерного и
неравномерного сплайнов, ведут себя совершенно по-разному. Сплайн с
неравномерным разбиением (синяя линия) достаточно хорошо справляется с
задачей построения гладкой кривой, тогда как равномерный сплайн (зеленая)
имеет особенности в виде "перехлестов". В окрестностях точек 4 и 15 хорошо
видны особенности сплайна с равномерным разбиением:

[pic]

[pic]

Видны "перехлесты" равномерного сплайна, тогда как сплайн с неравномерным
разбиением таких особенностей не имеет.


Задача 2

То же, что и задача 1, но с другим набором точек. Точки расположены на
окружности с радиусом 1. Первая и последняя точки с индексами 0 и 11 имеют
одинаковые координаты:


[pic]



Задача 3

В задаче 3 введена особенность - к набору точек задачи 2 добавлена еще одна
точка с индексом 7, координаты которой совпадают с координатами предыдущей
точки 6:

[pic]

Видно, что после введения дополнительной точки даже сплайн с неравномерным
разбиением теряет гладкость и в точке 7 имеет излом:

[pic]

Подпрограмма IIS3R, представленная на сайте в разделе
http://www.srcc.msu.su/num_anal/lib_na/cat/i/iis3r.htm в виде текста на
FORTRAN-е, при решения задачи 3 выдает ошибку при обнаружении совпадающих
точек. В программе DebugCalculation модуль iis3r решает задачу 3 без выдачи
ошибки.

Задача 4

Построение гладкой кривой в случае, если имеются совпадающие точки. В
задаче 4 к набору точек задачи 3 добавлены еще две точки рядом с точками,
имеющими одинаковые координаты:


[pic]

Положение дополнительных точек 6 и 9 выбрано достаточно близко к особым
точкам совпадающим 7 и 8:

[pic]

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


Дополнение. Прикладное применение.

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

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

[pic]

Лаборатория вычисляет координаты по данным, получаемым со спутников GPS
(Global Positioning System - глобальной системы позиционирования) и
инерциальной навигационной системы. Координаты записываются как во время
движения лаборатории, так и в моменты ее временных остановок. Требуется
получить траекторию движения лаборатории, проведя гладкую интерполяционную
кривую через точки, записанные во время проведения заезда. Траектория
должна не иметь изломов в местах остановки лаборатории, когда точки
траектории имеют одинаковые координаты. Эта задача аналогична задаче 4,
описанной выше и решается с использованием кубических сплайнов с
неравномерным сеточным разбиением параметра t.