![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Брезенхема для генерации окружности
В растр нужно разлагать не только линейные, но и другие, более сложные функции. Для того чтобы нарисовать окружность необходимо сгенерировать только 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 равна Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пикселя желательно использовать только знак ошибки, а не ее величину. При При δ < 0 расстояние от окружности до диагонального пикселя ( - при δ < 0 выбираем лд в точке (xf +1, у,), - при δ > 0 выбираем /л. в точке (xrf +1, yt -1), - при δ =0, когда расстояние от окружности до обоих пикселов одинаково, выбираем горизонтальный шаг. Если При δ '< 0 расстояние от окружности до вертикального пикселя (х,, у, -1) больше и следует выбирать диагональный шаг к пикселю (x,, y, -1). Напротив, в случае δ '> 0 расстояние от окружности до диагонального пикселя больше и следует выбрать вертикальное движение к пикселю (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)
|