Введение

Метод вычисления сплайн-кривых

В математической области численного анализа алгоритм де Бура — это полиномиальный по времени и численно устойчивый алгоритм для вычисления сплайн-кривых в B-сплайновой форме. Он является обобщением алгоритма де Кастельжо для кривых Безье. Алгоритм был разработан немецко-американским математиком Карлом Р. де Буром. Были созданы упрощённые, потенциально более быстрые варианты алгоритма де Бура, но они характеризуются сравнительно низкой устойчивостью.

Введение

В основной статье приводится общее введение в B-сплайны. Здесь мы обсуждаем алгоритм де Бура – эффективный и численно устойчивый метод вычисления значения сплайн-кривой в заданной точке. Кривая строится как сумма B-сплайнов, умноженных на потенциально векторные константы, называемые контрольными точками. B-сплайны порядка *k* представляют собой кусочно-полиномиальные функции степени *k-1*, определенные на сетке узлов (далее мы всегда будем использовать нулевую индексацию). Алгоритм де Бура использует O(*p*²) + O(*p*) операций для вычисления значения сплайн-кривой. Примечание: в основной статье о B-сплайнах и в классических публикациях используется другая нотация: B-сплайн индексируется как *N<sub>i,k</sub>*, где *i* ≥ 0.

Местная поддержка

B-сплайны обладают локальной поддержкой, что означает, что полиномы отличны от нуля только на конечном участке и равны нулю вне его. Формула рекурсии Кокса — де Бура это демонстрирует:

Пусть индекс *i* определяет интервал узлов, содержащий заданную позицию. Из формулы рекурсии видно, что ненулевыми для этого интервала узлов являются только B-сплайны с *i*. Таким образом, сумма сводится к:

Из этого следует, что аналогично, из рекурсии видно, что максимальный запрошенный индекс узла равен *k*. Это означает, что любой фактически используемый интервал узлов должен иметь как минимум *k* дополнительных узлов до и после. В компьютерной программе это обычно достигается путем повторения начального и конечного используемых узлов *k* раз. Например, для *k* и заданных узлов, вектор узлов дополняется до .

Алгоритм

С помощью этих определений мы можем теперь описать алгоритм де Бура. Алгоритм не вычисляет B-сплайны напрямую. Вместо этого он вычисляет их значения, используя эквивалентную рекуррентную формулу. Пусть — новые контрольные точки, где для . Для применяется следующая рекурсия:

После завершения итераций мы получаем , что означает, что является искомым результатом. Алгоритм де Бура более эффективен, чем прямое вычисление B-сплайнов с использованием рекуррентной формулы Кокса — де Бура, поскольку он не вычисляет слагаемые, которые гарантированно умножаются на ноль.

Оптимизация

Вышеуказанный алгоритм не оптимизирован для реализации на компьютере. Он требует памяти для временных контрольных точек. Каждая временная контрольная точка записывается ровно один раз и считывается дважды. Изменив направление итерации (считая в обратном порядке, а не в прямом), мы можем выполнить алгоритм, используя память только для временных контрольных точек, позволяя повторно использовать память для предыдущей точки. Кроме того, в каждом шаге используется только одно значение , поэтому мы также можем повторно использовать память для него. Более того, удобнее использовать индексацию с нуля для временных контрольных точек. Связь с предыдущим индексом следующая: Таким образом, мы получаем улучшенный алгоритм:

Пусть для итерируйте для :

Обратите внимание, что j необходимо считать в убывающем порядке. После завершения итераций результатом будет .