7.13. Алгоритм зі списком ребер і прапорцем

Алгоритм, який використовує список ребер і прапорець, є двокроковим. Перший крок полягає в обрисовуванні контура, в результаті чого на кожному скануючому рядку утворюються пари обмежуючих пікселів. Другий крок полягає у заповненні пікселів, що розташовані між обмежуючими. Більш точно алгоритм можна сформулювати в наступному вигляді:

Обрисовування контуру.

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

тобто

х ≤x+1/2≤x_{перетину}

Заповнення.

Для кожного скануючого рядка, що перетинає багатокутник

Всередині = FLASH

For x = 0 (ліва межа) to x=x_max (права межа)

if піксель в точці х має граничне значення

then інвертувати значення змінної Всередині

if Всередині = TRUE then

присвоїти пікселю в х значення кольору багатокутника

else

присвоїти пікселю в х значення кольору фону

end if

neхt x.

Приклад 7.9. Алгоритм, що використовує список ребер і прапорець

Розглянемо застосування даного алгоритму до тестового багатокутника наведеного на рис. 7.23. Спочатку вимальовується контур, результат цього кроку наведений на рис. 7.27,а. Активовані пікселі в точках (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6), (3 , 5), (4, 4), (5, 3), (6, 3), (7, 4), (8, 4), (8, 3), (8, 2), (8, 1 ).

Тоді багатокутник заповнюється. Для ілюстрації цього процесу виділений і показаний рядок 3 на рис. 7.27,б. Для обрисовування контуру на цьому рядку активовані пікселі при х = 1, 5, 6 і 8. Застосування алгоритму заповнення дає наступні результати:

Рис. 7.27. Алгоритм заповнення по ребрах і прапорцеві

Спочатку

Всередині = FALSE

Для х = 0 Піксель − не граничний і Всередині = FALSE, отже, вживати ніяких дій

не потрібно.

Для х = 1 Піксель - межовий, тому змінна Всередині інвертується і отримує

значення TRUE. Змінна Всередині = TRUE, тому пікселю

присвоюється колір або інтенсивність багатокутника.

Для х = 2, 3, 4 Піксель − не граничний і Всередині = TRUE, тому пікселю

присвоюється колір багатокутника.

Для х = 5 Піксель - межовий, тому змінна Всередині інвертується.

Всередині = FALSE, тому пікселю присвоюється фоновий колір.

Для х = 6 Піксель − межовий, тому змінна Всередині інвертується і отримує

значення TRUE. Змінна Всередині = TRUE, тому пікселю присвоюється

колір багатокутника.

Для х = 7 Піксель − не граничний і Всередині = TRUE, тому пікселю

присвоюється колір багатокутника.

Для х = 8 Піксель − межовий, тому змінна Всередині інвертується і отримує

значення FALSE. Мінлива всередині = FALSE, тому пікселю

присвоюється колір фону.

Результат наведений на рис. 7.27,с, а кінцевий результат для всього багатокутника співпадає з результатом роботи алгоритму зі списком ребер.

У даному алгоритмі кожен піксель обробляється лише один раз, так що затрати на ввід/вивід значно менше, ніж в алгоритмі зі списком ребер або алгоритмі з перегородкою. Жоден з цих алгоритмів, якщо вони працюють з буфером кадру, не вимагає побудови, підтримки та сортування будь-яких списків. При програмній реалізації алгоритм з впорядкованим списком ребер і алгоритм зі списком ребер і прапорцем працюють приблизно з однаковою швидкістю. Однак алгоритм зі списком ребер і прапорцем придатний для апаратної або мікропрограмної реалізації, в результаті чого він виконується на один-два порядки швидше, ніж алгоритм з впорядкованим списком ребер. Для простих зображень навіть можлива анімація в реальному режимі часу.