![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Алгоритми заповнення областейДля заповнення областей, обмежених замкнутою лінією, застосовуються два основних підходи: затравочное заповнення й растрове розгорнення. Методи першого типу виходять із того, що задано деяку крапку (запал) усередині контуру й заданий критерій приналежності крапки границі області (наприклад, заданий колір границі). В алгоритмах шукають крапки, сусідні із затравочной і розташовані усередині контуру. Якщо виявлено сусідню крапку, що належить внутрішньої області контуру, то вона стає затравочной і пошук триває рекурсивно. Методи растрового розгорнення засновані на скануванні рядків растра й визначенні, чи лежить крапка усередині заданого контуру області. Сканування здійснюється найчастіше "зверху долілиць", а алгоритм визначення приналежності крапки заданої області залежить від виду її границі. Спочатку розглянемо простий алгоритм заповнення із запалом з використанням стека. Під стеком у цьому випадку ми будемо розуміти масив, у який можна послідовно поміщати значення й послідовно витягати, причому витягають елементи не в порядку надходження, а навпаки: за принципом "першим прийшов - останнім пішов" ("first in - last out"). Алгоритм заповнення виглядає в такий спосіб: Помістити затравочный пиксель у стек Поки стік не порожній: Витягти пиксель зі стека Инициализировать пиксель Для кожного із чотирьох сусідніх пикселей: Перевірити, чи є він граничним і чи був він инициализирован Якщо ні, то помістити пиксель у стек Алгоритм можна модифікувати таким чином, що сусідніми будуть уважатися вісім пикселей (додаються елементи, розташовані в діагональному напрямку). Методи растрового розгорнення розглянемо спочатку в застосуванні до заповнення багатокутників. Найпростіший метод побудови полягає в тому, щоб для кожного пикселя растра перевірити його приналежність внутрішності багатокутника. Але такий перебір занадто неекономічний, оскільки фігура може займати лише незначну частину екрана, а геометричний пошук - завдання трудомістка, сполучена з довгими обчисленнями. Алгоритм стане більше ефективним, якщо попередньо виявити мінімальний прямокутник, у який занурений контур багатокутника, але й этого може виявитися недостатньо. У випадку, коли багатокутник, що обмежує область, заданий списком вершин і ребер (ребро визначається як пара вершин), можна запропонувати ще більш ощадливий метод. Для кожної сканирующей рядки визначаються крапки перетинання з ребрами багатогранника, які потім упорядковуються по координаті На закінчення як приклад приведемо алгоритм зафарбування внутрішньої області трикутника, заснований на складанні повного впорядкованого списку всіх відрізків, що становлять цей трикутник. Для запису горизонтальних координат кінців цих відрізків будемо використовувати два масиви Побудова починається з ініціалізації масивів Якщо тепер послідовно застосувати алгоритм Брезенхема до всім трьох сторонам трикутника, то ми одержимо потрібним образом заповнені масиви границь. Залишається тільки проинициализировать пиксели усередині відрізків Цей алгоритм можна легко поширити на випадок довільного опуклого багатокутника.
Рис. 10.11. Схема побудови растрового розгорнення трикутника Питання й вправи 1. Що таке розкладання в растр? 2. Яка математична основа растрового розкладання в алгоритмі Брезенхема? 3. За яким критерієм инициализируется пиксель у цьому алгоритмі? 4. Чим відрізняються галузі алгоритму при кутах нахилу <45° і >45°? 5. Яку частину окружності досить побудувати, щоб потім шляхом відбиттів одержати окружність цілком? 6. Яку частину еліпса досить побудувати, щоб потім шляхом відбиттів одержати еліпс цілком? 7. Назвіть два типи алгоритмів заповнення областей. 8. Яка структура даних використовується в алгоритмах із запалом? 9. Які дані використовуються при побудові растрового розгорнення трикутника?
|