10.4. ОПРЕДЕЛЕНИЕ МНОГОЧЛЕНА БЕЗЬЕ

Теперь выведем рекуррентное соотношение для многочленов Безье, имеющее наглядную графическую интерпретацию. Перепишем уравнение (10.12) в следующем виде.

воспользуемся уравнением (10.10а) для разбиения суммы в уравнении (10.16) на две и получим

или

Анализ уравнения (10.17) показывает, что члены, заключенные в первой паре квадратных скобок, представляют собой многочлены Безье для точек а члены, заключенные во второй паре квадратных скобок, — многочлен Безье для точек Если обозначить многочлен Безье для точек через то уравнение (10.17) можно переписать так:

или

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

Алгоритм 10.1. Геометрический алгоритм построения многочленов Безье

Обозначения. На каждой итерации старые точки-ориентиры обозначаются через а новые — через каждого от 0 до

(см. скан)

Этот алгоритм можно интерпретировать и графически, поскольку операция, выполняемая на шаге 5, эквивалентна выбору точки на сегменте, соединяющем точки причем ее расстояние от точки равно произведению текущего значения на длину данного сегмента. Так, если то соответствующий сегмент делится на частей и новая точка-ориентир размещается на конце такой части, по порядку отстоящей от старой точки-ориентира.

Рис. 10.4. Геометрический метод построения многочленов Безье при Каждый новый набор гочек-ориентиров определяется как множество точек, расположенных в серединах сторон многоугольника, построенного на предыдущем множестве таких точек Если остается лишь одна точка-ориентир, то это означает, что найдена точка искомой кривой

На рис. 10.4 иллюстрируется геометрический метод построения многочлена Безье для при . Поскольку все векторы — двумерные, для выполнения шага 5 требуется затратить скалярных операций: по одному сложению, вычитанию и умножению на компоненту вектора. В таком случае для выполнения всего алгоритма требуется

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

Еще более быстрый алгоритм можно получить, переписав уравнение (10.12) в следующем виде:

или

Алгоритм 10.2. Построение многочленов Безье по схеме Горнера

(см. скан)

Для определения по значению члена уравнения (10.206), заключенного в квадратные скобки, при условии, что известны значения и биномиальных коэффициентов, требуются восемь скалярных операций. Столько же операций необходимо затратить на вычисление каждого многочлена, заключенного в квадратные скобки и, следовательно, общее число затрачиваемых операций равно причем второй член суммы характеризует число операций, затрачиваемых на вычисление Эта процедура, в сущности, представтяет собой применение схемы Горнера для вычисления многочленов Безье. При малых удобнее пользоваться геометрическим алгоритмом, поскольку его реализация требует небольшого числа вспомогательных операций, однако при больших предпочтительнее схема Горнера. Чтобы увеличить точность решения, лучше использовать уравнение, действенное уравнению (10.20), вычисляя многочлен Безье при В этом случае множитель будет всегда меньше 1. Описанная процедура представлена в виде алгоритма 10.2.

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

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

Рис. 10.5. Иллюстрация геометрического метода построения многочленов Безье при использовании кратных точек-ориентиров

Несложный подсчет показывает, что эта производная равна нулю при , следовательно, коэффициент при достигает максимального значения при Можно также убедиться в том, что значение этого коэффициента быстро уменьшается до 0 при отличных от Итак, для любого значения имеется лишь несколько точек-ориентиров, которые влияют на форму искомой кривой: это точки, для которых близко заданному значению Увеличение кратности точки ведет к расширению диапазона значений в котором данная точка является определяющей для формирования искомой кривой.

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