Реферат: Алгоритм Брезенхема
d=|(xi +1)2 +(yi )2 -R2 |-|(xi +1)2 +(yi -1)2 -R2 |
При d<0 відстань від кола до діагонального піксела більша, ніж до горизонтального. Навпаки, якщо d>0, відстань до горизонтального піксела більша. Таким чином,
при d<=0 вибираємо mH (xi +1, уi )
при d>0 вибираємо mD (xi +1, уi -1)
При d=0, коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок.
Кількість обчислень, необхідних для оцінки величини d, можна скоротити, якщо помітити, що у випадку 1
(xi +1)2 +(yi )2 -R2 >=0
(xi +1)2 +(yi -1)2 -R2 <0
тому що діагональний піксел (xi +1, у i - 1) завжди лежить всередині кола, а горизонтальний (xi +1, у i ) –поза ним. Таким чином, d можна обчислити за формулою
d= (xi +1)2 +(yi )2 -R2 +(xi +1)2 +(yi -1)2 -R2
Доповнення до повного квадрата члена (yi )2 за допомогою додавання і віднімання – 2yi + 1 дає
d=2 [(xi +1)2 +(yi -1)2 -R2 ]+2yi - 1
У квадратних дужках стоїть по визначенню Di і його підстановка
d= 2 (Di +yi ) – 1
значно спрощує вираз.
Розглянемо випадок 2 на рис. 5.4 і помітимо, що тут повинен бути обраним горизонтальний піксел (xi +1, уi ), тому що у є монотонно спадною функцією. Перевірка компонентів d показує, що
(xi +1)2 +(yi )2 -R2 <0
(xi +1)2 +(yi -1)2 -R2 <0
оскільки у випадку 2 горизонтальний (xi +1, уi ) і діагональний (xi +1, уi -1) піксели лежать усередині кола. Отже, d<0, і при використанні того ж самого критерію, що й у випадку 1, вибирається піксел (xi +1, уi ).
Якщо Di >0, то діагональна точка (xi +1, уi -1) знаходиться поза колом, тобто це випадки 3 і 4 на рис. 5.4. У даній ситуації ясно, що потрібно вибрати піксел (xi +1, уi -1), або (xi , уi -1). Аналогічно розгляду попереднього випадку критерій вибору можна отримати, розглядаючи спочатку випадок 3 і перевіряючи різницю між квадратами відстаней від кола до діагонального mD і вертикального mV пікселів, тобто
d' =|(xi +1)2 +(yi -1)2 -R2 |-|(xi )2 +(yi -1)2 -R2 |.
При d' < 0 відстань від кола до вертикального піксела (xi , уi -1) більша і варто вибрати діагональний крок до піксела (xi +1, уi -1). Навпаки, у випадку d' >0 відстань від кола до діагонального піксела більша і варто вибрати вертикальний рух до піксела (xi , уi -1). Таким чином, при d' <= 0 вибираємо mD (xi +1, уi -1), при d'> 0 вибираємо mV (xi , уi -1).
Тут для випадку d' =0, тобто коли відстані рівні, обраний діагональний крок.
Перевірка компонентів d' показує, що
(xi )2 +(yi -1)2 -R2 >=0
(xi +1)2 +(yi -1)2 -R2 <0
оскільки для випадку 3 діагональний піксел (xi +1, уi -1) знаходиться поза колом, тоді як вертикальний піксел (xi , уi -1) лежить всередині кола. Це дозволяє записати d' у вигляді
d' =(xi +1)2 +(yi -1)2 -R2 +(xi )2 +(yi -1)2 -R2
Доповнення до повного квадрата члена (xi )2 за допомогою додавання і віднімання 2xi +1 дає