10. Алгоритмы заполнения с затравкой. Построчный алгоритм заполнения с затравкой. - p1xelse/CG GitHub Wiki

В построчном алгоритме затравочного заполнения мы помещаем в стек один затравочный пиксель для непрерывного интервала пикселей.

Алгоритм

(после ввода исходных данных следует пункт вычерчивание границ области) image В качестве нового затравочного пикселя необходимо взять самый правый из каждого непрерывного интервала затравочных пикселей (если поиск ведётся слева направо). Найденные пиксели добавляются в стек

Анализ эффективности

  1. Цвет каждого пикселя анализируется 3 раза у всех пикселей, кроме пикселей, примыкающих к граничным пикселям сверху и снизу, а также у первого затравочного пиксела - там 2 считывания.

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

  1. Цвет каждого пикселя меняется только один раз.

  2. Обрабатываются пиксели, находящиеся внутри области закраски, а так же пиксели, расположенные на границе: будет считан цвет граничных пикселей. За пределами области ничего не анализируем.

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

По быстродействию затравочный алгоритм уступает растровым. В растровых мы за минимальное число операций определяем, что нужно красить. Для затравочных алгоритмов дело обстоит по другому. Мы работаем со стеком, так вынуждены еще и трижды (в нашем алгоритме) узнавать цвет каждого пикселя.

Например, сравним затравочный алгоритм с алгоритмом заполнения по рёбрам. В алгоритме по ребрам, например, хоть он и не самый быстрый, мы за 2-3 арифметических операций определяем, что нужно закрасить кусок строки. Это происходит довольно быстро, и число запросов цвета минимально (не сильно больше числа закрашиваний).

Начальный цвет пикселей области

  1. Пиксели не могут иметь цвет границы.
  2. Пиксели могут иметь цвет закраски, но в ограниченном количестве. Может быть и в неограниченном, но важно, как распределены в области.
  3. Любой другой цвет они могут иметь.

Каким образом при задании затравки в одной подобласти, удается закрасить всю область?

Имеем следующую фигуру с затравочным пикселем, расположенным внизу правой области:

Рассмотрим, что происходит этапе закраски, когда мы из одной подобласти переходим в другую подобласть:

Анализируем строку выше текущей. Поиск затравочных пикселей происходит в рамках закрашенного ранее интервала (между двумя красными точками). Закрашивание строки уже не связано с ограничением красных точек. Закраска ограничена лишь границами фигуры. На нижеприведенном изображении я показала закраску одной строки.

С закраской новой строки происходит расширение интервала поиска затравочных пикселей (красные точки).

Имеем в итоге

Так же мы при поиске новых затравочных пикселей двигаемся не только вверх, мы анализируем еще и нижнюю строку относительно текущей. Если бы мы двигались только в одном направлении, мы бы не смогли закрасить все подобласти фигуры. Пиксели нижней строки в процессе помещаем в стек. После чего мы их достаем из стека и закрашиваем фигуру: