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

Рассмотрим область, ограниченную набором пикселей заданного цвета и точку (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 раза и, кроме того, этот алгоритм требует слиш­ком большого объёма стека из-за большой глу­бины рекурсии. Поэтому для решения за­дачи закраски области предпочтительнее алгоритмы, способные обраба­тывать сразу це­лые группы пикселей, т. Е. Ис­пользовать их «связность» - если данный пиксель принадлежит об­ласти, то скорее всего его ближайшие соседи также принадлежат данной области.

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

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

Заполнение многоугольника

Часто возникает задача заполнения многоугольников, заданных набором вершин.

Задача заполнения многоугольников решается в два этапа:

1. Сначала проводится операция отсечения многоугольника;

2. Затем производится заполнение полученных многоугольников.

Этап отсечения необходим для определения реальных областей многоугольника, кото­рые будут выведены на экран. Это необходимо если многоугольник больше или выходит за пределы экрана или окна вывода.