I have an assignment to fill the difference between two overlapping circles with a 4-way recursive Flood_Fill algorithm in MATLAB. I pick the starting point with a mouse. I created a function for it.
function [] = Flood_Fill(M,x,y,new_color,old_color,border_color)
if(x < 0 || y < 0 || x >= 60 || y >= 60 || M(x,y) ~= old_color) % M is a 60x60 array
return
else
M(x,y) = new_color;
pause(0.16);
image(M');
Flood_Fill(M,x+1,y,new_color,old_color,border_color);
Flood_Fill(M,x-1,y,new_color,old_color,border_color);
Flood_Fill(M,x,y+1,new_color,old_color,border_color);
Flood_Fill(M,x,y-1,new_color,old_color,border_color);
end
disp("looped");
end
I call this function in my program and it does work, partially, it starts to fill the circle. But when it detects a corner it doesn't fill it, leaving a non-coloured pixel. It also "forgets" that it ever drew over pixels when it "returns". For example, here it goes into an infinite loop because it draws a line, meets 3 adjacent already drawn pixels, returns, and does it again (the empty space on the bottom right of the brightly coloured patch): Flood fill algorithm entered a loop
As far as I can tell my algorithm seems ok, but I do not know why it forgets that it has set M(x,y) = new_color. I also do not see how the program will ever complete even if it has filled the circle, once it "returns" it forgets the drawn pixels so it's bound to get stuck. I am really at a loss, I'm not really familiar with MATLAB.
An 8-way algorithm works better, but it means I have to draw the border of the circles to be at least 2 pixels, so that I don't overlap it. I tried to increase my search region, for example, looping x+n (where n = 1,2,3...) in all the recursive calls, obviously that gave off an error... I tried to add some "edge cases" where it would jump a row or fill a pixel next to the border, but as I stated it forgets that ever happened. It also looked horrible code-wise. In all the material for flood fill on the internet, it just seems to fill the space. I'm stuck with trying to do it with a recursive algorithm. Could MATLAB be the issue? Everything else works fine, it's just the flood fill that is not working correctly.
Additionally: To better explain. I tried debugging it, it seems that when the return condition is met, it forgets the last drawn pixel and puts it in the old_color. It does this even with adding memory to the function (x_prev,y_prev arguments) and setting it to draw the M(x_prev,y_prev) = new_color. It acts as if it is searching for a path between two points in a maze, when it goes in a wrong direction it goes back and starts in another direction
function M = Zadacha_4_Fill_Recursion(M,x,y,new_color,old_color,border_color,x_prev,y_prev)
if(x < 0 || y < 0 || x >= 60 || y >= 60 || M(x,y) ~= old_color )
fprintf("return cond: x = %d, y = %d\n", x,y);
if(M(x,y) ~= border_color)
fprintf("erase_not: x = %d, y = %d | x_prev = %d, y_prev = %d\n", x,y,x_prev,y_prev);
M(x_prev,y_prev) = new_color;
x_prev = x;
y_prev = y;
end
pause(1.2);
image(M');
return
else
M(x,y) = new_color;
x_prev = x;
y_prev = y;
pause(0.3);
image(M');
fprintf("normal: x = %d, y = %d | x_prev = %d, y_prev = %d\n", x,y,x_prev,y_prev);
Zadacha_4_Fill_Recursion(M,x+1,y,new_color,old_color,border_color,x_prev,y_prev);
Zadacha_4_Fill_Recursion(M,x-1,y,new_color,old_color,border_color,x_prev,y_prev);
Zadacha_4_Fill_Recursion(M,x,y+1,new_color,old_color,border_color,x_prev,y_prev);
Zadacha_4_Fill_Recursion(M,x,y-1,new_color,old_color,border_color,x_prev,y_prev);
end
%disp("looped");
end ```
In MATLAB you pass arguments by value, when you change M in your function, you change a copy of it. You need to return the modified M for your code to work:
function M = Flood_Fill(M,x,y,new_color,old_color,border_color)
% ^^^
if(x < 0 || y < 0 || x >= 60 || y >= 60 || M(x,y) ~= old_color) % M is a 60x60 array
return
else
M(x,y) = new_color;
%pause(0.16);
%image(M');
M = Flood_Fill(M,x+1,y,new_color,old_color,border_color);
M = Flood_Fill(M,x-1,y,new_color,old_color,border_color);
M = Flood_Fill(M,x,y+1,new_color,old_color,border_color);
M = Flood_Fill(M,x,y-1,new_color,old_color,border_color);
% ^^^
end
%disp("looped");
end