洪水填充功能不起作用

Question

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

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

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'。 如果我是你，我会抛弃整个字符的东西，只使用整数。
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;
}