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

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

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

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

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

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

3. В переменных Х_лев и Х_прав запоминаются крайний левый и крайний правый пикселы интервала.

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

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

Теперь остается только один интереснй момент. После заполнения 4-связных полигональных подобластей с затравочными пикселами 5, 4 и 3 на рис. 2.16,е из стека извлекается пиксел, помеченный цифрой 2. Здесь мы обнаруживаем, что все пикселы на этой строке уже и на соседних строках (выше и ниже) уже заполнены. Таким образом, ни один пиксел в стек не помещается. Из стека извлекается пиксел 1 и строка обрабатывается, при этом вновь добавочных пикселов не появляется. Теперь стек пуст, многоугольник заполнен и работа алгоритма завершена.

По сравнению с алгоритмом из разд. 2.7 максимальная глубина стека в этом примере равна пяти.