В математической подполе численного анализа алгоритм де Бура [1] представляет собой полиномиальный и численно устойчивый алгоритм для оценки сплайн-кривых в форме B-сплайна . Это обобщение алгоритма де Кастельжау для кривых Безье . Алгоритм был разработан Карлом Р. де Буром . Были созданы упрощенные, потенциально более быстрые варианты алгоритма де Бура, но они страдают сравнительно более низкой стабильностью. [2] [3]
Вступление
Общее введение в B-сплайны дается в основной статье . Здесь мы обсуждаем алгоритм де Бура, эффективную и численно стабильную схему для оценки сплайновой кривой. на позиции . Кривая построена из суммы B-сплайновых функций умноженный на потенциально векторные константы , называемые контрольными точками,
B-шлицы порядка являются связными кусочно-полиномиальными функциями степени определяется сеткой узлов (в дальнейшем мы всегда используем индексы, отсчитываемые от нуля). Алгоритм Де Бура использует O (p 2 ) + O (p) операций для оценки сплайновой кривой. Примечание: основная статья о B-сплайнах и классические публикации [1] используют другую нотацию: B-сплайн индексируется как с участием .
Местная поддержка
B-сплайны имеют локальную поддержку, что означает, что полиномы положительны только в конечной области и равны нулю в других местах. Формула рекурсии Кокса-де Бора [4] показывает это:
Пусть индекс определить интервал узла, который содержит позицию, . Из формулы рекурсии видно, что только B-сплайны сотличны от нуля на этом интервале узлов. Таким образом, сумма сводится к:
Это следует из что . Точно так же мы видим в рекурсии, что местоположение самого высокого запрошенного узла находится в индексе. Это означает, что любой интервал узлов который фактически используется, должен иметь как минимум дополнительные узлы до и после. В компьютерной программе это обычно достигается путем повторения первого и последнего использованного местоположения узла.раз. Например, для и реальные места узлов , можно было бы проложить вектор узла до .
Алгоритм
С этими определениями мы можем теперь описать алгоритм де Бура. Алгоритм не вычисляет B-сплайн-функции.напрямую. Вместо этого он оценивает через эквивалентную формулу рекурсии.
Позволять быть новыми контрольными точками с для . Для применяется следующая рекурсия:
После завершения итераций у нас есть , означающий, что желаемый результат.
Алгоритм Де Бура более эффективен, чем явное вычисление B-сплайнов. с формулой рекурсии Кокса-де Бора, потому что она не вычисляет члены, которые гарантированно умножаются на ноль.
Оптимизация
Вышеупомянутый алгоритм не оптимизирован для реализации на компьютере. Требуется память для временные контрольные точки . Каждая временная контрольная точка записывается ровно один раз и читается дважды. Путем обращения итерации на (обратный отсчет вместо восходящего), мы можем запустить алгоритм с памятью всего за временные контрольные точки, позволяя повторно использовать память для . Точно так же есть только одно значение используется на каждом шаге, поэтому мы также можем повторно использовать память.
Кроме того, удобнее использовать индекс, отсчитываемый от нуля. для временных контрольных точек. Отношение к предыдущему индексу:. Таким образом, мы получаем улучшенный алгоритм:
Позволять для . Итерация для:
- ( следует вести обратный отсчет)
После завершения итераций результат будет .
Пример реализации
Следующий код на языке программирования Python представляет собой наивную реализацию оптимизированного алгоритма.
def deBoor ( k : int , x : int , t , c , p : int ): "" "Оценивает S (x). Аргументы --------- k: Индекс узлового интервала, который содержит x. x: положение. t: массив позиций узлов, необходимо дополнить, как описано выше. c: массив контрольных точек. p: Степень B-сплайна. "" " d = [ c [ j + k - p ] для j в диапазоне ( 0 , p + 1 )] для r в диапазоне ( 1 , p + 1 ): для j в диапазоне ( p , r - 1 , - 1 ): альфа = ( x - t [ j + k - p ]) / ( t [ j + 1 + k - r ] - t [ j + k - p ]) d [ j ] = ( 1.0 - alpha ) * d [ j - 1 ] + alpha * d [ j ] return d [ p ]
Смотрите также
Внешние ссылки
Компьютерный код
- PPPACK : содержит множество сплайновых алгоритмов на Фортране.
- Научная библиотека GNU : C-библиотека, содержит подбиблиотеку для сплайнов, портированных из PPPACK.
- SciPy : Python-библиотека, содержит подбиблиотеку scipy.interpolate со сплайн-функциями на основе FITPACK.
- TinySpline : C-библиотека для сплайнов с оболочкой C ++ и привязками для C #, Java, Lua, PHP, Python и Ruby
- Einspline : C-библиотека для сплайнов в 1, 2 и 3 измерениях с оболочками Fortran
Рекомендации
- ^ a b C. de Boor [1971], "Пакет подпрограмм для расчета с B-сплайнами", Techn.Rep. LA-4728-MS, Лос-Аламосская научная лаборатория, Лос-Аламос, штат Нью-Мексико; п. 109, 121.
- ^ Ли, ETY (декабрь 1982). «Упрощенная процедура вычисления B-сплайна». Вычислительная техника . Springer-Verlag. 29 (4): 365–371. DOI : 10.1007 / BF02246763 .
- ^ Ли, ETY (1986). «Комментарии к некоторым алгоритмам B-сплайнов». Вычислительная техника . Springer-Verlag. 36 (3): 229–238. DOI : 10.1007 / BF02240069 .
- ^ С. де Бур, стр. 90
Процитированные работы
- Карл де Бур (2003). Практическое руководство по сплайнам, переработанное издание . Springer-Verlag. ISBN 0-387-95366-3.