Каждое большое открытие имеет свою предысторию. Мы любим присваивать новым дорогам громкие имена выдающихся людей, и это прекрасно; мало того, это даже почти справедливо. Но все-таки делается это скорее для нашего удобства, нежели в точном соответствии с истиной. Наше историческое сознание невольно оставляет за бортом такие факты, как то, что Колумб был не первым и не единственным, кто ступил на американский берег; что пушкинский “конь ретивый” не заржал бы без “коня Фомы II” Проспера Мериме; что луна над Днепром, написанная Куинджи, осветила дорогу Николая Рериха к вершинам Тибета; или что знаменитый Максимилиан Берлиц был даже не разработчиком одноименного метода обучения иностранным языкам, а всего лишь... заказчиком разработки. Все эти факты верны, хотя они не умаляют ни эффективности метода Берлица, ни красоты рериховских картин, ни величия Колумба, ни гения Пушкина.
Нечто подобное произошло и с кривой Безье. В компьютерной графике эта кривая приобрела не меньшее значение, чем в прикладной механике – эвольвента. В любом распространенном у нас пакете векторной графики (CorelDraw!, Adobe Illustrator и т. п.) есть функция, которая обычно так и называется – Bezier. Форма кривой легко редактируется с помощью, как правило, четырех (двух конечных и двух управляющих) точек на экране, перемещаемых мышью. Однако при всей своей гибкости кривая Безье задает художнику собственный, своеобразный стиль: рисунки, выполненные с ее помощью, кажутся выгнутыми из проволоки.
|
Еще чаще мы сталкиваемся с формулами Безье, даже не подозревая об этом. Они “работают” в компьютерных играх при построении поверхностей и управлении движением. Да что там игры – все контурные шрифты, которыми мы пользуемся в графическом режиме, построены из кривых Безье!
В своей предыдущей статье я позволила себе обратить внимание читателей на важное обстоятельство – с помощью такой кривой можно аппроксимировать сколь угодно сложный контур. В математике подобные утверждения, вообще говоря, надо доказывать; для этого следует обратиться к событиям более чем столетней давности, имевшим место задолго до рождения Пьера Безье.
В 1885 году Карл Вейерштрасс впервые сформулировал и доказал замечательную по своей общности теорему. Вот в каком виде она приводится в современных курсах анализа.
|
Эта формулировка настолько абстрактна, что человеку непривычному она мало что говорит. Да, для любой непрерывной на отрезке функции найдется многочлен, сколь угодно мало отличающийся от данной функции. Но какой именно многочлен имеется в виду, и что за функция, и что, наконец, подразумевается под словами “сколь угодно мало”? Здесь, точно в правовом государстве, разрешено все, что не запрещено. Нет, например, ни слова о наличии у функции производных и об их непрерывности - значит, таковых может и не быть, то есть функции дозволено иметь весьма причудливую форму. Требуется только, чтобы она сама была непрерывной на заданном отрезке. Нет и никаких указаний на то, как построить аппроксимирующий многочлен и определить точность приближения. Не сообщая ничего о средствах достижения цели, теорема Вейерштрасса утверждает лишь то, что цель – обрисовать любую функцию с помощью такого простого инструмента, как полином – в принципе достижима. Именно такие общие результаты определяют развитие науки на годы вперед.
Вопрос о построении аппроксимирующего многочлена и нахождении наименьшего отклонения стал одним из главных в так называемой конструктивной теории функций. Полная определенность и корректность задач вместе с необходимостью преодоления трудностей алгебраического характера – вот что привлекало математиков. Среди них был выдающийся ученый Сергей Натанович Бернштейн.
|
В самом начале двадцатого столетия Бернштейн предложил удивительное доказательство теоремы Вейерштрасса с помощью теории вероятностей. Это доказательство, в отличие от прежних, сразу дает в руки исследователей инструмент для приближенных вычислений: необходимый полином строится в явном виде.
То, что решение задачи аппроксимации пришло именно из теории вероятностей, не должно нас удивлять. Если попытаться изложить суть дела обиходными словами, то функция – это когда что-то от чего-то однозначно зависит. Теория вероятностей тоже изучает зависимости – здесь это зависимости различных событий от условий, их порождающих. Истинный вид такой зависимости не всегда бывает известен, но, выполняя эксперимент, мы фактически получаем функцию в ее приближенном виде.
К примеру, назовем событием А выпадение орла при бросании монеты, а числом х – вероятность этого события. Произведем n независимых опытов, то есть бросков. Если событие А наступило m раз, то мы получили следующее событие: выигрыш F(m/n). Здесь F(x) – данная непрерывная на отрезке [0,1] функция, а F(m/n) – одно из ее значений, которое нам теперь известно.
Вероятность наступления события А m раз равна Cmnxm(1-x)n-m. Действительно, для каждой конкретной последовательности ААААА...А (это форма записи нашего эксперимента, где А – событие, противоположное событию А, то есть “не А” - в данном случае выпадение решки) вероятность того, что событие А приключится m раз, равна xm(1-x)n-m. Множитель Cmn представляет собой число сочетаний из n по m, то есть число возможных подмножеств по m элементов, содержащихся в одном множестве из n элементов. В нашем случае Cmn можно истолковать как число способов, которыми в последовательности экспериментов могут быть выбраны m мест для события А. Например, для трех опытов числа C03, C13, C23 и C33 будут равны 1, 3, 3 и 1 соответственно. Это значит, что есть три способа выбрать одно место из трех (первое, второе или третье) и три способа выбрать по два места (первое и второе, второе и третье, первое и третье). А вот занять все три места сразу, равно как и не занять ни одного, можно только одним способом.
В нашем опыте неважно, в какой последовательности мы получили несколько выпадений орла: эксперимент затевался только ради их количества m. Как следствие, вероятности всех подходящих последовательностей складываются, давая приведенную выше формулу.
Теперь рассмотрим математическое ожидание выигрыша – это сумма произведений всех возможных выигрышей на их вероятности. Итак,
Bn(x) = Snm= 0Cmnxm(1-x)n-m F(m/n).
Перед нами многочлен, аппроксимирующий функцию F(x) на отрезке [0,1]. Чем больше n, тем меньше отклонение этого многочлена от истинной функции, представленной только в виде принадлежащих ей n точек. Иными словами, значение Bn близко к F на заданном отрезке. Это и есть выражение, именуемое многочленом Бернштейна.
Доказательство теоремы Вейерштрасса методом Бернштейна приводится, например, в книге В. Немыцкого, М. Слудской и А. Черкасова “Курс математического анализа”.
Теперь посмотрим на многочлен Бернштейна повнимательнее. Не правда ли, он кое-что нам напоминает?
Впрочем, сходство не слишком-то бросается в глаза, и это совсем не случайно. Крупные компьютерные компании не любят привлекать внимание к самой дорогостоящей части своих разработок - теоретическим основам. Даже в тех случаях, когда фирма не имеет права скрывать их за семью печатями (а перед нами именно такой случай!), она стремится хотя бы несколько их завуалировать. Вот и в документации к программным продуктам Adobe, не особенно читаемой, но все же доступной любопытному взгляду, кривая Безье приведена в частном виде. Но мы сейчас сделаем ее происхождение совершенно очевидным.
Чтобы получить кривую на плоскости, требуется векторный оператор Бернштейна
B(v) = {Bx(t), By(t)}, где 0 <= t <= 1
Если на плоскости заданы точки (x0,y0), (x1,y1) ... (xn,yn), то можно записать его в виде:
Bx(t) = Snm=0 Cmntm(1-t)n-mxm
и
By(t) = Snm=0 Cmntm(1-t)n-mym
Раскроем суммы при n=3. Подставив в выражение для Bx(t) известные нам числа C03, C13, C23 и C33, получим:
Bx(t) = x0(1-t)3 + 3x1t(1-t)2 + 3x2t2(1-t) + x3t3
Приведем уравнение к виду
Bx(t) = axt3+ bxt2+cxt+x0
и выпишем коэффициенты при степенях t:
cx =3(x1 - x0)
bx =3(x0 - 2x1+ x2) = 3(x2 – x1) - cx
ax = x3 + 3x1 – 3x2 – x0 = x3 – x0 – 3[(x2 – x1) + (x1 - x0) – (x1 - x0)] = x3 - x0 - bx - cx
Совершенно аналогично определяются cy, by и ay. Далее см. эпиграф к этой статье. Кривая Безье оказалась переодетым полиномом Бернштейна!
Усатая кривая на экране CorelDraw! является многочленом третьей степени, именно поэтому у нее четыре управляющие точки (x0,y0), (x1,y1), (x2,y2), (x3,y3). Намечая эти точки “мышью”, мы фактически задаем истинный прообраз нашей линии, невидимую кривую-призрак, к которой согласно своей природе и льнет кривая Безье. Из уравнений Бернштейна нетрудно сделать вывод, что аппроксимирующая кривая всегда совпадает с истинной в ее начальной и конечной точках, но совсем не обязательно проходит через все остальные. То же самое мы видим и на экране.
Число управляющих точек для кривой Безье n-го порядка равно n + 1. Кривая четвертого порядка на плоскости имела бы пять управляющих точек и проходила бы ближе к ним; кривая пятого порядка – шесть и так далее. Быть может, для рисования вручную это было бы уже не так интересно. А вот для решения других, самых разнообразных задач сейчас построены новые функции, имеющие в своей основе кривую Бернштейна-Безье.Наконец, приведем способ запрограммировать кривую Безье произвольных степеней:
For r=1 to n do
For i=1 to (n – r) do
bri=(1 – t)br-1i + tbri+1;
где b00, ..., b0n – исходные точки, а bn0(t) – и есть кривая.
Заслуга Пьера Безье заключается не в построении, а в применении знаменитой кривой – что, согласитесь, тоже немало. Ему, как-никак, нужно было найти способ автоматического дизайна корпусов автомобилей “Рено”... Очень сложна и интересна, между прочим, задача построения поверхности по заданным точкам пространства с помощью многочленов Бернштейна. Для построения поверхности потребуются два параметра: с помощью одного мы задаем некоторое количество кривых, а потом с помощью второго формируем из них поверхность. Но это уже другая тема, достойная в будущем отдельного рассказа.
И все-таки название “кривая Бернштейна-Безье” представляется более справедливым, чем общепринятое, хотя в литературе, включая Интернет-публикации, такое название встречается редко. Можем рекомендовать нашим читателям книгу Е.В. Шикина и А.И. Плиса “Кривые и поверхности на экране компьютера (руководство по сплайнам для пользователей)”, М., ДИАЛОГ-МИФИ, 1996, разделы 3.2 и 4.2).