Алгоритми заповнення з приманкою
В алгоритмах, які вище обговорювалися, заповнення відбувається в порядку сканування. Інший підхід використовується в алгоритмах заповнення з приманкою. У них передбачається, що відомо хоча б один піксель із внутрішньої області багатокутника. Алгоритм намагається знайти і зафарбувати всі інші піксели, що належать внутрішній області. Області можуть бути або внутрішньо-, або гранично-визначеними. Якщо область відноситься до внутрішньо-визначених, то всі піксели, які належать внутрішній частині, мають той самий колір або інтенсивність, а всі піксели, зовнішні стосовно області, мають інший колір. Це продемонстровано на рис. 6.12. Якщо область відноситься до гранично-визначених, то всі піксели на межі області мають виділене значення або колір, як це показано на рис. 6.13. Жоден з пікселів із внутрішньої частини такої області не може мати це виділене значення. Проте піксели, які є зовнішніми відносно межі, також можуть мати граничне значення. Алгоритми, які заповнюють внутрішньо-визначені області, називаються внутрішньо-заповнюючими, а алгоритми для гранично-визначених областей — гранично-заповнюючими. Далі будуть обговорюватися гранично-заповнюючі алгоритми, однак відповідні внутрішньо-заповнюючі алгоритми можна одержати аналогічним образом.
Внутрішньо- або гранично-визначені області можуть бути 4- або 8-зв’язними. Якщо область є 4-зв’язною, то будь-якого піксела в області можна досягти за допомогою комбінації рухів тільки в 4-х напрямках: ліворуч, праворуч, вгору, вниз. Для 8-зв’язної області піксела можна досягти за допомогою комбінації рухів у двох горизонтальних, двох вертикальних і 4-х діагональних напрямках. Алгоритм заповнення 8-зв’язної області заповнить і 4-зв’язну область, однак обернене невірно. На рис. 6.14 показані прості приклади 4- і 8-зв’язних внутрішньо-визначених областей. Хоча кожна з підобластей 8-зв’язної області на рис. 6.14, б є 4-зв’язною, для переходу з однієї підобласті в іншу потрібен 8-зв’язний алгоритм. Однак у ситуації, коли треба заповнити різними кольорами дві окремі 4-зв’язні підобласті, використання 8-зв’язного алгоритму викликає неправильне заповнення обох областей тим самим кольором.
Рис. 6.12. Внутрішньо-визначена область
Рис. 6.13. Гранично-визначена область
Рис. 6.14. 4- і 8-зв’язні внутрішньо-визначені області
Рис. 6.15. 4- і 8-зв’язні гранично-визначені області
На рис. 6.15 показана 8-зв’язна область з рис. 6.14, перевизначена у вигляді гранично-визначеної області. На рис. 6.15 ілюструється той факт, що для 8-зв’язної області, у якої дві підобласті стикаються кутами, границя 4-зв’язна, а границя 4-зв’язної області 8-зв’язна. Далі мова в основному піде про алгоритми для 4-зв’язних областей, однак їх можна легко переробити для 8-зв’язних областей, якщо заповнення проводити не в 4, а в 8 напрямках.
Простий алгоритм заповнення з приманкою
Використовуючи стек, можна розробити простий алгоритм заповнення гранично-визначеної області. Стек — це просто масив або інша структура даних, у яку можна послідовно розміщувати значення і з якої їх можна послідовно витягати. Коли нові значення додаються або поміщаються в стек, всі інші значення опускаються вниз на один рівень. Коли значення видаляються або витягаються зі стека, інші значення спливають або піднімаються вгору на один рівень. Такий стек називається стеком прямої дії або стеком з дисципліною обслуговування «першим прийшов, останнім обслугований» (FILO). Простий алгоритм заповнення з приманкою можна представити наступним чином:
Простий алгоритм заповнення з приманкою і стеком
Помістити приманковий піксель у стек
Поки стек не порожній
Витягти піксель зі стека
Присвоїти пікселю необхідне значення
Для кожного із сусідніх до поточного 4-зв’язних пікселів перевірити: чи є він граничним пікселем або чи не присвоєно вже пікселю необхідне значення. Проігнорувати піксель у кожному з цих двох випадків. У протилежному випадку помістити піксель у стек.
Алгоритм можна модифікувати для 8-зв’язних областей, якщо переглядати 8-зв’язні піксели, а не тільки 4-зв’язкові. Наведемо більш формальний виклад алгоритму, у якому передбачається існування приманкового піксела і гранично-визначеної області.