Алгоритм Брезенхема для генерации окружности

В растр нужно разлагать не только линейные, но и другие, более сложные функции.

Для того чтобы нарисовать окружность необходимо сгенерировать только 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): горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Алгоритм выбирает пиксель, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т.е. минимум из следующих выражений:

Разность между квадратами расстояний от центра окружности до диагонального пикселя () и от центра до точки на окружности R²равна

Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пикселя желательно использовать только знак ошибки, а не ее величину.

При <0 диагональная точка () находится внутри реальной окружности, в этой ситуации следует выбрать либо пиксель (), т.е. , либо пиксель (), т.е. . Далее проверяется разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

При d<0 расстояние от окружности до диагонального пикселя () больше, чем до горизонтального пикселя (). Напротив, если d>0, расстояние до горизонтального пикселя () больше. Таким образом:

- при d£0 выбираем в точке (),

- при d>0 выбираем в точке (),

- при d=0, когда расстояние от окружности до обоих пикселов одинаково, выбираем горизонтальный шаг.

Если >0, то диагональная точка () находится вне окружности. В данной ситуации ясно, что должен быть выбран либо пиксель (), т.е. , либо (), т.е. . Далее проверяется разность между квадратом расстояний от окружности до диагонального пикселя и вертикального пикселов, т.е.

При <0 расстояние от окружности до вертикального пикселя () больше и следует выбирать диагональный шаг к пикселю (). Напротив, в случае >0 расстояние от окружности до диагонального пикселя больше и следует выбрать вертикальное движение к пикселю (). Таким образом:

- при £0 выбираем в (),

- при >0 выбираем (),

- здесь в случае =0, т.е. когда расстояния равны, выбран диагональный шаг.

Подведем итог полученных результатов:

d£0 выбираем пиксель () à ,

d>0 выбираем пиксель () à ,

£0 выбираем пиксель () à ,

>0 выбираем пиксель () à ,

=0 выбираем пиксель () à ,

Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг к пикселю (). Обозначим это новое положение пикселов (i+1). Тогда координаты нового пикселя и значение равны: