Лекція 4

Моделювання кривих

1. Апроксимація та інтерполяція.

У цій лекції розглядатимуться питання побудови кривих по контрольних точках. Нас цікавитимуть два завдання:

Інтерполяція - побудова кривої, що проходить через контрольні точки

Апроксимація - наближення кривої (не обов'язково проходить точно через задані точки, але задовольняє деякій заданій властивості щодо цих точок)

2. Інтерполяція

Загальна постановка задачі:

Рис. 1. Постановка завдання

Дано: . i  . Побудувати функцію f(x), що задовольняє цій умові.

2.1. Інтерполяційний многочлен Лагранжа

;

;

Одержуємо безперервну функцію, що проходить через всі точки

Недоліки:

1) Вимагає значних обсягів обчислень для знаходження значення функції в довільній точці.

2) Невизначена поведінка побудованої функції між вузлами, зокрема можна привести наступні результати:

1916 Бернштейн :

1925 Рунге :

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

2.2. Кусково-лінійна інтерполяція

Рис. 1. Кусково-лінійна інтерполяція

Интерполяция следующей кусочно-линейной функцией: Клас

2.3. Кубічна інтерполяція Ерміта (форма Ерміта)

Рис. 2. Кубічна інтерполяція Ерміта.	Задано наступні умови: ,
Для кожного i шукатимемо функцію у вигляді . Підставивши цю функцію в рівняння умов одержимо лінійну невироджену систему з 4 рівнянь з 4 невідомими (а, b, c та d), тобто рішення існує і єдино. Клас

Эта система решается относительно нахождением обратной матрицы размером .

.

Здесь - эрмитова матрица, - геометрический вектор Эрмита. Подставим выражение для нахождения : . Аналогично для остальных координат: ,

Проблеми:

1. Необхідно знати вектори похідних (напрям + значення)

2. Бажано мати , а не тільки

2.3. Сплайни

Сплайн кусковий поліном ступеня K з безперервною похідною ступеня K-1 в точках з'єднання сегментів.

Далі будемо розглядати кубічні сплайни.

Поняття сплайна прийшло з машинобудування, де сплайном називали гнучку лінійку, закріпивши яку в потрібних місцях, добивалися плавної кривої, яку потім креслили по цій лінійці (див. рис. 4).

Форма такої лінійки, якщо її розглядати як функцію у(x), задовольнятиме рівнянню Эйлера-Бернуллі: , де M(x) - момент вигину уздовж рейки, E - модуль Юнга, залежний від властивостей матеріалу рейки, I - момент інерції, визначуваний формою кривої. Якщо ми фіксуємо деякі точки підпорами, то момент вигину на кожному відрізку змінюється за лінійним законом: M(x) = A*x + B , підставляючи в початкове рівняння одержуємо:

, двічі інтегруючи одержуємо рівняння кривої на даному відрізку:

Рис. 3. Сплайн.

; таким чином форма фізичного сплайна описується шматковим кубічним поліномом. Розглянемо завдання побудови системи таких кубічних поліномів для всього відрізка

1. Для N відрізків маємо 4N коефіцієнтів: для ;

2. Умова ( i  ) дає 2N рівнянь;

3. Вимога в точках ( i  ) дає N-1 рівняння;

4. Вимога в точках ( i  ) дає N-1 рівнянь.

Всього маємо 4N-2 рівнянь; для того щоб система була визначеною, необхідно ще 2 рівняння; їх можна вивести, наприклад, із заданих значень похідних на граничних точках або із умови періодичності. При коректно заданих умовах лінійна відносно система має єдинее рішенння.

Усі форми реалізуються параметоричним методом. Якщо - незалежний параметр, такий що . Кубічним параметричним сплайном називають наступну систему рівнянь:

Ермітова матриця

.

де - ермітова матриця, - геометричний вектор Ерміта.

.

,

3. Апроксимація

3.1. Криві Безьє

Для задач апроксимації найширше застосовуються криві Безье. Це пов'язано з їх зручністю як для аналітичного опису, так і для наочної геометричної побудови (стосовно комп'ютерної графіки це означає, що користувач може задавати форму кривої інтерактивно, тобто рухаючи опорні точки курсором на екрані ).

Наочний метод побудови цих кривих був запропонований de Casteljau в 1959 році. Побудуємо криву по 3 опорним точкам (Мал. 5). Метод de Casteljau заснований на розбитті відрізків, що сполучають початкові точки відносно t (значення параметра), а потім в рекурсивному повторенні цього процесу для одержаних відрізків.

Рис. 4. Крива Безьє з трьома опорними точками

Позначимо опорні точки як , , початок кривої в точці (t=0), а кінець в точці (t=1), для кожного найдем точку , таким чином, отримаємо криву другого порядку.

Аналогічно побудуємо криву Безьє з 4 опорними точками.

Рис. 5. Крива Безьє з 4 опорними точками

Можно продолжать подобные построения и для большего числа узлов, получая аналогичные выкладки. Запишем общее аналитическое представление для кривой Безье с N+1 опорной точкой:

, где , где - биномиальные коэффициенты,

называются базисными многочленами Бернштейна n степени (а также весовыми функциями Безье/Бернштейна). На рисунках ниже изображены многочлены Бернштейна 3 и 4 степеней

Рис. 6. Базисные функции Бернштейна для кривой Безье с 3 опорными точками.

Рис. 7. . Базисные функции Бернштейна для кривой Безье с 4 опорными точками.