Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Кривые B-spline: Вычисление Коэффициентов

Читайте также:
  1. B-spline: Мотивация
  2. Анализ потребительского выбора (бюджетное ограничение, кривые безразличия, оптимум, эффекты)
  3. Базисные Функции B-spline: Определение
  4. В) Вычисление интервала корреляции;
  5. Векторное произведение двух векторов. Условие коллинеарности векторов. Вычисление площади параллелограмма и треугольника.
  6. Выборка с группированием данных и вычислением функций агрегации
  7. Вычисление выборочных характеристик распределения

Хотя алгоритм de Boor является стандартным способом нахождения точки на кривой B-spline, соответствующей данному u, во многих случаях (напр., интерполяция и аппроксимация кривых) нам действительно нужны коэффициенты. Покажем простой способ сделать это.

Дана фиксированая кривая B-spline степени p, построенная по n+1 контрольным точкам p0, p1, ..., pn, и m+1 узлам u0=u1=...=up=0, up+1, up+2, ..., um-p-1, um-p=um-p+1=...= um=1, нам нужно вычислить коэффициенты N0,p(u), N1,p(u), ..., Nn,p(u) для любого данного u на [0,1]. Простейший способ - это использовать следующее рекурсивное выражение:

Тем не менее, это очень затратный по времени процесс. Чтобы найти Ni,p(u), нам нужно вычислить Ni,p-1(u) и Ni+1,p-1(u). Чтобы найти Ni,p-1(u), нам нужно вычислить Ni,p-2(u) и Ni+1,p-2(u). Чтобы найти Ni+1,p-1(u), нам нужно Ni+1,p-2(u) и Ni+2,p-2(u). Как видите Ni+1,p-2(u) участвует дважды, и, в результате, ее рекурсивные вычисления также повторятся. Когда рекурсия идет вглубь, появляется все больше повторяющихся вычислений. Это очень похоже на рекурсивную версию алгоритма de Casteljau, который обсуждался ранее. Следовательно, скорость вычисления очень мала.

Есть простой способ сделать то же самое. Допустим, u лежит на узловом интервале [uk,uk+1). Важное свойство базисных функций B-spline говорит о том, что базисные функции самое большее p+1 степени не равны нулю на [uk,uk+1), а именно: Nk-p,p(u), Nk-p+1,p(u), Nk-p+2,p(u), ..., Nk-1,p(u), Nk,p(u). По определению, единственная ненулевая базисная функция 0 степени на [uk,uk+1) - это Nk,0(u). В итоге, коэффициенты можно найти из Nk,0(u) в треугольной форме в виде веера:

Так как Nk,0(u) = 1 на узловом интервале [uk,uk+1), а другие базисные функции 0 степени равны нулю на [uk,uk+1), мы можем начать с Nk,0(u) и вычислить базисные функции 1 степени Nk-1,1(u) и Nk,1(u). Из этих двух значений 1 степени можно найти значения базисных функций 2 степени Nk-2,2(u), Nk-1,2(u) и Nk,2(u). Этот процесс повторяется, пока не будут найдены все p+1 ненулевых коэффициента.

В этом вычислении, "внутренние" значения, такие как Nk-1,2(u), имеют как соседа справа сверху (т.e. Nk-1,1(u)), так и соседа справа снизу (т.e. Nk,1(u)); значения на границе, идущей по направлению вправо вниз, такие как Nk-1,1(u) имеют только соседа слева снизу (т.e., Nk,0(u)); а значения на границе, идущей по направлению влево вниз, такие как Nk,2(u) имеют только соседа слева сверху (т.e., Nk,1(u)). Таким образом, значения, находящиеся на границе, идущей по направлению вправо вверх (соотв., вправо вниз), исползуют второй (соотв. первый) член рекурсивного уравнения в определении. Только внутренние значения зависят от обоих членов. Основываясь на этом наблюдении, имеем следующий алгоритм:

Вход: n, p, m, u, и m+1 фиксированных узлов { u0, ..., um }
Выход: Коэффициенты N0,p(u), N1,p(u), ..., Nn,p(u) в [in] N[0], N[1], ..., N[n]
Алгоритм:

Задаем N[0..n] равными 0; // инициализация
If u = u0 then // проверяем особые случаи

N[0] = 1.0;
return

else u = um then

N[n] = 1.0
return

End if

// теперь u между u0 и um

Пусть u лежит на узловом интервале [uk,uk+1);
R[k] := 1.0 // коэффициент 0 степени
for d :=1 to p do // изменяем степень d от 1 до p



Begin

N[k-d] = * N[(k-d)+1]; // только правый член (юго-западный угол)
for i := k-d+1 to k-1 do // вычисляем значения внутри

N[i] := * N[i] + * N[i+1];

N[k] = * N[k]; // только левый член (северо-западный угол)

End

// в массиве N[0..n] нужные коэффициенты.

Вышеизложенный алгоритм не очень эффективен. Его цель - просто и понятно проиллюстрировать смысл вычислений. Массив N[ ] содержит все промежуточные и конечные результаты. Для степени d элемент N[i] хранит значение Ni,d(u), а в конце, N[k-d], N[k-d+1], ..., N[k] содержат все ненулевые коэффициенты. Вычисление начинается с d=1, потому что мы знаем, что единственная ненулевая базисная функция - это Nk,0(u), если u на узловом интервале [uk,uk+1). Внешний цикл изменяет степень d от 1 до p. Первое выражение после begin вычисляет Nk-d,d(u), используя только один член выражения (т.e., его юго-западный сосед в треугольной схеме, Nk-d+1,d-1(u)), внцтренний цикл for вычисляет "внутренние" члены, а последнее выражение во внешнем цикле вычисляет Nk,d(u), используя только один член выражения (т.e., его северо-западный сосед в треугольной схеме, Nk,d-1(u)).

Загрузка...

Если вы хорошо разберетесь в этом аалгоритме, сможете ли вы сделать его более эффективным?


Дата добавления: 2015-10-29; просмотров: 158 | Нарушение авторских прав


Читайте в этой же книге: Объединение Двух Кривых Безье с соблюдением C1-Непрерывности | Соотношение Между Производной и Алгоритмом de Casteljau | Разбиение Кривой Безье | Повышение Степени Кривой Безье | B-spline: Мотивация | Базисные Функции B-spline: Определение | Два Важных Замечания | Влияние Множественных УзлоFF | Множественные Узлы | Кривые B-spline: Определение |
<== предыдущая страница | следующая страница ==>
Кривые B-spline: Важные Свойства| Кривые B-spline: Перемещение Контрольных Точек

mybiblioteka.su - 2015-2021 год. (0.014 сек.)