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

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

Для того чтобы нарисовать окружность необходимо сгенерировать только 1/8 часть. Остальные ее части могут быть получены последовательными отражениями. Если сгенерирован первый октант (от 0 до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у=х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х=0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у=0 для завершения построения полной окружности (рис.4).

Рис.4. Генерация окружности

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат (рис.5). Заметим, что если работа алгоритма

Рис.5. Первая четверть окружности

начинается в точке x=0, y=R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргумента дг. Аналогично, если исходной точкой является точка x=R, у~О, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у.

Предположим, что центр окружности и начальная точка находятся точно в точках растра, выберем для нашего случая генерацию по часовой стрелке с началом в точке x=0, y=R.

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

Рис.6. Выбор пикселя при генерации окружности

горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. Алгоритм выбирает пиксель, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т.е. минимум из следующих выражений:

Разность между квадратами расстояний от центра окружности до диагонального пикселя (х, +1, у, -1) и от центра до точки на окружности jR2 равна

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

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

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

- при δ < 0 выбираем лд в точке (xf +1, у,),

- при δ > 0 выбираем /л. в точке (xrf +1, yt -1),

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

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

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

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

Аналогично координаты нового пикселя и значение для шага (x, +1, y, -1) таковы:

То же самое для шага к пикселю (x,, y, -1):

Выполняя частные алгебраические преобразования метод Брезенхема, получим следующий алгоритм:

Procedure Mich_Circle (radius; color, integer);

Var

x, y, d: integer;

Begin

x: =0; y: =radius; d: =3-2* radius

While x< y do begin

CirclePoint (x, у.color); if d< 0 then d: =d+4*x+6 else

begin

d: =d+4*(x-y)+10; y; =7-l

end;

x: =x+l

end;

if x=y then CirclePoint (x, у.color)

End.

Процедура CirclePoint имеет вид;

Procedure CirclePoint (x, у.color: integer); Begin

PutPixel (x, у, color);

PutPixel (y, x, color);

PutPixel (y, -x, color);

PutPixel (-x, -y, color); PutPixel (x, -y, color);

PutPixel (-y.-x, color); PutPixel (-y.x, color); PutPixel (-x.y, color)