Алгоритм Брезенхема. Будемо міркувати подібно алгоритму Брезенхема для відрізків (з відповідними виправленнями на 4-й октант) [17]

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

 

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

Для того щоб вибрати один із двох можливих пікселів, будемо порівнювати відстані від них до окружності: де відстань менше - той пиксель і буде знайденим. У прикладі на мал. 6.8 рівняються відстані від крапок S(xs, ys) і D(xd, yd) до окружності з радіусом 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.

x = -r; y = 0; F = 1-r;?Fs = 3;?Fd = 5-2*r; while( x + y < 0){ plot8( x, y ); if( F > 0) { // d: Діагональний зсув F += ?Fd; x++; y++; ?Fs += 2; ?Fd += 4; } else { // s: Вертикальний зсув F += ?Fs; y++; ?Fs += 2; ?Fd += 2; }}

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

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








Дата добавления: 2015-04-03; просмотров: 805; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2022 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.009 сек.