Алгоритм закрашивания очень часто используется в компьютерной графике для закрашивания фигур имеющих границы. Так же этот алгоритм может иметь и другое применение например его можно использовать для нахождения центра масс тела по его изображению. Приведу два алгоритма один рекурсивный, а второй линейный. Рекурсивный имеет один недостаток, его нельзя использовать для закрашивания больших фигур так как при большом количестве элементов происходит переполнение стека. Код использует OpenCV для работы с изображениями, но при желании их можно переписать под что угодно.
1. Рекурсивный алгоритм
void zakrashivanie(uchar** ptr,int x, int y){
if(ptr[y][3*x]==255){
//Закраска (x, y) пикселя
ptr[y][3*x] = 0;
ptr[y][3*x+1] = 255;
ptr[y][3*x+2] = 0;
zakrashivanie(ptr,x-1,y);
zakrashivanie(ptr,x+1,y);
zakrashivanie(ptr,x,y-1);
zakrashivanie(ptr,x,y+1);
}
}
2. Волновой алгоритм
void NearPix(uchar** ptr,int x, int y, int *numStack, CvPoint *Stack){
if(ptr[y][3*x]==255){
ptr[y][3*x] = 0;
ptr[y][3*x+1] = 255;
ptr[y][3*x+2] = 0;
Stack[*numStack].x=x;
Stack[*numStack].y=y;
(*numStack)++;
}
}
void OneStep(uchar** ptr, int *numSrc, int *numDest, CvPoint *Src, CvPoint *Dest){
int x,y,i;
*numDest=0;
for(i=0; i<*numSrc;i++){
x=Src[i].x;
y=Src[i].y;
NearPix(ptr,x+1,y,numDest,Dest);
NearPix(ptr,x-1,y,numDest,Dest);
NearPix(ptr,x,y+1,numDest,Dest);
NearPix(ptr,x,y-1,numDest,Dest);
}
}
void WaveFill(uchar** ptr,int xst, int yst){
int numA, numB;
CvPoint *stackA, *stackB;
stackA=new CvPoint[10000];
stackB=new CvPoint[10000];
numA=1;
stackA[0].x=xst;
stackA[0].y=yst;
numB=0;
while(1){
if(numA>0)OneStep(ptr,&numA,&numB,stackA,stackB);
else break;
if(numB>0)OneStep(ptr,&numB,&numA,stackB,stackA);
else break;
}
delete [] stackB;
delete [] stackA;
}
|
