В растр нужно разлагать не только линейные, но и другие, более сложные функции.
Для того чтобы нарисовать окружность необходимо сгенерировать только 1/8 часть. Остальные ее части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой y=x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x=0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой y=0 для завершения построения полной окружности (рис.4).
Рис.4. Генерация окружности
Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат (рис.5). Заметим, что если работа алгоритма начинается в точке x=0, y=R, то при генерации окружности по часовой стрелке в первом квадранте y является монотонно убывающей функцией аргумента x. Аналогично, если исходной точкой является точка x=R, y=0, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента y.
Предположим, что центр окружности и начальная точка находятся точно в точках растра, выберем для нашего случая генерацию по часовой стрелке с началом в точке x=0, y=R.
Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксель, наилучшим образом приближающий окружность (рис.6): горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Алгоритм выбирает пиксель, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т.е. минимум из следующих выражений:
,
,
.
Разность между квадратами расстояний от центра окружности до диагонального пикселя () и от центра до точки на окружности R2 равна
.
Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пикселя желательно использовать только знак ошибки, а не ее величину.
При <0 диагональная точка () находится внутри реальной окружности, в этой ситуации следует выбрать либо пиксель (), т.е. , либо пиксель (), т.е. . Далее проверяется разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:
.
При d<0 расстояние от окружности до диагонального пикселя () больше, чем до горизонтального пикселя (). Напротив, если d>0, расстояние до горизонтального пикселя () больше. Таким образом:
- при d£0 выбираем в точке (),
- при d>0 выбираем в точке (),
- при d=0, когда расстояние от окружности до обоих пикселов одинаково, выбираем горизонтальный шаг.
Если >0, то диагональная точка () находится вне окружности. В данной ситуации ясно, что должен быть выбран либо пиксель (), т.е. , либо (), т.е. . Далее проверяется разность между квадратом расстояний от окружности до диагонального пикселя и вертикального пикселов, т.е.
.
При <0 расстояние от окружности до вертикального пикселя () больше и следует выбирать диагональный шаг к пикселю (). Напротив, в случае >0 расстояние от окружности до диагонального пикселя больше и следует выбрать вертикальное движение к пикселю (). Таким образом:
- при £0 выбираем в (),
- при >0 выбираем (),
- здесь в случае =0, т.е. когда расстояния равны, выбран диагональный шаг.
Подведем итог полученных результатов:
<0
d£0 выбираем пиксель () à ,
d>0 выбираем пиксель () à ,
>0
£0 выбираем пиксель () à ,
>0 выбираем пиксель () à ,
=0 выбираем пиксель () à ,
Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг к пикселю (). Обозначим это новое положение пикселов (i+1). Тогда координаты нового пикселя и значение равны:
,
,
Аналогично координаты нового пикселя и значение для шага к пикселю () таковы:
,
,
.
То же самое для шага к пикселю () :
,
,
.
Выполняя частные алгебраические преобразования и используя метод Брезенхема, получим следующий алгоритм: