Алгоритм со списком ребер и флагом

Обрисовка контура:

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

x + 1/2 > xпересечения

Заполнение:

Для каждой сканирующей строки, пересекающей многоугольник

Внутри = FALSE

for x = 0 (левая граница) to x = xmax, (правая граница)

if пиксел в точке x имеет граничное значение

then инвертировать значение переменной Внутри

if Внутри = TRUE then

присвоить пикселу в x значение цвета многоугольника

else

присвоить пикселу в x значение цвета фона

end if

next x

В данном алгоритме каждый пиксел обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком рёбер, в результате чего, при его аппаратной реализации, он работает на один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер.

2.9. Алгоритмы заполнения с затравкой

В обсуждавшихся выше алгоритмах заполнение происходит в по­рядке сканирования. Иной подход используется в алгоритмах заполнения с затравкой. В них предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритм пытается найти и закрасить все другие пикселы, принадлежащие внут­ренней области. Области могут быть либо внутренние, либо гранично-определенные. Если область относится к внутренне - опреде­ленным, то все пикселы, принадлежащие внутренней части, имеют один и тот же цвет или интенсивность, а все пикселы, внешние по отношению к области, имеют другой цвет. Это продемонстрирова­но на рис. 2.10. Если область относится к гранично-определенным, то все пикселы на границе области имеют выделенное значение или цвет, как это показано на рис. 2.11. Алгоритмы, заполняющие внутренне - определенные области, называются внутренне - заполня­ющими, а алгоритмы для гранично-определённых областей – гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие алгоритмы, однако соответствующие внутренне заполняющие алгоритмы можно получить аналогичным образом.

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

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

Используя стек, можно разработать алгоритм заполнения гранично-определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Как показывает практика, стек может быть довольно большим. Зачастую в нём содержится дублирующаяся информация. В построчном алгоритме заполнения с затравкой стек минимизируется за счёт хранения только затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов.

Данный алгоритм применим гранично-определённым 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