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

Як приклад застосування алгоритму розглянемо гранично-визначену полігональну область, задану вершинами (1, 0), (7, 0), (8, 1), (8, 4), (6, 6), (1, 6), (0,5) і (0, 1). Область зображена на рис.9.1. Затравочний піксел - (4, 3). Область заповнюється піксел за пікселем у порядку, зазначеному на рис.9.1 лінією зі стрілками. Числа, зображені на пікселі, позначають позицію піксела в стеку, яку він займає при роботі алгоритму. Для деяких пікселів таких чисел декілька. Це означає, що піксел поміщали в стек більше 1 разу. Коли алгоритм доходить до піксела (5, 5), стек нараховує 25 рівнів глибини і містить піксели (7, 4), (7, 3), (7, 2), (7, 1), (6, 2), (6, 3), (5, 5), (6, 4), (5, 5), (4, 4),(3, 3), (3, 4), (3, 5), (2, 4), (2, 3), (2, 2), (2, 2), (3, 2), (5, 1), (3, 2), (5, 2), (3, 3), (4, 4), (5, 3).

Тому що всі піксели, які оточують (5, 5), містять або граничні, або нові значення кольору, то жоден з них у стек не поміщається. Отже зі стека виймається піксел (7, 4) і алгоритм продовжує заповнювати колонку (7, 4), (7, 3), (7, 2), (7, 1). При досягненні піксела (7, 1) перевірка знову показує, що навколишні піксели або уже заповнено, або є граничними пікселами. Тому що в цей момент багатокутник цілком заповнений, то вибирання пікселів зі стека до повного його спустошення не викликає появи додаткових пікселів, які варто запам’ятати. Коли стек стає порожнім, алгоритм завершує роботу.

Рис.9.1. Затравочне заповнення за допомогою простого стекового алгоритму\

Багатокутник із прикладу 9.1 є однозв’язною областю, але алгоритм буде правильно заповнювати й області, що містять діри. Це показано в наступному прикладі.

Приклад 9.2. Алгоритм заповнення з запалом для багатокутника з діркою

Як приклад застосування алгоритму розглянемо гранично-визначену область, що містить діру. Вона зображена на рис.9.2. Як і в попередньому прикладі, вершини багатокутника задані пікселами (1, 0), (7, 0), (8, 1), (8, 4), (6, 6), (1, 6), (0,5) і (0, 1). Внутрішня діра визначається пікселами (3, 2), (5, 2), (5, 3), (3, 3). Затравочний піксел - (4, 4). Через діру багатокутник заповнюється не в тому порядку, що у прикладі 9.1. Новий порядок заповнення зазначений на рис.9.2 лінією зі стрілками. Як і в попередньому прикладі, числа в квадратику піксела показують позицію в стеку, займану пікселем. Коли обробка доходить до піксела (3, 1), усі навколишні його 4-зв’язні піксели або вже заповнені, або є граничними. Тому жоден з пікселів не поміститься в стек. Глибина стеку в цей момент дорівнює 15. У стеку знаходяться піксели (7, 1), (7, 2), (7, 3), (6, 5), (7, 4), (6, 5), (3, 1), (1, 2), (1, 3), (1, 4), (2, 5), (3, 5), (4, 5), (5, 4).

Після вибору із стека піксела (7, 1) заповнюється стовпчик (7, 1), (7, 2), (7, 3), (7, 4), при цьому жоден піксел у стек не додається. Для піксела (7, 4) знову всі 4-зв’язні навколишні піксели або вже заповнені, або є граничними. Звертаючись до стеку, алгоритм витягає піксел (6, 5), його заповнення завершує заповнення всього багатокутника. Подальша обробка відбувається без якого-небудь заповнення, і коли стек стає порожнім, алгоритм завершує роботу.

Рис.9.2. Затравочне заповнення області з отвором за допомогою простого стекового алгоритму