С помощью локальных сплайнов

МОДЕЛИРОВАНИЕ ПОВЕРХНОСТЕЙ

И КРИВЫХ ПРИ ПОМОЩИ СПЛАЙНОВ

 

При интерполяции кривых и поверхностей алгебра-ическими полиномами и квадратичными формами с возрас-танием числа геометрических условий растут и их степени. Отличительной особенностью полиномов и квадратичных форм высоких степеней является их осцилляция в про-межутках между узлами интерполирования. Это приводит к тому, что соответствующие кривые и поверхности имеют ”волнистый” вид. Он, как правило, неприемлем для разра-ботчиков по двум причинам: 1) исходный интерпо-лируемый объект имеет довольно гладкую поверхность, 2) образующаяся волнистая поверхность неудовлетво-рительна с эстетической точки зрения. Также многочлены высоких степеней чувствительны к ошибкам вычислений.

С целью устранения этих недостатков для областей, содержащих большое число узлов, используют не один полином (квадратичную форму) высокой степени, а не-сколько таких объектов невысокой степени. Непрерыв-ность таких кусочно-полиномиальных объектов, которые называют сплайнами, и их производных обеспечивается за счёт того, что их составляющие с нужной степенью глад-кости m соединяются между собой в местах стыков. Слу-чай m=0 соответствует непрерывному соединению поли-номов (квадратичных форм) - без разрывов. При m=1 непрерывны первые производные, т.е. в местах соединения углы наклона касательных слева и справа также равны. В основном на практике используют полиномы и квад-ратичные формы нечётных степеней k (чаще всего – 3, реже – 1), имеющие чётное число коэффициентов. Это обусловлено тем, что при однотипных геометрических условиях в краевых точках элементарных участков (отре-зок, прямоугольник) их общее число также чётно. Высокие

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

С помощью сплайновой интерполяции решают раз-личные типы задач. Рассмотрим основные из них.

1. Построение локальных сплайнов.

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

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

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

2. Построение интерполяционных сплайнов.

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

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

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

Следовательно, для их построения необходимо использо-вать методы, отличные от рассмотренных выше методов, применяемых для обычных алгебраических полиномов и квадратичных форм.

 

Интерполирование кривых и поверхностей

с помощью локальных сплайнов

 

У локальных сплайнов на каждом элементарном участке сетки полностью заданы все геометрические усло-вия для построения соответствующего участка сплайна и его форма не зависит от условий на других участках. Рассмотрим более подробно построение локальных сплай-нов по однократным и двукратным узлам.

 

3.1.1. Построение сплайнов по однократным узлам

 

Допустим, плоская кривая у(х) задана набором значе-ний у(x_i) = у_i в узлах x_i (i = 0,1,...,n). Необходимо построить интерполяционный сплайн наименьшей степени, проходящий через узлы x_i: S(x_i) = у_i, (i = 0,1,...,n). Если кривая является пространственной, то наряду с функцией у(х) должна быть задана зависимость z(x). Задача интерпо-лирования по оси z решается точно так же, как и по оси у.

Рассмотрим отрезок [x_i,x_i+1]. В его граничных точках заданы по одному геометрическому условию: у(x_i) = у_i, у(x_i+1) = у_i+1. Поскольку узлы являются однократными, то наименьшая степень полинома S_i+1(x) (i = 0,1,...,n-1) равна единице. Как показано в Разделе 2 (2.11),интерполяцион-ный многочлен Лагранжа для S_i+1(x) имеет вид:

S_i+1(x)= у_i (x_i+1 –x)/(x_i+1 -x_i)+ у_i+1 (x-x_i) /(x_i+1 -x_i ). (3.1 а)

В векторной форме:

S_i+1(x) = (`Ф(x),`Y);

`Ф(x) = ((x<sub>i+1</sub> –x) / (x<sub>i+1</sub> -x<sub>i</sub>), (x-x<sub>i</sub>) / (x<sub>i+1</sub> -x<sub>i</sub> ));`Y= (у_i, у_i+1).

Переходя к безразмерной переменной t=(x-x_i) / (x_i+1 -x_i), у которой t(x_i)=0; t(x_i+1)=1, для функций Лагранжа и полинома S_i+1(t) получим следующие выражения:

(3.1.б)

Одномерный сплайн рассмотренного вида является ломаной, приближённо заменяющей исходную кривую.

Интерполирование двухмерными сплайнами поверх-ностей по однократным узлам производится аналогично. Допустим, поверхность z(x,у), которая задана набором зна-чений z(x_i,у_j) = z_{i j} в узлах двухмерной сетки (x_i,у_j) (i = 0,1,...,n; j=0,1,...,m). Необходимо построить интерполяци-онный сплайн S(x,y) наименьшей степени, проходящий че-рез узлы (x_i,у_j): S(x_i,у_j) = z_{i j} (i = 0,1,..., n; j = 0,1,..., m).

Рассмотрим прямоугольный участок сетки [x_i,x_i+1]´ [у_j, y_j+1]. В его граничных точках заданы по одному геомет-рическому условию: z(x_i,у_j)= z_ij, z(x_i+1 ,у_j) =z_{(i+1) j}, z(x_i, у_j+1)= z_{i (j+1)} , z(x_i+1 ,у_j+1) =z_(i+1)(j+1) . Минимальные степени квадратичной формы S_(i+1),_(j+1)(x,y) по переменным х,у рав-ны единице. Как показано в Разделе 2 (2.22), явное реше-ние для S_(i+1),_(j+1)(x,y) при помощи функций Лагранжа имеет вид:

S_(I+1),(j+1) (x,y) =`Ф(x) Z`Ф(у); (3.2 а)

`Ф(x)=((x_i+1 –x) / (x_i+1 -x_i), (x-x_i) / (x_i+1 -x_i));

`Ф(у)=((y_j+1 –y) / (y_j+1 -y_j), (y-y_j) / (y_j+1 -y_j));

Переходя, как и в одномерном случае, к безразмер-ным переменным t_х= (x - x_i)/(x_i+1 - x_i) и t_у = (у - y_j)/ (y_j+1 - y_j)

и используя матрицу М_Л, решение для S_(i+1),_(j+1)(x,y) можно представить в виде:

Построенный двухмерный сплайн S(x,y)={ S_(i+1),_(j+1)(x, y), (i = 0,1,..., n-1; j = 0,1,..., m-1) } задаёт множество про-странственных четырёхугольников (в общем случае – не-плоских), заменяющих исходную поверхность z(x,у) таким образом, что они совпадают с заданными значениями в уз-лах интерполирования (x_i,у_j).

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

 

3.1.2. Интерполирование по двукратным узлам

 

Для того, чтобы построить с помощью локальных сплайнов кривые и поверхности, обладающие гладкостью 1-й степени (непрерывностью первой производной), необ-ходимо использовать интерполирование по двукратным узлам. Допустим, в узлах x_i, (i = 0,1,...,n) наряду со значениями у(x_i)=у_i заданы величины первых производных у ¢ (x_i) = у ¢ _i некоторой функции у(x), описывающей кривую. Требуется построить сплайн S(x) минимально возможной степени, для которого S(x_i) = у_i, S ¢ (x_i) = у ¢ _i (i = 0,1,...,n).

Рассмотрим отрезок [x_i,x_i+1]. В его граничных точках заданы по два геометрических условия: у(x_i) = у_i, у¢(x_i) = у¢_i, у(x_i+1) = у_i+1, у¢ (x_i+1) = у¢_i+1. Введём на отрезке [x_i,x_i+1] нормированную переменную t= (x – x_i) / (x_i+1 - x_i) и обозначим h_i+1 = x_i+1 - x_i. В Разделе 2 (2.17) дано явное решение для S_(i+1)(t) при помощи кубического интерполя-ционного многочлена Эрмита:

S_(i+1)(t)=у_ij_1i (t)+у_i+1j_2i (t)+h_i+1 у¢_ij_3i (t)+h_i+1 у¢_i+1j_4i (t), (3.4 а)

где j_1i(t),j_2i(t),j_3i (t),j_4i (t) - полиномы Эрмита.

Используя матрицу М_Э, задающую переход от сте-пенного вектора `Т <sup>3</sup> к вектору значений полиномов Эрмита, и расширенный вектор ` Y ^*=(у_i, у_i+1, h_i+1 у¢_i, h_i+1 у¢_i+1), искомый многочлен Эрмита можно представить в виде:

S_(i+1)(t)=( ` Y <sup>*</sup>, М<sub>Э</sub>`Т ³). (3.4 б)

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

Рассмотрим интерполирование поверхностей по дву-кратным узлам двухмерными сплайнами. Пусть поверх-ность z(x,у) заданав узлах двухмерной сетки (x_i,у_j) (i = 0,1,..., n; j = 0,1,..., m) наборами значений z(x_i,у_j) = z_{i j}, а также частными производными по x, у: z¢_х (x_i, у_j) = z^х_{i j}, z¢_у (x_i, у_j) = z^у_{i j} и смешанной z¢¢_ху (x_i, у_j) = z^ху_{i j}.

Требуется построить двухмерный сплайн S(x,у) мини-мально возможной степени, у которого бы для составляю-щих его квадратичных форм S_(i+1)(j+1)(x,у) выполнялись следующие равенства:

S_{(i+1) (j+1)} (x_i,у_j)=z_{i j}; S¢_{(i+1) (j+1)х} (x_i, у_j) = z^х_{i j}, S¢_{(i+1) (j+1) у} (x_i,у_j) = z^у_{i j}, S¢¢_{(i+1) (j+1)ху} (x_i,у_j) =z^ху_{i j}, (i = 0,1,...,n-1; j =0,1,...,m-1),

т.е. в узлах совпадали бы не только значения, но и первые и смешанная производные исходной функции z (x,у).

Как и в случае однократных узлов, рассматриваем прямоугольный участок сетки [x_i,x_i+1]´ [у_j,y_j+1]. В его граничных точках заданы значения функции z(x, у) и её первые производные. Переходя, как и в одномерном слу-чае, к безразмерным переменным t_х=(x-x_i)/h_хi и t_у =(у-y_j)/h_yj ( где h_хi = x_i+1 - x_i, h_yj = y_j+1 -y_j), и используя матрицу М_Э, решение для S_{(i+1) (j+1)} (x,y) можно представить в виде:

где ` Т<sub>х</sub><sup>3</sup> и ` Т_у³ - степенные векторы переменных t_х и t_у,

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

 

123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: