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

Вначале затравка (X, Y) запоминается в стек. Затем в цикле, пока стек не пуст, производятся следующие действия. Извлекается точка из стека и закрашивается весь максимальный горизонтальный связный отрезок области, содержащий эту точку. Во время закраски вычисляются наименьшая X_лев и наибольшая X_прав абсциссы точек этого отрезка. Просматриваются слева направо точки (X,Y-1) в пределах X_лев £ X £ X_прав. Определяется, есть ли среди этих точек незакрашенные. Если такие точки есть, то в каждом связном подинтервале множества таких точек выбирается крайний правый пиксел и запоминается в стек. Аналогичные действия производятся с точками (X,Y+1). Заметим, что после каждого извлечения из стека, действия внутри цикла целесообразно производить только в тех случаях, когда извлеченная точка снова является затравкой (то есть, не закрашена).

Ниже приведена программа, реализующая этот алгоритм.

Программа

#include <stdio.h>

#include <conio.h>

#include <graphics.h>

#define pop() x=stx[--deep];y=sty[deep]

#define push(a,b) stx[deep]=a;sty[deep++]=b

int deep=0, stx[1000], sty[1000] ;

int xmax, xmin=0, ymax, ymin=0 ;

void flstr(int color, int x, int y)

{

int tempx;

int xleft, xright;

int xenter;

int flag, i ;

push(x,y) ;

while(deep>0)

{

pop() ;

if(getpixel(x,y)!=color)

{

putpixel(x,y,color) ;

tempx=x; //сохранение текущей коорд. x

x++;     //перемещение вправо

while(getpixel(x,y)!=color && x<=xmax)

putpixel(x++, y, color);

xright=x-1;

x=tempx; x--; //перемещение влево

while(getpixel(x,y)!=color && x>=xmin)

putpixel(x--, y, color);

xleft=x+1;

x=tempx;

for(i=0;i<2;i++)

{

//при i=0 проверяем нижнюю,

//а при i=1 - верхнюю строку

if(y<ymax && y>ymin)

{

x=xleft; y+=1-i*2;

while(x<=xright)

{

flag=0;

while(getpixel(x,y)!=color && x<xright)

{

if(flag==0) flag=1;

x++;

}

if (flag==1)

{

if(x==xright &&

getpixel(x,y)!=color)

{

push(x,y);

}

else

{push(x-1,y);}

flag=0;

}

xenter=x;

while(getpixel(x,y)==color && x<xright)

x++;

if(x==xenter) x++;

}

}

y-- ;

}

}

}

}

void main()

{

int gd=DETECT , gm;

initgraph (&gd, &gm, "");

moveto (280, 110);

lineto (250, 180);

lineto (50, 20);

lineto (280, 110);

xmax=getmaxx();ymax=getmaxy();

flstr (WHITE, 270, 110);

getch();

closegraph();

}

Опишем этот алгоритм для более простого случая, а именно для выпуклого многоугольника. Известна затравка (X, Y) и цвет границы. Вначале затравка (X, Y) запоминается в стек. Затем, в цикле, пока стек не пуст, извлекается одна точка из стека и заносится в (X, Y). Если (X, Y) не закрашена, то закрашивается максимальный горизонтальный отрезок области, содержащий точку (X, Y). Во время закраски вычисляются X_лев – наименьшая абсцисса этого отрезка (левая граница) и X_прав– наибольшая абсцисса этого отрезка (правая граница). Затем просматриваются слева направо точки (X, Y-1) в пределах X_лев ≤ X ≤ X_прав. Среди этих точек могут оказаться точки границы или закрашенные точки. Определяем, есть ли среди этих точек незакрашенные. Если такие точки есть, то среди незакрашенных точек выбирается крайняя правая точка и заносится в стек. Если незакрашенная точка единственная, то она и заносится в стек. Аналогичные действия производятся с точками (X, Y+1).