· Сплайн (spline) — геометрический элемент, представляющий собой непрерывную плавную кривую линию, проходящей через заданные точки по определенному аналитическому закону (уравнению или системе уравнений).

Различают сплайны одномерные (т.е. сплайновые кривые) и двумерные (сплайновые поверхности). При построении первых используются кубические многочлены в уравнении, при построении поверхностей — бикубические многочлены.

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

1-й — построение кривой, проходящей через все заданные точки (задача интерполяции);

2-й — построение кривой, проходящей вблизи от этих точек (задача сглаживания).

Рассмотрим сначала задачу интерполяции.

А. Случай одной переменной. Пусть на плоскости задан набор точек (xi, yi), I = 0, 1, 2, …, m, причем верно неравенство такого типа x0 < x1 < … < xm-1 < xm (Рис.1). Поскольку набор точек пронумерован в порядке возрастания абсцисс, то тогда кривая проходящая через них график функции дискретного набора.

Из математического анализа известно, что наиболее подходящим описанием подобной ситуации (графика функции, проходящей через заданные точки) является применение интерполяционного многочлена Лагранжа.

График этой функции проходит через все заданные точки (многочлен однозначно определяется набором своих коэффициентов; их число совпадает с количеством точек набора).

Недостатки:

1. Степень многочлена Лагранжа на единицу меньше числа заданных точек. Ввиду этого график функции (при большом количестве точек набора) проходит через них, но может быть отличным от теоретического (Рис.2).

2. Изменением одной точки требует полного пересчета коэффициентов и может существенно изменить вид кривой.

Приближенное построение кривой линии, проходящей через точки массива довольно просто. Для этого необходимо сединить точки отрезками. Получим ломаную. Затем необходимо найти 2m чисел (каждый отрезок определяется двумя коэффициентами конечных точек). Однако такая, кусочно-линейная функция будет не гладкой, т.к. уже первая производная терпит разрывы в узлах интерполяции. Следовательно, надо найти такой класс функций, для которых эти недостатки будут ликвидированы. Поэтому используют кривую разбивают на фрагменты. Для описания каждого используют многочлен Лагранжа, затем последовательно строят и объединяют сегменты. Получают полиномиальный многозвенник (Рис.4), для которого плавность сопряжения сегментов зависит от тщательного подбора коэффициентов многочленов. На Рис.4 получаем физическую модельсплайновой кривой. Функция y = S(x) — описывает ее математически. Свойства этой кривой следующие:

· с довольно большой точностью часть графика этой функции, заключенную между двумя соседними опорами можно считать многочленом третьей степени;

· на всем промежутке [x0, xm] функция y = S(x) дважды непрерывно дифференцируема.

Данная функция S(x) называется интерполяционным кубическим сплайном т.к. обладает следующими свойствами:

— график функции проходит через каждую из точек заданного массива S(xi) = yi, i = 0, 1, 2, …, m;

— на каждом из отрезков [xi, xi+1], i = 0, 1, 2, …, m-1 функция является многочленом третьей степени

— на всем отрезке задания [x0, xm] функция S(x) имеет непрерывную вторую производную.

Поскольку на любом из отрезков [xi, xi+1] сплайн определяется 4-мя коэффициентами, то для полного построения необходимо найти 4m чисел.

Условие непрерывности звеньев можно использовать, как необходимость для внутренних узлов (1…m-1), а достаточным будет — непрерывность первой и второй производных в этих узлах. В сумме получаем m-1+m-1+m-1+m+1=4m-2 равенства.

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

S`(x0) = l0, S`(xm) = lm.

Б. Случай двух переменных.

Рассматривается аналогично приведенному ранее варианту, с учетом того, что интерполяция проходит в трехмерной среде для функций 2-х переменных. Результатом построения будет фигура, называемая — интерполяционным бикубическим сплайном.

Для выяснения его свойств выполним следующее. Пусть на плоскости имеем набор из (m+1)(n+1) точек (Рис.5), заданных, как : (xi, yj), i = 0, 1, 2, …, m ; j = 0, 1, 2, …, n. Здесь: x0 < x1 < … < xm-1 < xm; y0 < y1 < … < yn-1 < yn. Добавим к каждой паре (xi, yj) третью координату — zij. Получаем массив (xi, yj, zij).

· Интерполяционный бикубический сплайн — поверхность проходящая через все точки заданного массива (xi, yj, zij), и описываемая функцией S(x, y) со следующими свойствами:

— график этой функции проходит через каждую точку заданного массива S(xi, yj) = zij, i = 0, 1, 2, …, m ; j = 0, 1, 2, …, n;

— на каждом частичном прямоугольнике (см. Рис.5):

[xi, xi+1] ? [yj, yj+1], i = 0, 1, 2, …, m — 1 ; j = 0, 1, 2, …, n — 1,

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

— на всем прямоугольнике задания [x0, xm] ? [y0, yn] функция S(x, y) имеет по каждой переменной непрерывную вторую производную.

В этом случае для построения искомого би-сплайна необходимо определить 16mn коэффициентов. Результат находится аналогично рассмотренному ранее случаю с одной переменной, т.е. решая систему линейных уравнений, связывающих эти коэффициенты.

Достоинства интерполяционных методов построения сплайна:

1) наличие множества способов для решения систем линейных уравнений;

2) системы достаточно просты;

3) графики функций проходят через все точки заданного массива.

Недостатки интерполяционных методов построения сплайна:

1) изменения координат одной точки требуют полного пересчета;

2) отсутствие точных данных о координатах точек во многих практических задачах.

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

· Параметрически заданная кривая — множество g точек М(x, y, z) координаты x, y, z которых определяются соотношениями x = x(t), y =y(t), z = z(t), a ? t ? b, где x(t),y(t), z(t) — функции непрерывные на отрезке [a,b] (Рис.6). Эти соотношения — п а р а м е т р и ч е с к и е уравнения кривой g.

Векторная форма записи параметрических уравнений имеет следующий вид: r = r(t), 0?t?1, где r(t) = (x(t), y(t), z(t)). Здесь t — параметр, задающий ориентацию параметризованной кривой g (порядок прохождения точек при монотонном возрастании параметров).

· Кривая g называется р е г у л я р н о й кривой, если r?(t) ? 0 в каждой ее точке. Т.е. в каждой точке кривой существует касательная к ней и эта касательная меняется непрерывно. Единичный вектор касательной равен:

. Если для кривой существует вторая r?(t) призводная от векторной функци, то определен вектор, задающий кривизну

Примечание! Модуль вектора кривизны характеризует степень отклонения кривой от прямой линии. В частности, если g — отрезок прямой, то К = 0.

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