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

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

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

• (Защита) В качестве затравочного выбирается самый крайний пиксел в строке. Это необходимо, так как рассматриваемый интервал пикселей может прерываться граничными пикселами, а именно рассматриваемый интервал может содержать несколько непрерывных интервалов пикселей. Если в таком случае взять самый левый пиксел при движении слева направо, не найдутся затравочные пиксели для других интервалов, входящих в состав исходного интервала. Поэтому выбираем крайний правый пиксел

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

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

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

ЗАЩИТА:

1. Объясните, что будет, если затравку задать на границе области?

2. Какой цвет могут изначально иметь пиксели области?

3. Сколько раз анализируется цвет каждого пикселя?

4. Какой пиксель в интервале надо заносить в стек в качестве затравочного?

5. Объясните, каким образом при задании затравки в одной подобласти, удается закрасить всю область?(на примере многоугольника перед программой в отчете, затравка задана вверху слева).Сделайте коротко и по сути (конкретно).

1.Выбранный граничный пиксел закрашивается как затравочный. Далее идет анализ: Если по бокам 2 граничных пиксела, то ничего больше закрашено не будет, цикл поиска новых затравочных пикселей не будет работать, соответственно закраска на этом закончится. Если по бокам не 2 граничных пикселя, то алгоритм начнет закрашивать область вне границы и сработает некорректно.

2. Любой, отличный от цвета граничного.

3. Граничные 1 раз, остальные 3 раза

4. Самый правый.

5. В качестве затравочного выбирается самый крайний пиксел в строке. Это необходимо, так как рассматриваемый интервал пикселей может прерываться граничными пикселами, а именно рассматриваемый интервал может содержать несколько непрерывных интервалов пикселей. Если в таком случае взять самый левый пиксел при движении слева направо, не найдутся затравочные пиксели для других интервалов, входящих в состав исходного интервала. Поэтому выбираем крайний правый пиксел

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

• Цвет пикселя меняется всего лишь один раз.
• Обрабатываются пиксели внутри области и граничные пиксели. В среднем, пиксель будет обработан 3 раза: при проходе по его строке, и при поиске затравочных пикселей слева и справа.
• Размещаем в стеке только лишь один затравочный пиксель, для непрерывного интервала пикселей.