Алгоритм заполнения Flood в C ++

Question

Я пытаюсь написать код, который будет выполнять заливку цвета на изображении, и я использую стеки. (Все еще плохо знакомы со стеками и очередями, поэтому я не уверен, какая из них будет лучшей идеей). Во всяком случае, я думаю, что я понял основную идею, но есть недостаток в моем коде:

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;  

}

Так что я думаю, что проблема, или мне кажется, по крайней мере, заключается в том, что при посещении соседних узлов я посещаю одни и те же узлы каждый цикл, верно? Какой обходной путь к этому?

Answer 1

В стеке вы должны сохранять координаты, а не цвет.Вместо сохранения *img(x+1,y) вам нужно сохранить только x+1,y.Вы можете сделать это, возможно, с struct, который содержит обе координаты.

Сохранение координат позволяет вам перемещаться по региону, который вы заполняете.Сохранение цвета на самом деле не имеет никакого смысла.

Вы могли бы найти эту ошибку самостоятельно, шаг за шагом войдя в код с помощью отладчика и представив, что вы толкаете в стекчто это выходит из стека.

Точное понимание алгоритма, прежде чем пытаться его реализовать, также помогает.Чтобы получить это понимание, вы можете запустить алгоритм вручную с ручкой и бумагой на примере маленькой игрушки.