Реферат: Алгоритм Брезенхема

y=y+1

e=e-1

end while

x=x+1

e=e+Dy/Dx

next i

finish

Блок-схема алгоритму на рис. 3.3. Приклад наведений нижче.

Приклад 3.1. Алгоритм Брезенхема.

Розглянемо відрізок, проведений із точки (0,0) у точку (5,5). Розклад відрізка в растр по алгоритму Брезенхема приводить до такого результату:

початкові установки

x=0

y=0

Dx=5

Dy=5

е=1–1/2=1/2

Результати роботи покрокового циклу

i	Plot	e	x	y
1/2	0	0
1	(0,0)
-1/2	0	1
1/2	1	1
2	(1,1)
-1/2	1	2
1/2	2	2
3	(2,2)
-1/2	2	3
1/2	3	3
4	(3,3)
-1/2	3	4
1/2	4	4
5	(4,4)
-1/2	5	5
1/2	5	5

Блок-схема алгоритму Брезенхема

Результат показаний на рис. 3.4 і збігається з очікуваним. Помітимо, що точка растра з координатами (5,5) не активована. Цю точку можна активувати шляхом зміни циклу for-next на 0 to Dx. Активацію точки (0,0) можна усунути, якщо поставити оператор Plot безпосередньо перед рядком next i.

Результат роботи алгоритму Брезенхема в першому октанті

2. Загальний алгоритм Брезенхема

Щоб реалізація алгоритму Брезенхема була повною необхідно розглянути відрізки у всіх октантах. Модифікацію легко зробити, враховуючи в алгоритмі номер квадранта, в якому лежить відрізок і його кутовий коефіцієнт. Коли абсолютна величина кутового коефіцієнта більше 1, у постійно змінюється на одиницю, а критерій похибки Брезенхема використовується для ухвалення рішення про зміну величини x. Вибір постійно змінюваної координати (на +1 чи -1) залежить від квадранта (рис. 4.1.). Загальний алгоритм може бути оформлений у наступному вигляді:

Узагальнений цілочисельний алгоритм Брезенхема квадрантів передбачається, що кінці відрізка (x1, y1) і (x2, y2) не збігаються усі змінні вважаються цілими Sign – функція, що повертає -1, 0, 1 для від’ємного, нульового і додатнього аргумента відповідно ініціалізація змінних

x=x1

y=y1

Dx=abs (x2-x1)

Dy=abs (y2-y1)