Построчный алгоритм заполнения с затравкойКак видно из предыдущего примера, стек может стать довольно большим. Еще один недостаток предыдущего алгоритма - стек зачастую содержит дублирующую или ненужную информацию. В построчном алгоритме заполнения с затравкой размер стека минимизируется за счет хранения только одного затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов. Данный алгоритм применим к гранично-определенным областям. Гранично-определенная 4-связная область может быть как выпуклой, так и не выпуклой, а также может содержать дыры. В области, внешней и примыкающей к нашей гранично-определенной области, не должно быть пикселов с цветом, которым область или многоугольник заполняется. Схематично работу алгоритма можно разбить на четыре этапа.
Как показано в примере ниже, алгоритм справляется с дырами и зубцами на границе. Ниже приводится более подробное описание алгоритма на псевдокоде: Затравка (х, у) - выдает затравочный пиксел
Пример 2.4. Построчный алгоритм заполнения с затравкой. Рассмотрим работу алгоритма для гранично-определенной области на рис. 2.16. При инициализации в стек помешается затравочный пиксел, помеченный как Затравка (5, 7) на рис. 2.16, а. Первоначально в качестве затравки интервала из стека извлекается этот пиксел. Интервал заполняется справа и слева от затравки. Найденные при этом концы интервала Хправ = 9 и Xлев = 1. Затем проверяется строка, расположенная выше текущей и оказывается, что она не граничная и не заполненная. Крайним правым пикселом в диапазоне 1 < = x < = 9 оказывается пиксел (8, 8), помеченный цифрой 1 на рис. 2.16, а. Этот пиксел помещается в стек. Затем аналогичным образом обрабатывается строка ниже текущей. В диапазоне Хлев < = x < = Xправ есть два подинтервала на этой стороне. Для левого интервала в качестве затравки выступает пиксел (3, 6), помеченный цифрой 2 на рис. 2.16, а, он тоже помещается в стек. Затравка для правого подинтервала - пиксел (9, 6), он помещается в стек. Заметим, что пиксел (9, 6) - не самый крайний правый пиксел на интервале, однако это самый крайний правый пиксел в диапазоне Хлев < = x < = Xправ, т.е. в диапазоне 1 < = x < = 9. На этом завершается первый проход алгоритма.
Далее из стека извлекается верхний пиксел. Здесь заполняются интервалы, расположенные в правой части многоугольника на последовательных сканирующих строках (рис. 2.16, b, c, d). Для строки 3 затравкой служит пиксел (10, 3) (рис. 2.16, d). В результате заполнения интервала справа и слева от затравки получаем новые пределы диапазона Хправ = 10 и Xлев = 1. Обрабатывая строку выше, получаем для основного подынтервала затравочный пиксел (3, 4), коорый помещается в стек. Правый подинтервал к этому времени уже заполнен. Обработка строки ниже дает затравку (3, 2) для левого и (10, 2) для правого подынтервалов. Эти пикселы также помещаются в стек. Именно сейчас достигается максимальная глубина стека для обрабатываемого многоугольника. Теперь остается только один интересный момент. После заполнения 4-связных полигональных подобластей с затравочными пикселами 5, 4 и 3 на рис. 2.16, е из стека извлекается пиксел, помеченный цифрой 2. Здесь мы обнаруживаем, что все пикселы на этой строке уже и на соседних строках (выше и ниже) уже заполнены. Таким образом, ни один пиксел в стек не помещается. Из стека извлекается пиксел 1 и строка обрабатывается, при этом вновь добавочных пикселов не появляется. Теперь стек пуст, многоугольник заполнен и работа алгоритма завершена. По сравнению с алгоритмом из разд. 2.7 максимальная глубина стека в этом примере равна пяти.
|
