Растровые алгоритмы построения окружности.

Окружность, как и отрезок, можно построить в лоб, используя математическое представление:

Тогда для каждого значения по оси абсцисс мы сможем вычислить соответствующее ему значение по ординате и поставить точку.

У данного метода существует несколько недостатков:

• Слишком сложные вычисления (операция извлечения корня квадратного)

• Пиксели неравномерно распределяются по окружности, и она оказывается неравномерно освещенной

От второго недостатка можно избавиться, если использовать представление окружности в полярных координатах:

Тогда, пробегая все возможные значения  с заданным шагом, для каждого из них мы определим координаты соответствующего ему пиксела, и закрасим его. На этот раз, т.к. мы каждый раз поворачиваем радиус на один и тот же угол, то пикселы будут равномерно распределены по окружности (рис.5). Однако, как и в предыдущем алгоритме, вычисление операции cos и sin слишком трудоёмки.

Задачу можно значительно упростить, если использовать то, что окружность является центрально-симметричной фигурой, а значит, если построить, к примеру, одну восьмую ее часть, то с помощью преобразования симметрии, можно достроить окружность полностью (рис.6).

Тогда можно использовать метод срединной точки для построения дуги окружности. Если за первый в дуге взять самый верхний пиксел, то следующим может быть лишь Е или SE пиксел. И это справедливо для каждого пиксела в дуге. Если линия проходит выше срединной точки, то следующим пикселом будет E, если ниже – то SE.

Как и в случае отрезка, будем использовать задание окружности в неявном виде с помощью функции F(x,y):

Если F=0, то точка с данными координатами (x,y) расположена на окружности, если больше нуля – то вне окружности. А если меньше нуля – то внутри окружности.

Пусть поставленная точка имеет координаты:

Вычислим значение в соответствующей ей срединной точке:

Если это d меньше нуля, т.е. окружность проходит выше срединной точки, то выбирается пиксел E, иначе выбирается пиксел SE.

Рассмотрим два случая (для двух различных выборов пиксела):

1. Если выбран пиксел E:

2. Если выбрали пиксел SE, то он имеет координаты (x+1,y-1), а значит, соответствующая ему исрединная точка (x+2,y-3/2). И тогда:

Таким образом, начиная с самой первой точки (верхняя точка окружности), мы определяем значение d для каждого нового пиксела, и, сравнив его значение с нулем, строим следующий пиксел в дуге окружности.

Рассчитаем значение d в начальной точке дуги (0,R):

Значение d получается вещественным, что требует использования вещественных операций, которых желательно было бы избежать. Сделав замену h=d-1/4, получим, что h=1-R. Тогда необходимо сравнивать h с -1/4, но так как приращения d – целые числа, то сравнение можно заменить сравнением с нулем.

Построение дуги завершим, когда x станет примерно равен у. Вопрос с граничными точками соединения дуг решается отдельно в каждой реализации. Эти точки могут просто дублироваться.

Лабораторные основы

Цель работы: понять общие принципы построения изображения на примерах использования простейшего алгоритма построения отрезка, окружности и алгоритмов Брезенхема.

В этой работе будет выполнено:

1). рисование отрезка прямой линии, проходящего из точки с координатами ( xl, yl ) в точку с координатами ( х2, у2 ), реализуя простейший алгоритм,

2). рисование отрезка прямой линии, проходящего из точки с координатами ( xl, yl ) в точку с координатами ( х2, у2 ) по алгоритму Брезенхема для отрезка,

3). рисование окружности по простейшему алгоритму,

4). рисование окружности по алгоритму Брезенхема.