Плоская машинная графика, страница 8

for(i=60;i>=20;i--) {XorLine(60,i); delay(200);}

//проход по верхней стороне квадрата с задержкой

for(i=60;i>=20;i--) XorLine(i,20);

getch();          //Ожидание нажатия клавиши

closegraph();     //Выключение графического режима

}

Результат работы программы приведен на рис. 8.

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

Достоинством всех затравочных алгоритмов заполнения области является то, что для закраски области с произвольной границей достаточно знать цвет границы и координаты одной незакрашенной точки области, не принадлежащей границе. Но затравочные алгоритмы различны по эффективности. Вначале рассмотрим самый простой, но и наименее эффективный алгоритм закраски – простой алгоритм заполнения. В силу своей неэффективности, этот алгоритм не используется на практике, но именно на примере этого алгоритма проще всего объяснить суть затравочных алгоритмов.

Простой алгоритм заполнения. Задана область и произвольная затравка (X,Y). Вначале точка (X,Y) помещается в стек. Затем, пока стек не пуст, последовательно вынимается точка из стека и заносится в (X,Y), и если эта точка не закрашена (что может случиться, если точка попала в стек второй раз), то производятся следующие действия:

закрашивается точка (X, Y),

если (X+1  , Y     ) - затравка, то (X+1         , Y      ) запоминается в стек,

если (X      , Y+1 ) - затравка, то (X    , Y+1 ) запоминается в стек,

если (X-1   , Y     ) - затравка, то (X-1 , Y     ) запоминается в стек,

если (X      , Y-1 ) - затравка, то (X    , Y-1 ) запоминается в стек.

Алгоритм неэффективен, т.к. предполагает неоднократную обработку одних и тех же точек области. Отметим, что, если область достаточно велика, то возможно переполнение стека.

Простой алгоритм заполнения с затравкой с использованием рекурсии. Используя рекурсию, алгоритм заполнения с затравкой можно реализовать следующим образом:

void fl ( int x, int y )

{

if (getpixel(x,y)) return;

putpixel(x,y,WHITE);

fl(x-1,y); fl(x,y+1); fl(x+1,y); fl(x,y-1);

}

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

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

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