Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

Данный алгоритм применим гранично-определённым 4-связным областям, которые могут быть как выпуклыми, так и не выпуклыми, а также могут содержать дыры. В области, внешней и примыкающей к нашей, не должно быть пикселов с цветом, которым область или многоугольник заполнятся. Схематично работу алгоритма можно разбить на четыре этапа.

Построчный алгоритм заполнения с затравкой

Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.

Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор пока не будет найдена граница.

В переменной Xлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала

В диапазоне Xлев ( x ( Xправ проверяются строки расположенные непосредственно над в под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.

При инициализации алгоритма в стек помешается единственный затравочный пиксел, работа завершается при опустошении стека. Ниже приводится более подробное описание алгоритма на псевдокоде.

Построчный алгоритм заполнения с затравкой

Затравка ( x, y ) выдаёт затравочный пиксел
Pop - процедура, которая извлекает пиксел из стека
Push - процедура, которая помещает пиксел в стек

инициируем стек
Push Затравка ( x, y )
While ( стек не пуст )

Извлекаем пиксел из стека и присваиваем ему новое значение Pop
Пиксел ( x, y )

Пиксел ( x, y ) = Нов_значение сохраняем x- координату затравочного пиксела

Врем_х = x заполняем интервал справа от затравки x = x +1 while Пиксел ( x, y ) ( Гран_значение

Пиксел ( x, y ) = Нов_значение x = x +1 end while сохраняем крайний справа пиксел

Xправ = x (1 восстанавливаем x- координату затравки x = Врем_х заполняем интервал слева от затравки x = x (1 while Пиксел ( x, y ) ( Гран_значение

Пиксел ( x, y ) = Нов_значение x = x (1 end while сохраняем крайний слева пиксел

Xлев = x +1 восстанавливаем x- координату затравки x = Врем_х проверим, что строка выше не является ни границей многоугольника, ни уже полностью заполненной; если это не так, то найти затравку, начиная с левого края подинтервала сканирующей строки x = Xлев y = y +1 while x ( Xправ ищем затравку на строке выше

Флаг = 0 while ( Пиксел ( x, y ) ( Гран_значение and

Пиксел ( x, y ) ( Нов_значение and x < Xправ ) if Флаг = 0 then Флаг = 1 x = x + 1 end while помещаем в стек крайний справа пиксел if Флаг =1 then if ( x = Xправ and Пиксел ( x, y ) ( Гран_значение and Пиксел ( x, y ) ( Нов_значение ) then

Push Пиксел ( x, y ) else

Push Пиксел ( x ( 1, y ) end if

Флаг = 0 end if продолжим проверку, если интервал был прерван

Xвход = x while (( Пиксел ( x, y ) = Гран_значение or

Пиксел ( x, y ) = Нов_значение ) and x < Xправ) x = x + 1 end while удостоверимся что координата пиксела увеличена if x = Xвход then x = x + 1 end while проверим, что строка ниже не является ни границей многоугольника, ни уже полностью заполненной

Эта часть алгоритма совершенно аналогична проверке для строки выше, за исключением, того что вместо y = y + 1 надо подставить y = y ( 1 end while finish

Рекомендуем скачать другие рефераты по теме: предмет культурологии, реферат на тему организация.





Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата