Flood fill function not working

Question

I want to do flood fill for 2D images, but I keep getting the same results.

The program is quite simple. It reads a 2D image from a txt file containing 0s and 1s and applies the depth-first variant of the flood fill algorithm:

void floodFill (int u, int v, int label,Image &img, ImageLabels &imgL)
{

    struct Point { int x; int y; int l;};

    Point p = {0 , 0 , 1};

    u = p.x;
    v = p.y;
    label = p.l;

    vector <Point> stack;
        stack.push_back(p);

    while (!stack.empty()) 
    {
        Point p = stack.back();
        stack.pop_back();


        Point one = {(p.x+1), p.y, label};
        Point two = {p.x,(p.y+1), label};
        Point three = {p.x,(p.y-1), label};
        Point four = {(p.x-1),p.y, label};        
        if ((p.x>=0) && (p.x<img.size()) && (p.y>=0) && (p.y<img[0].size()) && img[p.x][p.y]==1)
        {
                stack.push_back(one);
                stack.push_back(two);
                stack.push_back(three);
                stack.push_back(four);
            img[p.x][p.y] = label;
        }
    }
}

Here is the image labeling code:

void imageLabeling(Image &img, ImageLabels &imgL)
{
    long int numLines=img.size();
    long int numCols=img[0].size();

    int u=0;
    int v=0;
    int label=1;

    imgL.resize(numLines);
    for (unsigned int i=0; i<numLines; i++)
        imgL[i].resize(numCols);

    for (unsigned int i=0; i <numLines; i++)
        for (unsigned int j=0; j <numCols; j++)
            imgL[i][j]=0;


    for (int i=0; i<numLines; i++)
        for (int j=0; j<numCols; j++)
        {
            if(img[i][j]=='1'&&imgL[i][j]==0)
            {
                imgL[i][j]=label;
                floodFill (u,v,label,img,imgL);
                label++;
            }
        }
}

Answer 1

I stripped out a ton of your code since it wasn't really relevant and refactored it a bit.

I didn't really keep track of each change, but from what I remember:

1. u and v are passed in and overwritten with 0,0 so nothing else is ever tested.
2. The check for a valid position never passed because img[p.x][p.y]==1 needed to be img[p.x][p.y]=='1'. If I was you I'd ditch the whole char thing and just use ints.
3. img was being modified, not imgL.
4. There's an infinite loop because the check for if a point should be added doesn't check imgL for being visited already.

This seems to give the desired output:

#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <string>

using namespace std;

typedef vector<vector<char> > Image;
typedef vector<vector<int> > ImageLabels;

void showImage(ostream &f, const Image &img)
{
    for(size_t i = 0; i < img.size(); i++)
    {
        for(size_t j = 0; j < img[i].size(); j++)
        {
            f << setw(3) << img[i][j];
        }
        f << endl;
    }
}

void showImageLabelling(ostream &f, const ImageLabels &imgL)
{
    for(size_t i = 0; i < imgL.size(); i++)
    {
        for(size_t j = 0; j < imgL[i].size(); j++)
        {
            f << setw(3) << imgL[i][j];
        }
        f << endl;
    }
}

void readImage(istream &f, Image &img)
{
    unsigned int numLines, numCols;

    f >> numLines;
    f >> numCols;

    img.resize(numLines);
    for(unsigned int i = 0; i < numLines; i++)
    {
        img[i].resize(numCols);
    }

    for(unsigned int i = 0; i < numLines; i++)
    {
        for(unsigned int j = 0; j < numCols; j++)
        {
            f >> img[i][j];
        }
    }
}

struct Point
{
    Point(int x_, int y_)
    : x(x_)
    , y(y_)
    {}

    int x;
    int y;
};

bool Valid(size_t x, size_t y, const Image& img, const ImageLabels& imgL)
{
    if(x >= img.size() || y >= img[0].size())
    {
        return false;
    }
    return img[x][y] == '1' && imgL[x][y] == 0;
}

void floodFill(int x, int y, int label, Image &img, ImageLabels &imgL)
{
    static const Point dir[4] =
    {
        Point(-1,  0),
        Point( 0, -1),
        Point( 0, +1),
        Point(+1,  0)
    };

    vector <Point> stack;
    stack.push_back(Point(x, y));

    while(!stack.empty())
    {
        Point p = stack.back();
        stack.pop_back();

        imgL[p.x][p.y] = label;

        for(int i = 0; i < 4; ++i)
        {
            int nx = p.x + dir[i].x;
            int ny = p.y + dir[i].y;
            if(Valid(nx, ny, img, imgL))
            {
                stack.push_back(Point(nx, ny));
            }
        }
    }
}

void imageLabeling(Image &img, ImageLabels &imgL)
{
    const size_t numLines = img.size();
    const size_t numCols = img[0].size();

    imgL.resize(numLines);
    for(unsigned int i = 0; i < numLines; i++)
    {
        imgL[i].resize(numCols, 0);
    }

    int label = 1;
    for(size_t i = 0; i < numLines; i++)
    {
        for(size_t j = 0; j < numCols; j++)
        {
            if(img[i][j] == '1' && imgL[i][j] == 0)
            {
                imgL[i][j] = label;
                floodFill(i, j, label, img, imgL);
                label++;
            }
        }
    }
}

int main()
{
    Image imgResult;
    ImageLabels imgL;

    ifstream inFile("img1.txt");
    readImage(inFile, imgResult);

    cout << "Initial:\n";
    showImage(cout, imgResult);
    cout << "\n";

    imageLabeling(imgResult, imgL);

    cout << "After Label:\n";
    showImageLabelling(cout, imgL);
    cout << endl;

    return 0;
}