Приложение Е. Алгоритм де Кастильо

Алгоритм де Кастильо можно сформулировать следующим образом.

Р(u), координаты точки на кривой Безье при значении параметра, равном и, равны Рnо и вычисляются по следующей рекурсивной формуле-.

Приложение Е.  Алгоритм де Кастильо
где

r= 1....... п ;

i = 0,..., п - r;

Рi° =Рi

а начальные значения Рi° — это координаты задающих точек Рi.

Выражение (Е.1) показывает, что Рi1 вычисляются по Рi°, или что задающие точки Рi2 вычисляются по Рi1 и т. д., пока не будет получено Р0n — значение Р(u). Этот процесс показан на рис. Е.1 для кривой Безье порядка 3 (п = 3). Обратите внимание, что Рo1 получается путем разбиения сегмента линии Р0Р1 на отрезки с отношением длин и : (1 - и), Р11 и Р21 определяются так же. Затем находится Р02, для чего сегмент линии РрР11 разбивается на отрезки с тем же отношением длин, а после этого определяются Р03 или Рon путем аналогичного разбиения сегмента Р02Р,2.∙Р03 дает координаты точки кривой, соответствующей значению параметра и. Как вы помните, значение параметра определяет отношение, в котором разбиваются соответствующие сегменты линии. Рисунок Е.1 показывает также, что исходная кривая Безье состоит из двух кривых Безье: одна определена четырьмя задающими точками Р0, P01 , Р02 и Р03, а другая — Р03, Р12, Р21. и Р3. Проверку этого утверждения можно найти в [48]. Обратите также внимание, что два новых задающих многоугольника аппроксимируют оригинальную кривую Безье гораздо более близко, чем исходный задающий многоугольник. Таким образом, алгоритм де Кастильо может применяться многократно для аппроксимации кривой Безье сегментами прямых линий.

Процесс получения Р0n с помощью формулы (Е.1) иллюстрируется схематически на рис. Е.2. Любая точка Рir определяется верхним левым соседом Рir-1 и левым соседом Рi+1r-1 следовательно, новые точки, создаваемые в процессе рекурсии, образуют нижний треугольник с вершиной в Р0n. Эта схематическая диаграмма содержит дополнительную полезную информацию. Мы показали, что кривая Безье порядка 3 в процессе применения алгоритма де Кастильо может быть разделена на две кривые Безье того же порядка. Эту идею можно распространить на кривую Безье любого порядка. На самом деле две группы точек, окруженные пунктирными линиями, — это задающие точки двух кривых Безье, полученных путем разделения исходной кривой Безье, определенной точками Р0, Р1,.... Рn. Таким образом, кривую Безье любого порядка можно разбить на множество кривых Безье того же порядка, многократно применяя алгоритм де Кастильо, и результирующие задающие многоугольники будут достаточно близко аппроксимировать исходную кривую. Такая аппроксимация прямолинейными сегментами может использоваться для вычисления начальных значений точек пересечения между кривыми Безье. Реализация алгоритма де Кастильо на языке С представлена в листинге Е.1.

С помощью алгоритма де Кастильо можно также вычислить производные кривой Безье. Дело в том, что производная любого порядка от кривой Безье может быть выражена уравнением кривой Безье, как отмечалось в разделе 6.4.1.

Приложение Е.  Алгоритм де Кастильо
 
Приложение Е.  Алгоритм де Кастильо
 
Приложение Е.  Алгоритм де Кастильо
 
Приложение Е.  Алгоритм де Кастильо