Заливка замкнутой области

Пример показывает один из самых простых и эффективных способов заливки. Использовать его в таком варианте не рекомендую, рисовать на TImage->Canvas довольно медленно, но в качестве примера очень удобно.

Процедура последовательно просматривает соседние точки, и если они не залиты, то заливает и добавляет 4 соседние точки в очередь, на рассмотрение. И так пока очередь не кончится.

На рисунке черными стрелками показаны точки, которые будут добавлены в очередь для просмотра, а красными, которые не будут добавлены, так как уже залиты.

Теперь собственно - исходник. (Borland C++ Builder). На форме достаточно иметь TImage - Image1.

void ImageFill(short x, short y, TColor color) {
    // Получим размеры изображения
    int imw=Form1->Image1->Width;
    int imh=Form1->Image1->Height;
    // Выделим памяти для складирования координат, которые еще предстоит залить
    int STACK_SIZE=(imw+2)*(imh+2);
    short *floodfill_stackx=(short*)malloc(STACK_SIZE*sizeof(short));
    short *floodfill_stacky=(short*)malloc(STACK_SIZE*sizeof(short));
    if (floodfill_stacky==NULL || floodfill_stackx==NULL) return;
    int stack_head=0;
    int stack_tail=0;
    TColor clr=Form1->Image1->Canvas->Pixels[x][y];
    floodfill_stackx[stack_head]=x;
    floodfill_stacky[stack_head]=y;
    Form1->Image1->Canvas->Pixels[x][y]=color;
    stack_head++;
    // Пока не кончится память или точки на изображении
    while (stack_head<STACK_SIZE && stack_head>stack_tail) {
        x=floodfill_stackx[stack_tail];
        y=floodfill_stacky[stack_tail];
        stack_tail++;
        if (x>=0 && y>=0 && x<imw && y<imh) {
            // Проверим точку справа, если она не залита, то зальем
	        if (Form1->Image1->Canvas->Pixels[x+1][y]==clr) {
                floodfill_stackx[stack_head]=x+1;
            	floodfill_stacky[stack_head]=y;
                Form1->Image1->Canvas->Pixels[x+1][y]=color;
            	stack_head++;
                }
            // Проверим точку слева, если она не залита, то зальем
            if (Form1->Image1->Canvas->Pixels[x-1][y]==clr) {
                floodfill_stackx[stack_head]=x-1;
    	        floodfill_stacky[stack_head]=y;
                Form1->Image1->Canvas->Pixels[x-1][y]=color;
            	stack_head++;
                }
            // Проверим точку снизу, если она не залита, то зальем
            if (Form1->Image1->Canvas->Pixels[x][y+1]==clr) {
                floodfill_stackx[stack_head]=x;
                floodfill_stacky[stack_head]=y+1;
                Form1->Image1->Canvas->Pixels[x][y+1]=color;
            	stack_head++;
                }
            // Проверим точку сверху, если она не залита, то зальем
            if (Form1->Image1->Canvas->Pixels[x][y-1]==clr) {
                floodfill_stackx[stack_head]=x;
                floodfill_stacky[stack_head]=y-1;
                Form1->Image1->Canvas->Pixels[x][y-1]=color;
            	stack_head++;
                }
            }
        }
    Form1->Image1->Canvas->TextOutA(1,1,IntToStr(stack_head));
    // Освободим память
    free(floodfill_stacky);
    free(floodfill_stackx);
    }

void __fastcall TForm1::Button1Click(TObject *Sender) {
    Image1->Canvas->Ellipse(20,20,300,200);
    ImageFill(1,1,0xFF0000);
    }

1.

Аноним

17 марта 2006, 22:46:05

Ах да, скажу - неизбежно будет переполнение стека (который таки переполнится несмотря на проверку stack_head<STACK_SIZE, поглядите внимательно). Почему? А потому, что признаком конца псевдоитерации служит считанный цвет и при равных цветах распространение всегда будет во все четыре стороны и алгоритм вообще никогда не остановится.
з.ы. if(clr==color)return; надо поставить первой строкой, чтобы зря не выделять и не удалять память.

2.

Аноним

17 марта 2006, 22:10:49

Мало того, что алгоритм ужасен в неэффективности, так ещё и... вот подумайте, что будет, если заливать область тем же цветом, что и сама область! Подумали?
А теперь ОБЯЗАТЕЛЬНО вставьте проверку if(clr==color)return;