CODEWITHSUNDEEP
c++algorithmstack
iRobot
iRobot

Reputation: 79

Flood fill algorithm in c++

I'm trying to write code that will do a flood fill of a color on an image, and I'm using Stacks. (Still new to stacks and queues, so I'm not sure which one would be a better idea). Anyway, I think I got the basic idea down, but there's a flaw with my code:

animation DFSfill(BMP& img, int x, int y, colorPicker & fillColor, int tolerance, int frameFreq) {


Stack<RGBApixel> s;
s.push(*img(x,y));
int actualTol;
int height, width;
width=img.TellWidth();
height=img.TellHeight();
int counter=1;
animation finalAnimation;
RGBApixel top;

bool visited[width][height];
for(int i=0;i<width;i++)
    for(int j=0;j<height;j++)
        visited[x][y]=false;



while(!s.isEmpty()){
    top = s.peek();
    s.pop();

    actualTol=(top.Red-fillColor(x,y).Red)^2
+(top.Blue-fillColor(x,y).Blue)^2+(top.Green-fillColor(x,y).Green)^2;

    //check 
    if(x<0 || x>=width)
        continue;
    if(y<0 || y>=height)
        continue;
    if (visited[x][y]==true)
        continue;
    if(actualTol>tolerance)
        continue;

    visited[x][y]=true;
    img(x,y)->Red=fillColor(x,y).Red;
    img(x,y)->Blue=fillColor(x,y).Blue;
    img(x,y)->Green=fillColor(x,y).Green;
    counter++;

    //visit adjacent nodes


    s.push(*img(x+1, y));//right

    s.push(*img(x, y-1));//down

    s.push(*img(x-1, y));//left

    s.push(*img(x, y+1));//up

    if((counter%frameFreq)==0)
        finalAnimation.addFrame(img);
}

return finalAnimation;

}

So I think the problem, or to me it seems at least, is that when visiting adjacent nodes, I am visiting the same nodes every loop, right? Whats a workaround to this?

Upvotes: 1

Views: 3256

Answers (1)

shoosh
shoosh

Reputation: 78914

In the stack you are supposed to save the coordinates, not the color. Instead of saving *img(x+1,y) you need to save just x+1,y. you can do this possibly with a struct that holds both coordinates.

Saving the coordinates allows you to travel across the region you're filling. Saving the color doesn't really make any sense.

You could have found this bug on your own by stepping into the code with a debugger step by step and seem what it is that you are pushing into the stack and what it is that gets out of the stack.

A solid understanding of the algorithm before trying to implement it also helps. To get this understanding you can run the algorithm manually with a pen and paper on a small toy example.

Upvotes: 2

Related Questions