Лекция 3б закраска. Лекция 3b_Закраска (2). Алгоритмы заполнения с затравкой Понятия
 Скачать 0.58 Mb.
|
|
Алгоритмы заполнения с затравкой 1. Понятия. В предыдущих алгоритмах растровой развертки сплошных областей заполнение происходит в порядке сканирования строк. В алгоритмах с затравкой предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритмы пытаются найти и закрасить все другие пикселы, принадлежащие внутренней области. Области могут быть внутренне-определенными и гранично-определенными. 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 Рис. 1. Внутренне-определенная область. Все пикселы, принадлежащие внутренней части, имеют один и тот же цвет, а все пикселы, внешние по отношению к области, имеют другой цвет. 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 Рис. 1.Гранично-определенная область. Все пикселы на границе области имеют выделенное значение или цвет. Ни один из пикселов из внутренней части области не может иметь это выделенное значение. Тем не менее, пикселы, внешние по отношению к границе, также могут иметь граничное значение. Алгоритмы, заполняющие внутренне-определенные области, называются внутренне-заполняющими, а алгоритмы для гранично-определенных областей - гранично-заполняющими. Внутренне- или гранично-определенные области могут быть 4-х или 8-ми связными. Если область 4-х связная, то любого пиксела в области можно достичь с помощью комбинации движений только в четырех направлениях. Налево, направо, вверх, вниз. Для 8-ми связной области пиксела можно достичь с помощью комбинаций движения в двух горизонтальных, двух вертикальных и 4 диагональных направлениях. Алгоритм заполнения 8-ми связной области заполнит и 4-х связную, но не наоборот! 4-х связная область 8-ми связная область Рис. 2. 4-х и 8-ми связные внутренне-определенные области. Рис.3. 4-х и 8-ми связные гранично-определенные области. Для 8-ми связной области, у которой две подобласти соприкасаются углами, граница 4-х связная, а граница 4-х связной области - 8-ми связная. Далее будут рассмотрены алгоритмы для 4-х связных областей. 2. Простой алгоритм заполнения с затравкой. 2.1. Общее описание алгоритма. В алгоритме используется стек. Стек - это массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Когда новые значения добавляются в стек, все остальные значения опускаются вниз на один уровень. Такой стек стек называется стеком прямого действия, или стеком с дисциплиной обслуживания «первый пришел, последний обслужен» (FILO). Поместить затравочный пиксел в стек. Пока стек не пуст Извлечь пиксел из стека Присвоить пикселу требуемое значение Проверить для каждого из соседних к текущему 4-х связных пикселов: является ли он граничным пикселом или не присвоено ли уже пикселу требуемое значение ? Проигнорировать пиксел в любом из этих двух случаев. В противном случае поместить пиксел в стек. 1. Простой алгоритм заполнения с затравкой: Предположим, что затравочный пиксел находится в гранично-определенной области. Некоторые обозначения: Затравка(x,y) - выдает затравочный пиксел. Push - процедура, которая помещает пиксел в стек. Pop - процедура, которая извлекает пиксел из стека. Формальное изложение алгоритма. Пиксел(x,y) = Затравка(x,y) Гран_значение = Цвет1 Нов_значение = Цвет2 Инициализируем стек Push Пиксел(x,y) While (стек не пуст) Извлекаем пиксел из стека Pop Пиксел(x,y) if Пиксел(x,y) <> Нов_значение then Пиксел(x,y) = Нов_значение end if Проверим, надо ли помещать соседние пикселы в стек ? If (Пиксел(x+1,y) <> Нов_значение and Пиксел(x+1,y) <> Гран_значение then Push Пиксел(x+1,y) if (Пиксел(x,y+1) <> Нов_значение and Пиксел(x,y+1) <> Гран_значение then Push Пиксел(x,y+1) if (Пиксел(x-1,y) <> Нов_значение and Пиксел(x-1,y) <> Гран_значение then Push Пиксел(x-1,y) if (Пиксел(x,y-1) <> Нов_значение and Пиксел(x,y-1) <> Гран_значение then Push Пиксел(x,y-1) end if end while В алгоритме проверяются и помещаются в стек 4-х связные пикселы, начиная с правого от текущего пиксела. Направление обхода пикселов - против часовой стрелки. (x , y-1) (x-1,y ) (x ,y+1) (x+1, y ) Пример 1. Затравочный пиксел Внутренний пиксел Граничный пиксел Пусть имеем гранично-определенную полигональную область, заданную вершинами: (1,0), (7,0), (8,1), (8,4), (7,5), (6,6), (1,6), (0,5), (0,1). Затравочный пиксел: (4,3). 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 1 Пример 1. Затравочный пиксел Внутренний пиксел Граничный пиксел 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 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). Пример 1. Затравочный пиксел Внутренний пиксел Граничный пиксел 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 1 Так как все пикселы, окружающие (5,5), содержат либо граничные, либо новые значения цвета, то ни один из них в стек не помещается. Следовательно, из стека извлекается пиксел (7,4) и алгоритм продолжает заполнять колонку: (7,4), (7,3), (7,2), (7,1 ). Пример 1. Затравочный пиксел Внутренний пиксел Граничный пиксел 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 1 При достижении пиксела (7,1) проверка снова показывает, что окружающие пикселы либо уже заполнены, либо являются граничными пикселами. Т.к. в этот момент многоугольник полностью заполнен, то извлечение пикселов из стека до полного опустошения не вызывает появления дополнительных пикселов, которые следует заполнить Когда стек становится пустым, алгоритм завершает работу. Пример 2 (с дырой). Затравочный пиксел Внутренний пиксел Граничный пиксел Дыра определена вершинами:(3,2), (5,2), (5,3), (3,3). Затравочный пиксел: (4,4). 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 1 Пример 2 (с дырой). Затравочный пиксел Внутренний пиксел Граничный пиксел Когда обработка доходит до пиксела (3,1), глубина стека равна 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,4), при этом ни один новый пиксел в стек не добавляется. 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 1 Пример 2 (с дырой). Затравочный пиксел Внутренний пиксел Граничный пиксел Как только закрасится пиксел (7,4), все 4-х связные окружающие пикселы либо уже заполнены, либо являются граничными. Обращаясь к стеку, алгоритм извлекает пиксел (6,5). Дальнейшая обработка идет без заполнения, и когда стек становится пустым, алгоритм завершает работу. 0 1 2 3 4 5 6 7 8 9 7 6 5 4 3 2 1 Недостатки простого алгоритма заполнения: 1. Стек может быть довольно большим. 2. Стек содержит дублирующую или ненужную информацию. 3. Построчный алгоритм заполнения с затравкой. Введен термин «Непрерывный интервал» - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). В данном алгоритме размер стека минимизируется за счет хранения только одного затравочного пиксела. Для любого непрерывного интервала на сканирующей строке. Используется эвристический подход к поиску пиксела. Построчный алгоритм заполнения: Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы. Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор, пока не будет найдена граница. В переменных Xлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала. В диапазоне Xлев <= x<= Xправ проверяются строки, расположенные непосредственно над и под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т.е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек. 0 1 2 3 4 5 6 7 8 9 10 11 12 Затравочный пиксел Граничный пиксел Заполненный пиксел 10 8 6 4 2 Затравка(x,y) - выдает затравочный пиксел. Push -процедура, которая помещает пиксел в стек, инициализирует стек. Pop - процедура, которая извлекает пиксел из стека. Push Затравка (x,y) While (стек не пуст) извлекаем пиксел из стека и присваиваем ему новое значение Pop Пиксел (x,y) Пиксел (x,y) = Нов_значение сохраняем х-координату затравочного пиксела Врем_х = х Заполняем интервал справа от затравки х = х +1 While Пиксел (x,y) <> Гран_значение Пиксел (x,y) = Нов_значение х = x + 1 end While сохраняем крайний справа пиксел Хправ = х - 1 восстанавливаем х-координату затравки х = Врем_х заполняем интервал слева от затравки х = х - 1 While Пиксел (x,y) <> Гран_значение Пиксел (x,y) = Нов_значение х = х -1 end While сохраняем крайний слева пиксел Хлев = x + 1 восстанавливаем х-координату затравки х = Врем_х проверим, что строка выше не является ни границей многоугольника, ни уже полностью заполненной; если не так, то найти затравку, начиная с левого края подинтервала сканирующей строки х = Хлев y = y + 1 While х <= Хправ ищем затравку на строке выше Флаг = 0 While (Пиксел (x,y) <> Гран_значение and Пиксел (x,y) <> Нов_значение and x < Хправ if Флаг = 0 then Флаг =1 х = х + 1 end While помещаем в стек крайний справа пиксел if Флаг = 1 then if (х = Хправ and Пиксел (x,y) <> Гран_значение and Пиксел (x,y) <> Нов_значение then Push Пиксел (x,y) else Push Пиксел (x-1, y) end if Флаг = 0 end if продолжаем проверку, если интервал прерван Хвход = х While ((Пиксел (x,y) = Гран_значение or Пиксел (x,y) = Нов_значение) and x < Хправ) х = х + 1 end While удостоверимся, что координата пиксела увеличина if x =Хвход then х = х + 1 end While проверим, что строка ниже не является ни границей многоугольника, ни уже полностью заполненной Эта часть алгоритма аналогична проверке для строки выше, за исключением того, что вместо y = y + 1 надо подставить y = y - 1 end While 0 1 2 3 4 5 6 7 8 9 10 11 12 10 8 6 4 2 1. Интервал заполняется справа и слева от (5,7). 2. Запоминаются концы интервала: Хправ = 9, Хлев = 1. 3. Проверяется строка выше текущей (7+1=8). Она не граничная и не заполненная. 4. Крайним правым пикселом в диапазоне 1<= x <= 9 оказываеся пиксел (8.8). Он помечен на рисунке цифрой 1. Этот пиксел помещается в стек. Затравка(5,7) -затравочный пиксел. 1 0 1 2 3 4 5 6 7 8 9 10 11 12 10 8 6 4 2 7. Для левого подинтервала в качестве затравки выступает пиксел (3,6), он помечен цифрой 2. Он помещается в стек. Для правого подинтервала в качестве затравки выступает пиксел (9,6). Заметим, что он не самый крайний правый пиксел на интервале, но он самый крайний правый в диапазоне Хлев < = х < = Хправ, т.е. в диапазоне 1 < = x < = 9. 8. На этом завершается первый проход алгоритма. 1 2 5. Обрабатывается строка ниже текущей (7 - 1 = 6). 6. В диапазоне Хлев <= x <= Хправ есть 2 подинтервала на этой строке. 0 1 2 3 4 5 6 7 8 9 10 11 12 10 8 6 4 2 11. Обрабатывая строку выше (4), получим для левого подинтервала затравочный пиксел (3,4), который помещается в стек. Правый подинтервал к этому времени уже заполнен. 12. Обработка строки ниже (2) дает затравку (3,2) для левого и (10,2) для правого подинтервалов. Эти пикселы также помещаются в стек. 1 2 9. Для строки 3 затравкой служит пиксел (10,3). 10. В результате заполнения интервала слева и справа от затравки получим новые пределы диапазона: Хлев = 1 и Хправ =10 3 |