Закраска области, заданной цветом границы

Рассмотрим область, ограниченную набором пикселей заданного цвета и точку (x, y), лежащую внутри этой области.

Задача заполнения области заданным цветом в случае, когда эта область не является выпуклой, может оказаться довольно сложной.

Простейший рекурсивный алгоритм:

void PixelFill(int x, int y, int border_color, int color)

{

int c = getpixel(x, y);

if ((c!= border_color) && (c!= color))

{

putpixel(x, y, color);

PixelFill(x – 1, y, border_color, color);

PixelFill(x + 1, y, border_color, color);

PixelFill(x, y – 1, border_color, color);

PixelFill(x, y + 1, border_color, color);

}

}

Этот алгоритм является слишком неэффективным, так как для всякого уже отрисованного пикселя функция вызывается ещё 4 раза и, кроме того, этот алгоритм требует слишком большого объёма стека из-за большой глубины рекурсии. Поэтому для решения задачи закраски области предпочтительнее алгоритмы, способные обрабатывать сразу целые группы пикселей, т. е. использовать их «связность». Если данный пиксель принадлежит области, то, скорее всего, его ближайшие соседи также принадлежат данной области.

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

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