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

Алгоритм Ву — это алгоритм разложения отрезка в растр со сглаживанием. Был предложен У Сяолинем (Xiaolin Wu, отсюда устоявшееся в русском языке название алгоритма) в статье, опубликованной журналом Computer Graphics в июле 1991 года. Алгоритм сочетает высококачественное устранение ступенчатости и скорость, близкую к скорости алгоритма Брезенхема без сглаживания.

Алгоритм

Этот алгоритм закрашивает разные участки отрезка в разные цвета, и за счет этого «сглаживает» неровности.
Горизонтальные и вертикальные линии не требуют никакого сглаживания, поэтому их рисование выполняется отдельно. Для остальных линий алгоритм Ву проходит их вдоль основной оси, подбирая координаты по неосновной оси аналогично алгоритму Брезенхема. Отличие состоит в том, что в алгоритме Ву на каждом шаге устанавливается не одна, а две точки.
Например, если основной осью является Х, то рассматриваются точки с координатами (х, у) и (х, у+1). В зависимости от величины ошибки, которая показывает как далеко ушли пиксели от идеальной линии по неосновной оси, распределяется интенсивность между этими двумя точками. Чем больше удалена точка от идеальной линии, тем меньше ее интенсивность.
Значения интенсивности двух пикселей всегда дают в сумме единицу, то есть это интенсивность одного пикселя, в точности попавшего на идеальную линию. Такое распределение придаст линии одинаковую интенсивность на всем ее протяжении, создавая при этом иллюзию, что точки расположены вдоль линии не по две, а по одной.
Также следует отметить, что этот алгоритм принимает не целые координаты концов отрезка, а вещественные. При изменении координат отрезок, нарисованный алгоритмом Брэзенхема, перемещается резко, скачками.

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

Отрезок по алгоритму Ву будет перемещаться непрерывно. За счет этого можно обеспечивать плавную анимацию при рисовании движущихся изображений.
На рисунках ниже показано, как мы выбираем из множества пикселей пары. В нашем случае прямая лежит ближе к оси OX, чем к OY, поэтому пары состоят из соседних по вертикали элементов. Если бы прямая была ближе к оси OY, то мы бы выбирали пары из соседей по горизонтали.

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

Результат работы алгоритма:

Реализация в псевдокоде (только для линии по x):

function plot(x, y, c) is // рисует точку с координатами (x, y) // и яркостью c (где 0 ≤ c ≤ 1)   function ipart(x) is return целая часть от x   function round(x) is return ipart(x + 0.5) // округление до ближайшего целого   function fpart(x) is return дробная часть x   function draw_line(x1,y1,x2,y2) is if x2 < x1 then swap(x1, x2) swap(y1, y2) end if   dx := x2 — x1 dy := y2 — y1 gradient := dy ÷ dx   // обработать начальную точку xend := round(x1) yend := y1 + gradient × (xend — x1) xgap := 1 — fpart(x1 + 0.5) xpxl1 := xend // будет использоваться в основном цикле ypxl1 := ipart(yend) plot(xpxl1, ypxl1, 1 — fpart(yend) × xgap) plot(xpxl1, ypxl1 + 1, fpart(yend) × xgap) intery := yend + gradient // первое y-пересечение для цикла   // обработать конечную точку xend := round(x2) yend := y2 + gradient × (xend — x2) xgap := fpart(x2 + 0.5) xpxl2 := xend // будет использоваться в основном цикле ypxl2 := ipart(yend) plot(xpxl2, ypxl2, 1 — fpart(yend) × xgap) plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap)   // основной цикл for x from xpxl1 + 1 to xpxl2 — 1 do plot(x, ipart(intery), 1 — fpart(intery)) plot(x, ipart(intery) + 1, fpart(intery)) intery := intery + gradient repeat end function

Загрузка. Пожалуйста, подождите…

Задания к главе «Алгоритмика» (Ответы)


1. Продолжите фразы.

а) Исполнитель – это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
б) Формальный исполнитель – исполнитель, который одну команду выполняет всегда одинаково.
в) Неформальный исполнитель – исполнитель, который одну команду может выполнить по-разному.
г) Управление – это процесс целенаправленного воздействия одних объектов на другие. Исполнители являются объектами управления.
д) Алгоритм – это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решения поставленной задачи.

2. Приведите примеры:
а) неформальных исполнителей:
ученик, программист, врач, собака.
б) формальных исполнителей:
магнитофон, телевизор, компьютер

3. Исполнитель Кулинар предназначен для обжаривания лепёшек. Лепёшка считается готовой, если каждая её сторона жарилась 1 минуту.
Среда исполнителя – сковорода, на которой помещается две лепёшки.
Система команд исполнителя представлена в таблице:

Система отказов исполнителя следующая. Отказ «не понимаю» возникает тогда, когда исполнителю отдают команды «поместить 3», «перевернуть 3» и т.п.; этих команд нет в СКИ исполнителя Кулинар. Отказ «не могу» возникает при попытке поджарить одну сторону дважды. Для исполнителя Кулинар составьте алгоритм:

а) приготовления 4 лепёшек за 4 минуты:
Поместить 1, поместить 2, ждать, перевернуть 1, перевернуть 2, ждать, убрать 1, убрать 2.

б) приготовление 5 лепёшек за 5 минут:
Поместить 1, поместить 2, ждать, перевернуть 1, перевернуть 2, ждать, убрать 1, убрать 2.
Поместить 1, ждать, перевернуть 1, поместить 2, ждать, убрать 1, перевернуть 2, поместить 1, ждать, убрать 2, перевернуть 1, ждать, убрать 1.

4. Собрался Иван Царевич на бой со Змеем Горынычем, трёхглавым и трёххвостым.
«Вот тебе меч-кладенец, — говорит ему Баба Яга. – Одним ударом ты можешь срубить либо одну голову, либо две головы, либо один хвост, либо два хвоста. Запомни: срубишь голову – новая вырастет, срубишь хвост – два новых вырастут, срубишь два хвоста – голова вырастет, срубишь две головы – ничего не вырастет».
Какие удары и в какой последовательности должен наносить Иван Царевич, чтобы как можно быстрее срубить Змею все головы и все хвосты?
Решение задачи представьте в форме таблицы.

5. Внимательно прочитайте текст п. 3.1 «Алгоритм – модель деятельности исполнителя алгоритмов». Почему, по вашему мнению, его так назвали?

6. Охарактеризуйте исполнителя Чертёжник.
Исполнитель Чертёжник предназначен для построения рисунков на координатной плоскости.

7. Составьте для Чертёжника алгоритм рисования равнобедренного треугольника, если известны координаты концов отрезка, являющегося его высотой (4, 1) и (4, 6), а также координаты (2, 1) одной из вершин.

8. Составьте для Чертёжника алгоритм рисования прямоугольника со сторонами, параллельными осям координат, если известны координаты его двух вершин (2, 1) и (7, 5).

9.

Составьте для Чертёжника алгоритм рисования ромба, центр которого находится в точке (5, 5), диагонали параллельны координатным осям, а их длины равны 8 и 4 единицам.

10. Составьте алгоритм управления Чертёжником, в результате выполнения которого на координатной плоскости будет нарисован квадрат, длина стороны которого равна 2 единицам.


11. Составьте алгоритм управления Чертёжником, в результате выполнения которого на координатной плоскости будет нарисован прямоугольник, длины сторон которого равны 3 и 4 единицам.

12. Составьте алгоритм управления Чертёжником, в результате выполнения которого на координатной плоскости будет нарисован произвольный параллелограмм.

13. Составьте алгоритмы рисования изображённых ниже фигур так, чтобы в процессе рисования перо не отрывалось от бумаги и ни одна линия не проводилась дважды.

14. Найдите в тексте п. 3.2 «Управление исполнителем Чертёжник» ответ на вопрос «Благодаря чему Чертёжник способен обучаться?»

15.

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

Оформите в виде процедур алгоритмы рисования букв М, И, Р. Составьте алгоритмы рисования слов МИР, РИМ, МИМ.

16. Разработайте вспомогательный алгоритм для рисования домика. На его основе составьте основной алгоритм рисования улицы из пяти домиков.

17. Приведите пример жизненной ситуации, для описания которой уместно использовать цикл «повторить n раз».
Покраска кузова на заводе.
Уборка урожая на полях.
Скакать на скакалке.
Подтягивание на перекладине.

18. Составьте алгоритмы управления Чертёжником, после исполнения которых будут получены следующие рисунки.

19. Составьте алгоритмы управления Чертёжником, после исполнения которых будут получены следующие рисунки.

20. Придумайте свои задачи для Чертёжника.

21. Охарактеризуйте исполнителя Робот.
Исполнитель Робот действует на прямоугольном клетчатом поле. Между некоторыми клетками поля могут быть расположены стены. Некоторые клетки могут быть закрашены. Робот занимает одну клетку поля.

22. Приведите все алгоритмы из трёх команд, которые переместят Робота из исходного положения в точку Б.

23.

Маша придумала узор для Робота. Коля стёр ровно половину закрашенных клеток. Восстановите рисунок, зная, что он симметричен относительно вертикальной оси. Напишите программу для Робота.

24. Напишите программу, с помощью которой Робот сможет достичь клетки Б во всех трёх лабиринтах.

вправо
вниз
влево
вниз
вправо
вниз
вниз
влево
{reklama}
25. Напишите программу, с помощью которой Робот попадает в клетку Б.

26. Известны два вспомогательных алгоритма Робота:

27. Составьте алгоритмы, под управлением которых Робот закрасит указанные клетки.

28. Приведите пример жизненной ситуации, для описания которой уместно использовать цикл «пока».
Бить врага, пока не сдастся.
Красить забор, пока не закрасится.
Стрелять по мишени, пока не попадёшь.

29. Известно, что где-то правее Робота есть стена.
Начертите блок-схему алгоритма, под управлением которого Робот закрасит ряд клеток до стены и вернётся в исходное положение.

30. Известно, что где-то правее Робота есть закрашенная клетка.
Составьте алгоритм, под управлением которого Робот закрасит ряд клеток до закрашенной клетки и вернётся в исходное положение.

31. Известно, что Робот находится рядом с левым входом в горизонтальный коридор.
Составьте алгоритм, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.

32. Известно, что Робот находится где-то в горизонтальном коридоре. Ни одна из клеток коридора не закрашена.
Составьте блок-схему алгоритма, под управлением которого Робот закрасит все клетки этого коридора и вернётся в исходное положение.

33. В ряду из десяти клеток правее Робота некоторые клетки закрашены:

б) Составьте алгоритм (напишите программу), под управлением которого Робот закрасит клетки на одну выше и на одну ниже каждой закрашенной клетки.

ПОВТОРИТЬ 10 РАЗ
вправо
ЕСЛИ закрашено ТО
вниз
закрасить
вверх
вверх
закрасить
вниз
КОНЕЦ
КОНЕЦ

34. Напишите программу, с помощью которой Робот может попасть в клетку D во всех трёх лабиринтах.

ЕСЛИ слева свободно ТО
влево
вниз
вправо
вниз
вправо
ИНАЧЕ; ЕСЛИ снизу свободно ТО
вниз
вправо
вверх
вправо
вниз
вправо
вверх
ИНАЧЕ; ЕСЛИ справа свободно ТО
вправо
вправо
вправо
вверх
вверх
вверх
влево
вниз
вниз
влево
влево
вверх
вверх
вправо
КОНЕЦ

35. Напишите программу, следуя которой, Робот сможет пройти по коридору от левого нижнего угла поля к правому верхнему. Коридор имеет ширину в одну клетку и тянется в направлении слева-снизу вправо-вверх. Пример возможного коридора изображён на рисунке.

ПОКА сверху свободно ИЛИ справа свободно
ДЕЛАТЬ
ЕСЛИ сверху свободно ТО
вверх
ИНАЧЕ
вправо
КОНЕЦ
КОНЕЦ

36. Внимательно прочитайте текст п. 3.3 «Управление исполнителем Робот». Ответьте на следующие вопросы:
1) Что общего у циклов «повторить n раз» и «пока»?
2) Какие между ними различия?
3) Нужны ли две конструкции для описания повторяющихся действий?

37. Сравните возможности исполнителей Чертёжника и Робота.
Робот более обширная программа, т.к. Чертёжник может только чертить. Робот может использовать цикл «пока», а Чертёжник – «повторить n раз».

38. Выпишите основные понятия главы 3 «Алгоритмика» и дайте их определения.

Исполнитель — человек, группа людей, животное или техническое устройство, способные выполнять заданные команды. Различают неформальных и формальных исполнителей.
Неформальный исполнитель – одну и ту же команду может выполнять по-разному, формальный – всегда одинаково. Для каждого формального исполнителя можно указать круг решаемых задач, среду, систему команд, систему отказов и режимы работы.

Алгоритм – это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной задачи. Алгоритм – модель деятельности исполнителя алгоритмов.
Алгоритм вспомогательный – алгоритм, решающий некоторую подзадачу основной задачи.
Алгоритм линейный – алгоритм, в котором команды выполняются в порядке, в котором они записаны, т.е. последовательно друг за другом.
Система команд исполнителя (СКИ) – перечень всех команд, которые может выполнить конкретный исполнитель.

Цикл (повторение) – форма организации действий, при которой выполнение одной и той же последовательности команд (тела цикла) повторяется, пока выполняется некоторое заранее установленное условие. Если число повторений тела цикла известно заранее, то можно использовать цикл «повторить n раз». Если число повторений тела цикла заранее неизвестно, используют цикл «пока».
Ветвление – форма организации действий, при которой в зависимости от выполнения или невыполнения некоторого условия совершается либо одна, либо другая последовательность действий.

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

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

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi,  Yi), ближайшую к истинной окружности, так чтобы ошибка:

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

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.


Рис. 1: Варианты расположения очередного пиксела окружности

При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) — перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) — перемещение по диагонали, либо Pv = (Xi, Yi-1) — перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный — Pg или диагональный — Pd.

Для определения того, какой пиксел выбрать Pg или Pd составим разность:

И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.

Рассмотрим вычисление di для разных вариантов.

Dg і 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.

Добавив и вычтя (Y-1)2 получим:

В квадратных скобках стоит Dd, так что

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.

Здесь в качестве следующего пиксела могут быть выбраны или диагональный — Pd или вертикальный Pv.

Для определения того, какую пиксел выбрать Pd или Pv составим разность:

Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.

Рассмотрим вычисление si для разных вариантов.

Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.

Добавив и вычтя (X+1)2 получим:

В квадратных скобках стоит Dd, так что

Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.

Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.

С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si Ј 0 также выбираем диагональный пиксел.

Итак:

Dd < 0

di Ј 0 — выбор горизонтального пиксела Pg

di > 0 — выбор диагонального пиксела Pd

Dd > 0

si Ј 0 — выбор диагонального пиксела Pd

si > 0 — выбор вертикального пиксела Pv

Dd = 0

выбор диагонального пиксела Pd.

Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.

1.

Для горизонтального шага к Xi+1, Yi

Xi+1 = Xi + 1
Yi+1 = Yi
Ddi+1 = (Xi+1+1)2 + (Yi+1-1)2 — R2 =
Xi+12 + 2·Xi+1 + 1 + (Yi+1-1)2 — R2 =
(Xi+1)2 + (Yi-1)2 — R2 + 2·Xi+1 + 1 =
Ddi + 2·Xi+1 + 1

2. Для диагонального шага к Xi+1, Yi-1

Xi+1 = Xi + 1
Yi+1 = Yi — 1
Ddi+1 = Ddi + 2 ·Xi+1 — 2 ·Yi+1 + 2

3. Для вертикального шага к Xi, Yi-1

Xi+1 = Xi
Yi+1 = Yi — 1
Ddi+1 = Ddi — 2 ·Yi+1 + 1

В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:

X= 0

Y= R

Dd = (X+1)2 + (Y-1)2 — R2 = 1 + (R-1)2 — R2 = 2*(1 — R)

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

В Приложении приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности.

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

Подробнее см. текст Приложения. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.

Добавить комментарий

Закрыть меню