Простой алгоритм заливки

Рассмотрим простой алгоритм заливки гранично-определенной 4-х связной области. В [] приведена рекурсивная реализация подпрограммы заливки 4-х связной гранично-определенной области:

void V_FAB4R (grn_pix, new_pix, x_isx, y_isx)

int grn_pix, new_pix, x_isx, y_isx;

{

if (getpixel (x_isx, y_isx) № grn_pix &&

getpixel (x_isx, y_isx) № new_pix)

{

putpixel (x_isx, y_isx, new_pix);

V_FAB4R (grn_pix, new_pix, x_isx+1, y_isx);

V_FAB4R (grn_pix, new_pix, x_isx, y_isx+1);

V_FAB4R (grn_pix, new_pix, x_isx-1, y_isx);

V_FAB4R (grn_pix, new_pix, x_isx, y_isx-1);

}

} /* V_FAB4R */

Заливка выполняется следующим образом:

· определяется является ли пиксел граничным или уже закрашенным,

· если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела.

Полный текст тестовой программы V_FAB4R с использованием этой подпрограммы приведен в Приложении 6.

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

В [] приведен итеративный алгоритм закраски 4-х связной гранично-определенной области. Логика работы алгоритма следующая:

Поместить координаты затравки в стек

Пока стек не пуст

Извлечь координаты пиксела из стека.

Перекрасить пиксел.

Для всех четырех соседних пикселов проверить

является ли он граничным или уже перекрашен.

Если нет, то занести его координаты в стек.

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

Ясно, что такой алгоритм экономнее, так как в стек надо упрятывать только координаты.

Рассмотренный алгоритм легко модифицировать для работы с 8-ми связными гранично-определенными областями или же для работы с внутренне-определенными.

Программа V_FAB4, реализующая данный алгоритм, приведена в Приложении 6.

a) Порядок перебора соседних пикселов

б) Порядок заливки области

Рис. 0.5.2: Заливка 4-х связной области итеративным алгоритмом

Сравнительные прогоны тестовых программ V_FAB4R и V_FAB4 подтвердили соображения о неэкономности рекурсивного алгоритма: при стандартном окне стека в 64 K с помощью рекурсивной программы можно закрасить квадратик не более чем 57×57 пикселов. Итеративная же программа V_FAB4 при тех же условиях позволяет закрасить прямоугольник размером 110×110 истратив на массив координат 16382 байта.

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