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

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

Кармин А.

Научный руководитель - к.ф.-м.н, доцент Юмова С.Ж.

УУИЖТ

 

Введение

Исаак Шёнберг впервые употребил этот термин в 1946 году в качестве обозначения класса полиномиальных сплайнов. До 1960 годов сплайны были в основном инструментом теоретических исследований, появляясь в качестве решений различных экстремальных и вариационных задач, особенно в теории приближений. С развитием вычислительной техники их использование началось в компьютерной графике и моделировании.

1. Сплайны

Под сплайном обычно понимают кусочно-заданную функцию, совпадающую с более простыми функциями на каждом элементе разбиения своей области определения.

При построении классического сплайна одной переменной область определения разбивается на конечное число отрезков, на каждом из которых он совпадает с некоторым алгебраическим полиномом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Так, непрерывная ломаная есть сплайн степени 1 и дефекта 1. Сплайны имеют применения, как в математической теории, так и в разнообразных вычислительных приложениях. В частности, сплайны двух переменных интенсивно используются для задания поверхностей в различных системах компьютерного моделирования.

1.1 Кривые Безье

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

Кривой Безье называется параметрическая кривая, задаваемая выражением:

,

где   – функция компонент векторов опорных вершин, n – степень полинома, i – порядковый номер опорной вершины

1.2 Виды кривых  Безье:

1. Линейная кривая (n =1) представляет собой отрезок прямой линии, опорные точки P0 и P1 которой определяют его начало и конец:

 

2. Квадратичная кривая Безье (n = 2) задаётся тремя опорными точками: P0, P1 и P2:  .

3. Кубические кривые Безье (n = 3) в параметрической форме описывается следующим уравнением:

)

Четыре опорные точки P0, P1, P2 и P3, заданные в R2 или R3 определяют форму кривой. Линия берёт начало из точки P0, направляясь к P1 и заканчиваясь в точке P3, подходя к ней со стороны P2, не проходя через них. Отрезок [P0 P1] определяет, как скоро кривая повернёт к P3.

         Рис.1 Кубическая кривая Безье

Ниже записана матричная форма кубической кривой Безье:

,      ,

где МВ называется базисной матрицей Безье:

 

1.3 Построение  кривых Безье

Для построения квадратичных кривых Безье требуется выделение двух промежуточных точек Q0 и Q1 из условия, чтобы параметр t изменялся от 0 до 1:

Точка Q0 изменяется от P0 до P1 и описывает линейную кривую Безье.

Точка Q1 изменяется от P1 до P2 и описывает линейную кривую Безье.

Точка B изменяется от Q0 до Q1 и описывает квадратичную кривую.

 

Рис.3 Построение квадратичной кривой Безье

 

Для построения кривых высших порядков соответственно требуется и больше промежуточных точек. Для кубической кривой это промежуточные точки Q0, Q1 и Q2, описывающие линейные кривые, а также точки R0 и R1, которые описывают квадратичные кривые.

Рис.4 Построение кубической кривой Безье

Для кривых четвёртой степени это будут точки Q0, Q1, Q2 и Q3, описывающие линейные кривые, R0, R1 и R2, которые описывают квадратичные кривые, а также точки S0 и S1, описывающие кубические кривые:

Рис.5 Построение кривой Безье 4-ой степени

1.4 Применение  в компьютерной графике

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

1.5 Кубический интерполяционный сплайн

Пусть на [a,b] задана сетка a=x0<x1<..<xn=b, в узлах которой известны значения функции yi=f(xi). Сплайн третьей степени S3(x), нтерполирующий заданную функцию f(x), должен удовлетворять условиям:

1) S3(x)ÎC2[a,b], т.е. во внутренних узлах сплайн и его производные до 2-го порядка непрерывны;

2) для любого частичного промежутка [xi, xi+1] S3(x)-многочлен третьей степени такой, что S3(xi)=yi  , i=0,..,n.

 

Библиографический список

1. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы сплайн-функций. - М.: Наука, 1980 г.
2. Де Бор К. М. Практическое руководство по сплайнам. -Радио и связь, 1985.
3. Альберг Дж., Нилсон Э., Уолш Дж. Теория сплайнов и её приложения. -М. Мир, 1972.