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

y_i =y_i +1

D_i =D_i +2х_i -2у_i +2

gо to 1

4 finish

Змінна межі встановлюється в нуль для закінчення роботи алгоритму на горизонтальній осі, в результаті генерується коло у першому квадранті. Якщо необхідний лише один з октантів, то другий октант можна отримати за допомогою установки Межа=Integer (R/sqrt(2)), а перший – за допомогою відображення другого октанта відносно прямої у=х (рис. 5.1). Блок-схема алгоритму показана на рис. 5.5.

Блок-схема покрокового алгоритму Брезенхема для генерації кола в першому квадранті

Розглянемо коло радіусом 8 з центром в початку координат. Генерується тільки перший квадрант.

x=0

y=8

=2 (1–8)=-14

Межа=0

Покрокове виконання основного циклу

1 Plot (0,8)

yi>Межа (продовжувати)

Di<0 go to 2

2d=2 (-14)+2 (8) – 1=-13<0 go to 10

10x=0+1=1

Di=-14+2+1=-11

go to 1

1 Plot (1,8)

yi>Межа (продовжувати)

Di<0 go to 2

2d=2 (-11)+2 (8) – 1=-7<0 go to 10

10x=1+1=1

Di=-11+2 (2)+1=-6

go to 1

1 Plot (2,8)

Результати всіх послідовних проходів алгоритму зведені в таблицю. Список пікселів обраних алгоритмів складається з (0,8), (1,8), (2,8), (3,7), (4,7), (5,6), (6,5), (7,4), (7,3), (8,2), (8,1), (8,0).

Plot	Di	d	d'	x	y
-14	0	8
(0,8)
-11	-13	0	8
(1,8)
-6	-7	2	8
(2,8)
-12	3	3	7
(3,7)
-3	11	4	7
(4,7)
1	5	6	5
(6,5)
9	-11	7	4
(7,4)
18	-7	8	2
(8,2)
17	19	8	1
(8,1)
18	17	8	0
(8,0)