Алгоритм Брезенхема построения окружности.
Значительная часть школьного курса геометрии посвящена задачам на построение. Вопросы, связанные с алгоритмами построения геометрических фигур, интересовали еще математиков древности. Более поздние исследования показали их тесную связь с фундаментальными вопросами математики (достаточно вспомнить классические задачи о трисекции угла и квадратуре круга). Появление ЭВМ поставило перед математиками принципиально новые вопросы, которые не могли возникнуть в докомпьютерную эпоху. К их числу относятся задачи построения элементарных графических объектов - линий и окружностей.
Любая геометрическая фигура может быть определена как некоторое множество точек плоскости. В геометрии это множество, как правило, бесконечно; даже отрезок содержит бесконечно много точек.
В компьютерной графике дело обстоит иначе. Элементарная составляющая всех фигур - точка - обретает реальные физические размеры, а вопросы вида "сколько точек содержит данная фигура?" никого не удивляют. Мы попадаем в конечный мир, где все можно сравнить, измерить, подсчитать. Даже само слово "точка" употребляется редко. Его заменяет термин пиксель (pixel - от picture element - элемент картинки). Если взглянуть на экран дисплея сквозь увеличительное стекло, то можно увидеть, что фрагмент изображения, который невооруженному глазу кажется сплошным, на самом деле состоит из дискретного множества пикселей. Впрочем, на дисплеях с невысокой разрешающей способностью это можно наблюдать и без увеличительного стекла.
Пиксель нельзя разделить, так как он является минимальным элементом изображения - не бывает "двух с половиной пикселей". Таким образом, в компьютерной графике мы фактически располагаем целочисленной координатной сеткой, в узлах которой ставятся точки. Во всех алгоритмах, обслуживающих компьютерную графику, должно быть учтено это обстоятельство2.
Имеется и другой аспект проблемы. Допустим, вы хотите съесть яблоко. Имеет ли для вас значение, съедите вы все яблоко целиком или разделите его на 2 половинки и съедите каждую из них отдельно? Скорее всего, если яблоко достаточно вкусное, вы охотно согласитесь на оба варианта. А вот с точки зрения программиста, поделив прекрасное целое яблоко пополам, вы совершаете огромную ошибку. Ведь вместо замечательного целого числа вам приходится иметь дело с двумя дробными, а это значительно хуже. По той же самой причине из двух равенств 1+1=2 и 1,5+0,5=2 программист всегда выберет первое - ведь в нем нет этих непрятных дробных чисел. Такой выбор связан с соображениями повышения эффективности работы программ. В нашем случае, когда речь идет об алгоритмах построения элементарных графических объектов, которые предполагают многократное применение, эффективность является обязательным требованием. Большинство микропроцессоров имеет лишь средства целочисленной арифметики и не располагает встроенными возможностями для операций над вещественными числами. Безусловно, такие операции реализуются, но при этом бывает, что одна операция требует выполнения компьютером до десятка и более команд, что существенным образом влияет на время выполнения алгоритмов.
Статья посвящена рассмотрению одного из шедевров искусства программирования - алгоритму построения окружности, предложенному Брезенхемом (Brezenham). Требуется разработать метод построения окружности на целочисленной координатной сетке по координатам центра и радиусу. Мы должны также максимально сократить время выполнения алгоритма, что заставляет оперировать по возможности целыми числами. Каким графическим инструментарием мы располагаем? Практически никаким. Безусловно, мы должны уметь ставить точку (pixel) в нужном месте экрана. К примеру, языки программирования фирмы Borland содержат процедуру putpixel, с помощью которой можно оставить на экране точку, имеющую нужные координаты и цвет. Цвет для нас значения не имеет, для определенности пусть он будет белым.
1. От чего придется отказаться...
Представим себе, что мы не ограничены в средствах. Что мы не только можем оперировать с дробными числами, но и использовать трансцендентные тригонометрические функции (такое, кстати, вполне возможно на машинах, оснащенных математическим сопроцессором, который берет на себя подобные вычисления). Задача все та же - построить окружность. Что мы станем делать? Вероятно, мы вспомним формулы, параметрически определяющие окружность. Эти формулы достаточно просты и могут быть получены непосредственно из определения тригонометрических функций. Согласно им окружность радиуса R с центром в точке (x0, y0) может быть определена как множество точек M(x, y), координаты которых удовлетворяют системе уравнений
| м | x = x0 + R cos a y = y0 + R sin a, |
где a О [0;2p). |
| н | ||
| о |
Составить программу, реализующую построение окружности по приведенным формулам, совсем не сложно. Мы приведем такую программу на Паскале. При этом воспользуемся процедурами moveto и lineto, первая из которых устанавливает графический курсор на место с указанными координатами, а вторая - проводит линию от текущего положения курсора до точки, координаты которой являются ее параметрами. Использование этих процедур, безусловно, является еще одним отступлением от сформулированных нами правил, но ведь мы уже и так отошли от них, воспользовавшись тригонометрическими функциями.
procedure my_circle(x,y,r:integer);
var alfa: integer;
begin
moveto(x+r,y);
for alfa:=1 to 360 do
{ угол измерятся в градусах }
lineto(round(x+r*cos(alfa*pi/360)), round(y+r*sin(alfa*pi/360)))
{ здесь используется радианная мера углов }
end;
Если вы располагаете временем и достаточно любопытны, то можете попробовать определить время, которое потребуется для изображения, к примеру, тысячи произвольных окружностей с помощью нашей процедуры, и сохранить его с временем, которое понадобится на то же самое с использованием стандартной процедуры circle. Не сомневаемся, что полученные результаты убедят вас в правильности названия этого параграфа. Кроме всего прочего, необходимо сделать следующее замечание: на самом деле мы строим не окружность, а правильный 360-угольник. Весьма вероятно, что в недалеком будущем аппаратные средства позволят добиться такой разрешающей способности дисплеев, что отличие многоугольника от окружности станет заметным на глаз. Что мы станем делать тогда? Уменьшим шаг приращения угла? Это неплохой выход, но такая ситуация обещает повториться. Итак, приведенный алгоритм нас не устраивает. Надо поискать что-нибудь свободное от упомянутых недостатков.
2. Это похоже на фокус...
Математики любят удивлять. Загадайте... умножьте... разделите... сложите... теперь забудьте то, что вы задумали, и назовите первое число, которое вам придет в голову... Вы задумали... Это, конечно, развлечение. Но и настоящая, серьезная математика способна преподносить не менее удивительные сюрпризы. Алгоритм Брезенхема является одним из таких сюрпризов. Ниже приведена реализация этого алгоритма на Паскале. Изучите ее. Убедитесь, что программа действительно работает. Удивитесь, ибо ничего другого вам не остается. В следующем параграфе вас ждет увлекательный разбор алгоритма.
procedure bres_circle(xc,yc,r:interger):
var x,y,d:integer:
procedure sim(x,y;integer);
begin
putpixel(x+xc,y+yc,White);
putpixel(x+xc,-y+yc,White);
putpixel(-x+xc,-y+yc,White);
putpixel(-x+xc,y+yc,White);
putpixel(y+xc,x+yc,White);
putpixel(y+xc,-x+yc,White);
putpixel(-y+xc,-x+yc,White);
putpixel(-y+xc,x+yc,White);
end;
begin
d:=3-2*y;
x:=0;
y:=r;
while(x <= y) do
begin
sim(x,y);
if d<0 then d:=d+4*x+6
else begin
d:=d+4*(x-y)+10;
dec(y)
end;
inc(x)
end;
end;
3. Что у него внутри?
Перед тем как приступить к рассмотрению алгоритма, договоримся о расположении осей координат. Мы привыкли к обычной декартовой системе координат с положительным направлением осей вправо и вверх. Как правило, в графических системах используется другая система координат - с положительным направлением оси ординат вниз и началом координат в левом верхнем углу экрана. Мы станем пользоваться привычной нам системой координат. Преобразование координат в экранные может быть легко осуществлено, но в этом, как вы убедитесь ниже, нет никакой необходимости.
Обратимся к тексту процедуры bres_circle. Она использует процедуру sim, которая, как можно видеть, расставляет восемь точек вокруг точки (xc,yc) (центра нашей окружности). Эта процедура реализует следующее: окружность обладает центром симметрии и бесконечным количеством осей симметрии. Поэтому нет необходимости строить всю окружность, достаточно построить некоторую ее часть и последовательным применением преобразований симметрии получить из нее полную окружность. Мы станем строить 1/8 часть окружности, заключенную в РAOB (рис. 1).
Каждая точка этого фрагмента должна быть еще семь раз отображена с помощью преобразований симметрии для получения полной окружности.
Рис. 1
Кроме того, именно процедура sim отвечает за расположение центра окружности. Главная процедура вполне может считать, что она строит окружность с центром в начале координат.
Приступим к разбору ключевой идеи алгоритма. Пусть мы находимся в некоторой промежуточной фазе построения. Мы только что поставили точку (xi, yi) и теперь должны сделать выбор между точками 1(xi+1, yi-1) и 2(xi+1, y) (рис. 2). (Напомним, что мы строим часть окружности, заключенную в РAOB, следовательно, подняться выше мы не можем и спуститься вниз более чем на одну точку не можем тоже.)
Рис. 2
Реальная окружность может быть расположена относительно точек 1 и 2 одним из пяти способов 1-5. Если мы выбераем точку 1, то тем самым говорим, что (xi+1)2+(yi-1)2» R2. Если же выбераем точку 2, то допускаем, что (xi+1)2+(yi)2» R2. Рассмотрим две погрешности Di1 и Di2:
Di1 = (xi+1)2+(yi-1)2-R2
Di2 = (x1+1)2+(yi)2-R2
и контрольную величинуDi = Di1+Di2. При выборе точки, следующей за (xi, yi), станем руководствоваться следующим критерием:
если Di > 0, выберем точку 1;
если DiЈ 0, выберем точку 2.
Обоснуем разумность такого выбора. Рассмотрим знаки погрешностей Di1 и Di2 и их влияние на знак контрольной величины Di для всех пяти возможных положений окружности.
Для положения 1.
Di1 < 0, Di2 < 0 Ю Di1+Di2 < 0 Ю выбирается 2.
Для положения 2.
Di1 < 0, Di2 = 0 Ю Di1+Di2 < 0 Ю выбирается 2.
Для положения 3 возможны варианты (учитывая, что Di1 < 0, Di2 > 0).
Вариант 3.1. |Di1| і |Di2| Ю Di1+Di2 < 0 Ю выбирается 2.
Вариант 3.2. |Di1| < |Di2| ЮDi1+Di2 > 0 Ю выбирается 1.
Для положения 4.
Di1 = 0, Di2 > 0 Ю Di1+Di2 > 0 Ю выбирается 1.
Для положения 5.
Di1 > 0, Di2 > 0 Ю Di1+Di2 > 0 Ю выбирается 1.
Далее получим выражение для контрольной величины Di
Di = Di1+Di2 = (xi+1)2+(yi-1)2-R2+(xi+1)2+(yi)2-R2 = 2xi2+2yi2+4xi-2yi+3-2R2.
Выражение для Di+1 существенным образом зависит от выбора следующей точки. Необходимо рассмотреть два случая: yi+1 = yi и yi+1 = yi-1.
Di+1 [при yi+1 = yi] = 2x2i+1+2y2i+1+4xi+1-2yi+1+3-2R2 = 2(xi+1)2+2yi2+4(xi+1)-2yi+3-2R2 = Di+4xi+6.
Di+1 [при yi+1 = yi-1] = 2x2i+1+2y2i+1+4xi+1-2yi+1+3-2R2 = 2(xi+1)2+2(yi-1)2+4(xi+1)-2(yi-1)+3-2R2 = Di+4(xi-yi)+10.
Теперь, когда получено рекуррентное выражение для Di+1 через Di, остается получить D1 (контрольную величину в начальной точке.) Она не может быть получена рекуррентно, ибо не определено предшествующее значение, зато легко может быть найдена непосредственно
x1 = 0, y1 = R Ю D11 = (0+1)2+(R-1)2-R2 = 2-2R,
D12 = (0+1)2+R2-R2 = 1
D1 = D11+D12 = 3-2R.
Таким образом, алгоритм построения окружности, реализованный в bres_circle, основан на последовательном выборе точек; в зависимости от знака контрольной величины Di выбирается следующая точка и нужным образом изменяется сама контрольная величина. Процесс начинается в точке (0, r), а первая точка, которую ставит процедура sim, имеет координаты (xc, yc+r). При x = y процесс заканчивается.
Оставить комментарий
Комментарии
d:=3-2*y;
значение y еще не определено.
надо поставить этот оператор ниже, после
y:=r;
Однако, сама статья чудесная и разбор ее доставил мне настоящее удовольствие.
И, создается впечатление, что он годится для более сложных кривых.
Кто нибудь пробовал?
Di+1 [при yi+1 = yi] = 2x2i+1+2y2i+1+4xi+1-2yi+1+3-2R2 = 2(xi+1)2+2yi2+4(xi+1)-2yi+3-2R2 = Di+4xi+6. детальнее, пошагово.
Тірішкі подумав переробив і тепер коло )))
(ще додав колір (водьть останім число від 2 до 15))
procedure my_circle(x,y,r,col:integer);
var alfa: integer;
begin
setcolor(col);
moveto(x+r,y);
for alfa:=1 to 360 do
lineto(round(x+r*cos(alfa*pi/360)), round(y+r*sin(alfa*pi/360)));
moveto(x-r,y);
for alfa:=1 to 360 do
lineto(round(x-r*cos(alfa*pi/360)), round(y-r*sin(alfa*pi/360)));
end;
var alfa: integer;
begin
moveto(x+r,y);
for alfa:=1 to 360 do
lineto(round(x+r*cos(alfa*pi/360)), round(y+r*sin(alfa*pi/360)))
end;
Здесь вроде в строчке for alfa:=1 to 360 do нужно alfa:=0 ставить иначе иногда бывает выколотая точка. Пробывал в режиме 320х200.
"d:=3-2*y;" на d:=3-2*r;