c++ - 洪水填充功能不起作用

Question

我想对 2D 图像进行洪水填充，但我总是得到相同的结果。

程序非常简单。它从包含 0 和 1 的 txt 文件中读取二维图像，并应用洪水填充算法的深度优先变体:

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;
        }
    }
}

下面是图片标注代码:

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

我删除了大量您的代码，因为它们并不真正相关，并对其进行了一些重构。

我并没有真正跟踪每一个变化，但根据我的内存:

1. u 和 v 被传入并被 0,0 覆盖，因此不会测试任何其他内容。
2. 对有效位置的检查从未通过，因为 img[p.x][p.y]==1 需要为 img[p.x][p.y]=='1'。如果我是你，我会放弃整个 char 的东西，只使用 int。
3. img 被修改，而不是 imgL。
4. 存在一个无限循环，因为检查是否应添加一个点不会检查 imgL 是否已被访问。

这似乎给出了所需的输出:

#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;
}