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

Використання визначення D_i приводить вираз до вигляду

d' = 2 (D_i - x_i ) – 1

Тепер, розглядаючи випадок 4, знову зауважимо, що варто вибрати вертикальний піксел (x_i , у_i -1), тому що y є монотонно спадною функцією від х.

Перевірка компонентів d' для випадку 4 показує, що

(x_i +1)² +(y_i -1)² -R² >0

(x_i )² +(y_i -1)² -R² >0

Оскільки обидва піксели знаходяться поза колом. Отже, d' >0 і при використанні критерію, розробленого для випадку 3, відбувається вірний вибір m_V .

Залишилося перевірити тільки випадок 5 на рис. 5.4, який зустрічається, коли діагональний піксел (x_i +1, у_i -1) лежить на колі, тобто D_i =0. Перевірка компонентів d показує, що

(x_i +1)² +(y_i )² -R² >0

(x_i +1)² +(y_i -1)² -R² =0

Отже, d>0 і вибирається діагональний піксел (x_i +1, у_i -1). Аналогічним чином оцінюємо компоненти d' :

(x_i +1)² +(y_i -1)² -R² =0

(x_i +1)² +(y_i -1)² -R² <0

і d' <0, що є умовою вибору правильного діагонального кроку до (x_i +1, у_i -1). Таким чином, випадок D_i =0 підлягає тому ж критерію, що і випадок D_i <0 чи D_i >0. Підіб'ємо підсумок отриманих результатів:

D_i <0

d<=0вибираємо піксел (x_i +1, у_i ) – m_H

d> 0 вибираємо піксел (x_i +1, у_i -1) – m_D

D_i >0

d' <=0 вибираємо піксел (x_i +1, у_i -1) – m_D

d'> 0 вибираємо піксел (x_i , у_i -1) – m_V

D_i =0 вибираємо піксел (x_i +1, у_i -1) – m_D

Легко розробити прості рекурентні співвідношення для реалізації покрокового алгоритму. Спочатку розглянемо горизонтальний крок m_H до піксела (x_i +1, у_i ). Позначимо це нове положення піксела як (i+1). Тоді координати нового піксела і значення D_i рівні

x_i+1 =x_i +1

y_i+1 =y_i

D_i+1 =(x_i+1 +1)² +(y_i+1 -1)² -R² =D_i +2x_i+1 +1

Аналогічно координати нового піксела і значення D_i для кроку m_D до піксела (x_i +1, у_i -1) такі:

x_i+1 =x_i +1

y_i+1 =y_i -1

D_i+1 =D_i +2x_i+1 -2y_i+1 +2