Приклад 9.3. Порядковий алгоритм заповнення з запалом

Розглянемо роботу алгоритму для гранично-визначеної області на рис.9.3. При ініціалізації в стек поміщується затравочний піксел, позначений як Запал (5, 7) на рис.9.3a. Спочатку як запал інтервалу зі стека вибирається цей піксел. Інтервал заповнюється праворуч і ліворуч від запалу. Знайдені при цьому кінці інтервалу Х_прав=9 і Х_лів=1. Потім перевіряється рядок, розташований вище біжучого і виявляється, що він граничний і незаповнений. Крайнім правим пікселем у діапазоні 1<х<9 виявляється піксел (8, 8), позначений цифрою 1 на рис.7.7а. Цей піксел поміститься в стек. Потім аналогічним чином обробляється рядок нижче біжучого. У діапазоні Х_лів<х<Х_прав є два підінтервали на цьому рядку. Для лівого підінтервала як запал виступає піксел (3, 6), позначений цифрою 2 на рис.9.3а, він теж поміститься в стек. Запал для правого підінтервала - піксел (9, 6), він вміщується в стек. Помітимо, що піксел (9, 6) - це не самий крайній правий піксел на інтервалі, однак це самий крайній піксел у діапазоні Х_лів<х<Х_прав, тобто в діапазоні 1<х<9. На цьому завершується перший прохід алгоритму.

Далі зі стека вибирається верхній піксел. Тут заповнюються інтервали, розташовані в правій частині багатокутника на послідовних скануючих рядках (рис.9.3 b, c, d). Для рядка 3 запалом служить піксел (10, 3) (рис.9.3 d). У результаті заповнення інтервалу праворуч і ліворуч від запалу одержуємо нові межі діапазону: Х_лів=1 і Х_прав=10. Обробляючи рядок вище, одержуємо для лівого підінтервала затравочний піксел (3, 4), що вміщується в стек. Правий підінтервал до цього часу уже заповнений. Обробка рядка нижче дає запал (3, 2) для лівого і (10, 2) для правого підінтервалів. Ці піксели також помістяться в стек. Саме зараз досягається максимальна глибина стека для оброблюваного багатокутника.

Після заповнення 4-зв’язних полігональних підобластей із затравочними пікселами 5, 4 і 3 на рис.7.7е зі стека вибирається піксел, позначений цифрою2.

Тут виявляється, що всі піксели на цьому рядку і на сусідніх рядках (вище і нижче) уже заповнені. Таким чином, жоден піксел у стек не поміститься. Зі стека вибирається піксел 1 і рядок обробляється, при цьому знову додаткових пікселів не з’являється. Тепер стек порожній, багатокутник заповнений і робота алгоритму завершена.

Порядок виконання роботи

1. Запрограмувати алгоритм заповнення з запалом.

2. Створити малюнок, у якому би були помічене затравочне заповнення.

3. Здійснити затравку. Результат роботи алгоритму - заливка замкнутої області іншим кольором.

ЗМІСТ ЗВІТУ

1. Назва роботи.

2. Мета роботи.

3. Короткий теоретичний вступ.

4. Завдання до лабораторної роботи.

5. Тексти розроблених і відлагоджених программ.

6. Малюнки з реалізацією програми.

7. Висновки.

НАВЧАЛЬНЕ ВИДАННЯ

КОМП’ЮТЕРНА ГРАФІКА

МЕТОДИЧНІ ВКАЗІВКИ

до виконання лабораторної роботи № 9

Простий алгоритм заповнення з запалом

для студентів бакалаврського рівня підготовки спеціальності

«Комп‘ютерні науки» та «Видавничо-поліграфічна справа»

Укладач: Різник Олег Яремович

Комп’ютерне складання та верcтання: Скрибайло-Леськів Даніель Юрієвич

11