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

Будемо міркувати подібно алгоритму Брезенхема для відрізків (з відповідними виправленнями на 4-й октант) [17]. Із двох можливих пікселів в 4-му октанті (відповідних вертикальному й діагональному зсувам, які позначаються аналогічно колишнім s і d, див. мал. 6.10) будемо вибирати той, відстань від окружності до якого менше.

Рис. 6.8. Відстані до окружності.

Для того щоб вибрати один із двох можливих пікселів, будемо порівнювати відстані від них до окружності: де відстань менше - той пиксель і буде знайденим. У прикладі на мал. 6.8 рівняються відстані від крапок S(x_s, y_s) і D(x_d, y_d) до окружності з радіусом R. З евклідової метрики одержуємо:

Але обчислення квадратного кореня - трудомістка операція, тому при досить більших R ми будемо заміняти порівняння відстаней порівнянням наближених значень їхніх квадратів (див. мал. 6.9):

Рис. 6.9. Наближене порівняння відстаней.

Зменшимо два доданки на приблизно однакові величини:

замінимо на ,

замінимо на

одержимо

Таким чином, приблизно

1. D ближче до окружності, чим S

2. S ближче до окружності, чим D

Рис. 6.10. Алгоритм Брезенхема для окружності.

Нехай (x, y) - поточний піксель. Позначимо

Тоді із двох можливих зсувів d і s виберемо.

1. , тобто (x + 1, y + 1) ближче до окружності, чим (x, y + 1):

d: Переходимо в (x + 1, y + 1) і надаємо відповідні збільшення F, ΔF(s), ?F(d):

F = F +?F(d); ?F(s) = ?F(s)+4; ?F(d) = ?F(d)+8.

2. , тобто (x, y+1) ближче до окружності, чим (x + 1, y + 1):

s: Переходимо в (x, y + 1) і надаємо відповідні збільшення F, ΔF(s), ΔF(d):

F = F +?F(s); ?F(s) = ?F(s)+4; ?F(d) = ?F(d)+4.

Якщо ми починаємо з (-R, 0), то початкові значення будуть наступними:

Легко бачити, що в алгоритмі всі величини, пов'язані з F, крім F початкового, будуть кратні 2. Але, якщо ми поділимо всі ці величини на 2 (надалі значення всіх величин уже розуміються в цьому змісті), те . Тому що збільшення F можуть бути тільки цілочисловими, те , де ; тобто якщо відняти від всіх значень, то знак F не зміниться для всіх T, крім T = 0. Для того щоб результат порівняння залишився колишнім, будемо вважати, що F = 0 тепер відповідає зсуву s.

Лістинг 6.5. Алгоритм Брезенхема для окружності

Розмірність обчислень цього алгоритму (тобто відношення максимальних модулів значень величин, з якими він оперує до модулів вихідних даних (у цьому випадку R)) дорівнює 2.