Нахождение точки на Кривой Безье: Алгоритм De Casteljau's

Вслед за построением кривой Безье, следующей важной задачей будет нахождение точки p (u) на кривой по заданному u. Простой вариант - развернуть описание кривой в полную форму f (u) = (f (u), g (u), h (u)) (см. Пример) и подставлять отдельные значения u в это уравнение, чтобы получать f (u). Хот способ найден, но он не является численно стойким (т.е. в процессе вычисления многочленов могут возникать числовые ошибки).

Далее мы запишем номера [number] контрольных точек. То есть, контрольные точки - это 00 для p ₀, 01 для p ₁,..., 0 i для p _i,..., 0 n для p _n. Нули (0) в этих номерах обозначают начальную или 0- ю итерацию. Позже вместо нуля будет 1, 2, 3, и так далее.

Принцип алгоритма de Casteljau's в таком выборе точки C на отрезке AB, чтобы отношение расстояния между A и C к расстоянию между A и B было равно, скажем, u. Найдем способ определить точку C.

Вектор от A до B равен B - A. Так как u - это коэффициент в пределах от 0 до 1, точка C находится в u (B - A). Вводя в рассмотрение положение точки A, получаем C равно A + u (B - A) = (1 - u) A + u B. Таким образом, для данного u, (1 - u) A + u B - это точка C между A и B, причем отношение расстояний между C и A и между A и B равно u.

Смысл алгоритма de Casteljau's таков. Допустим, надо найти p (u), где u в пределах [0,1]. Начиная с первой ломаной, 00-01-02-03...-0 n, на каждом сегменте 0i... 0(i+1) по вышеуказанной формуле находим точки 1i, такие, чтобы отношение расстояний между 0i и 1i и между 0i и 0(i+1) было равно u. В итоге получим n точек 10, 11, 12,...., 1(n -1). Они образуют новую ломаную из n - 1 сегментов.

Я тут написал прогу на Delphi, строит кривые Безье по этому алгоритму. Очень просто. Могу дать исходники 8-). (прим. перев.)

На рисунке выше, u равно 0.4. 10 лежит на отрезке между 00 и 01, 11 - между 01 и 02,..., а 14 - между 04 и 05. Эти новые точки обозначены синим цветом.

Теперь новые точки обозначены 1 i. Проделывая эту операцию с новой кривой, затем с полученной и так далее, получим в итоге одну точку. De Casteljau докаазал, что это - точка p (u) на кривой, соответствующая u.

На рисунке выше показано нахождение точки на кривой, для u =0.4 - это точка 50.

Это - геометрическое представление алгоритма de Casteljau, одно из самых красивых в разработке кривых.

Вычисления

На рисунке показана схема нахождения точки на кривой Безье по алгоритму de Casteljau.

Вход (Input): массив p [0: n ] из n +1 точек и действительное число u
Выход (Output): точка на кривой, p (u)
Используется: массив точек q [0: n ]

for i:= 0 to n do

q [ i ]:= p [ i ]; // сохраняем введенное

for k:= 1 to n do

for i:= 0 to n - k do

q [ i ]:= (1 - u) q [ i ] + u q [ i + 1];

return q [0];

Дата добавления: 2015-10-29