Заповнення багатокутника і заливка області

У більшості додатків використовується одне з істотних переваг растрових пристроїв - можливість заповнення областей екрану.

Існує два різновиди заповнення:

· Перша, пов'язана як з інтерактивною роботою, так і з програмним синтезом зображення, служить для заповнення внутрішньої частини багатокутника, заданого координатами його вершин.

· Друга, пов'язана в першу чергу з інтерактивною роботою, служить для заливки області, яка або окреслена кордоном з кодом пікселя, який вирізняється від кодів будь-яких пікселів всередині області, або зафарбована пікселями з заданим кодом;

В даному розділі розглянемо алгоритм заповнення багатокутника. У наступному розділі будуть розглянуті алгоритми заливки області.

Найпростіший спосіб заповнення багатокутника, заданого координатами вершин, полягає у визначенні чи належить поточний піксель внутрішньої частини багатокутника. Якщо належить, то піксель заноситься.

Визначити приналежність пікселя багатокутника можна, наприклад, підрахунком сумарного кута з вершиною на пікселі при обході контуру багатокутника. Якщо піксель всередині, то кут буде дорівнює 360 °. якщо поза - 0 ° (рис.).

Мал. 0.4.1. Визначення приналежності пікселя багатокутника

Обчислення приналежності повинно проводитися для всіх пікселів екрану і так як більшість пікселів швидше за все поза багатокутників, то даний спосіб занадто марнотратний. Обсяг зайвих обчислень в деяких випадках можна скоротити використанням прямокутної оболонки - мінімального прямокутника, яка охоплює об'єкт, що цікавить, але все одно обчислень буде багато. Інший метод визначення приналежності точки внутрішньої частини багатокутника буде розглянуто нижче при вивченні відсікання відрізків за алгоритмом Кірус-Бека.

Реально використовуються алгоритми порядкового заповнення, засновані на тому, що сусідні пікселі в рядку швидше за все однакові і змінюються лише там де рядок перетинається з ребром багатокутника. Це називається когерентністю растрових рядків (рядки сканування Yi. Yi + 1. Yi + 2 на рис.). При цьому досить визначити X-координати перетинів рядків сканування з ребрами. Пари відсортованих точок перетину задають інтервали заливки.

Мал. 0.4.2. Построчная зафарбування багатокутника

Крім того, якщо будь-які ребра перетиналися i-м рядком, то вони швидше за все будуть перетинатися також і рядком i + 1. (Рядки сканування Yi і Yi + 1 на рис. 0.2). Це називається когерентністю ребер. При переході до нового рядка легко обчислити нову X-координату точки перетину ребра, використовуючи X-координату старої точки перетину і тангенс кута нахилу ребра:

(Тангенс кута нахилу ребра - k = dy / dx, так як dy = 1, то 1 / k = dx).

Зміна ж кількості інтервалів заливки відбувається тільки тоді, коли в рядку сканування з'являється вершина.

Облік когерентності рядків і ребер дозволяє побудувати для заповнення багатокутників різні високоефективні алгоритми порядкового сканування. Для кожного рядка сканування розглядаються тільки ті ребра, які перетинають рядок. Вони задаються списком активних ребер (САР). При переході до наступного рядка для пересічних ребер переобчислюють X-координати перетинів. При появі в рядку сканування вершин проводиться перебудова САР. Ребра, які перестали перетинатися, видаляються з САР, а все нові ребра, пересічні рядком заносяться в нього.

Загальна схема алгоритму, динамічно формує список активних ребер і заповнює багатокутник знизу-вгору, наступна:

Підготувати службові цілочисельні масиви Y-координат вершин і номерів вершин.

Спільно впорядкувати Y-координати по зростанню і масив номерів вершин для того, щоб можна було визначити вихідний номер вершини.

Визначити межі заповнення по осі Y - Y_мin і Y_max. Стартуючи з поточним значенням Y_tek = Y_min, виконувати пункти 4-9 до завершення розмальовки.

Визначити число вершин, розташованих на рядку Y_tek - поточної рядку сканування.

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

максимальне значення Y-координати ребра,

приріст X-координати при збільшенні Y на 1,

початкове значення X-координати.

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

За списком активних ребер визначається Y_след - Y-координата найближчій вершини. (Аж до Y_след можна не піклуватися про модифікацію САР а тільки міняти X-координати перетинів рядки сканування з активними ребрами).

У циклі від Y_tek до Y_след:

вибрати зі списку активних ребер і впорядкувати X-координати перетинів активних ребер з рядком сканування;

визначити інтервали і виконати зафарбовування;

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

Перевірити не досягли максимальної Y-координати. Якщо досягли, то заливка закінчена, інакше виконати пункт.

Очистити список активних ребер від ребер, що закінчилися на рядку Y_след і перейти до пункту 4.

У Додатку 5 наведені дві підпрограми заповнення багатокутника - V_FP0 і V_FP1. Перша реалізує даний (найпростіший) алгоритм. Ця програма цілком працездатна, але генерує двох і триразове занесення частини пікселів. Це мало прийнятно для пристроїв виведення типу матричних або струменевих принтерів.

На відміну від V_FP0, в програмі V_FP1 використовується більш складний алгоритм формування списку активних ребер, що забезпечує практично повна відсутність дублювань (рис.).

Мал. 0.4.3. Порівняння алгоритмів заповнення багатокутника

0.4.2 Сортування методом розподіляє підрахунку

Як уже зазначалося, для додатків, пов'язаних в основному з інтерактивною роботою, використовуються алгоритми заповнення області з запалом.

При цьому той чи інший спосіб задається заливається (перефарбовуються) область, код піксела, яким буде виконуватися заливка і початкова точка в області, починаючи з якої почнеться заливка.

За способом завдання області поділяються на два типи:

· Гранично-певні, що задаються своєї (замкнутої) кордоном такий, що коди пікселів кордону відмінні від кодів внутрішньої, перефарбовувати частини області. На коди пікселі внутрішньої частини області накладаються дві умови - вони повинні бути відмінні від коду пікселів кордону та коду пікселя перефарбовування. Якщо всередині гранично-певній галузі є ще одна межа, намальована пікселями з тим же кодом, що і зовнішня межа, то відповідна частина області не повинна перефарбовуватися;

· Внутрішньо-певні, намальовані одним певним кодом пікселя. При заливці цей код замінюється на новий код зафарбовування.

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

Заливається область або її межа - деякий зв'язне безліч пікселів. За способами доступу до сусідніх пікселів області діляться на 4-х і 8-ми зв'язкові. У 4-х зв'язкових областях доступ до сусідніх пікселів здійснюється за чотирма напрямками - горизонтально вліво і вправо і в вертикально вгору і вниз. У 8-ми зв'язкових областях до цих напрямках додаються ще 4 діагональних. Використовуючи зв'язність ми може, рухаючись від точки затравки, досягти і зафарбувати всі пікселі області.

Важливо відзначити, що для 4-х зв'язковий прямокутної області кордон 8-ми связна (рис. А) і навпаки у 8-ми зв'язковий області кордон 4-х связна (див. Рис. Б). Тому заповнення 4-х зв'язковий області 8-ми зв'язковим алгоритмом може призвести до "просочуванню" через кордон і заливанні пікселів в примикає області.

Загалом, 4-х зв'язну область ми можемо заповнити як 4-х, так і 8-ми зв'язковим алгоритмом. Зворотне ж невірно. Так область на рис. а ми можемо заповнити будь-яким алгоритмом, а область на рис. б, що складається з двох прилеглих 4-х зв'язкових областей можна заповнити лише 8-ми зв'язковим алгоритмом.

Мал. 0.5.1. Можливості підключення областей і їх кордонів

З використанням зв'язності областей і стека можна побудувати прості алгоритми зафарбовування як внутрішньо, так і гранично-певній галузі. В [] розглядаються зовсім короткі рекурсивні підпрограми заливки. В [] - дещо довші ітеративні підпрограми.

0.5.1 Простий алгоритм заливки

В даному додатку наведені три процедури заливки гранично-певній галузі з запалом.

Перша процедура - V_FAB4R реалізує рекурсивний алгоритм заповнення для 4-х зв'язковий області відповідний алгоритму, вміщеного в [4].

Друга процедура - V_FAB4 реалізує ітеративний алгоритм заповнення для 4-х зв'язковий області близький до алгоритму, вміщеного в [3].

Характерна особливість таких алгоритмів - дуже великі витрати пам'яті під робочий стек і багаторазове дублювання занесення пікселів. Характерні значення для розміру стека (див. Нижче визначення константи MAX_STK) близько десяти тисяч байт при розмірі близько 70 × 70 пікселів і дуже сильно залежать від розмірів заливається області, її конфігурації та вибору початкової точки. Так, наприклад, для заливки квадрата зі стороною, що дорівнює 65 дискретний, і старті заливки з точки (20,20) щодо кута квадрата потрібно 7938 байт для стека.

Третя процедура - V_FAST реалізує алгоритм порядкового заповнення з запалом гранично-певній галузі, близький до відповідного алгоритму з [3]. Відмінна риса таких алгоритмів - великі обсяги програмного коду, невеликі витрати пам'яті під робочий стек і практично відсутнє дублювання занесення пікселів. Характерні значення для розміру стека (див. Нижче визначення константи MAX_STK) близько сотні байт.

0.17.1 V_FAB4R - рекурсивна заливка 4-x зв'язковий області