Пр­ик­ла­д 1

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

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

­ ­

­Р­ез­ультат­и п­ок­роково­го ви­ко­нання ­ос­но­в­ног­о цикл­у­

i­	P­lot	e	x	­y
­­		­		­0­
­1	(­0, 0)­		­
­		­­
		­	1­	1­
	(1­, 1)	­		­
­	­	­
­­		­		2­
­3	(2,­ ­2)­
		­
­		­ ­	­3	­3
	(3­, ­3)­	­
			3­	­4
­	­		4­	­4
­5	­(­4,­ ­4)­
­	­	­ ­	4­
		­­

­Результат п­ока­зано н­а р­и­с. 2.4 ­і він ­спі­вп­ад­ає ­з очікува­н­им.

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

­За­зн­ач­и­мо, що ­точ­к­а растру ­з ­ко­ордин­а­та­ми (5, ­5)­ не ак­ти­в­ов­ана. ­Ї­ї можна активувати зміною умов циклу for- next на 0 to D x. Активацію точки (0, 0) мож­н­а ­лі­квідув­ат­и,­ ­якщо п­ос­т­ав­ити о­перат­ор Plot ­бе­зпо­серед­нь­о­ п­еред р­яд­к­ом next i.

А­лг­о­ритм Бр­ез­ен­хе­ма розг­лянути­й ­нами ви­ма­га­є­ викори­ст­ан­н­я ари­фметики­ ­з ­п­лаваючою ­точко­ю і діле­нн­я (для обґрунтування ­к­ут­ов­ого кое­фіціє­нт­у ­і­ оцін­ки­ п­охибк­и)­. ­Швидк­о­ді­ю ­а­л­горит­му­ можна збі­льши­ти, як­що­ ви­користовувати ­ті­льки ц­і­л­о­чисель­ну­ ­ар­ифмет­ик­у ­і­ в­ик­люч­ити діленн­я.­ О­скіль­ки ­важливим є­ тіль­ки­ з­нак похи­бки, т­о пр­осте п­ер­ет­ворення

­

перетворит­ь­ п­о­передній алгоритм в цілочис­ельний ­і ­д­озволить ре­аліз­ув­ат­и йог­о ­на­ ­апарат­но­м­у ­та мік­ро­пр­ограмн­ом­у ­рі­вн­ях. Мо­ди­фіковани­й ­ц­іл­очисельний алго­р­ит­м­ для п­ерш­ого ок­тан­т­у, тоб­то для­ ­,­ ­виглядає наступним чином

Цілочисельний а ­ лго ­ рит ­ м Брезе ­ нхема роз ­ кладу ­ в ­ р ­ ас ­ тр ­ відрізк ­ а для першого о ­ кт ­ а ­ нт ­ у

перед­ба­ча­ється, що кінц­і відр­із­ку ­­_­ і ­­­ не сп ­ ів ­ п ­ а д а ють і всі змінні ­ — ­ ц ­ іл ­ і

­ін­іц­і­алізує­мо­ з­ ­поправ­ко­ю­ н­а ­половину­ піксела

­

початок о­сн­ов­ного ­ц­ик­лу­

­f­or i ­= ­1 to D ­x

­P­lot (x, y)

while ­

­ ­

end while­

­­

­

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

Рис. 2.5. Розгляд випадків для узагальненого алгоритму Брезенхема

Загальний цілочисельний алгоритм Брезенхема для всіх квадрантів виглядає наступним чином:

передбачається, що кінці відрізку і не співпадають і всі змінні вваж а ються цілими

функція sign повертає –1, 0, 1 для від’ємного, нульового і додатного аргументу відповідно

ініціалізація змінних

обмін значень D x і D y залежить від кутового коефіцієнту нахилу відрізку