flood fill with recursion

Programming Questions

jane38

in Programming Questions • 5 months ago

just a while ago I came across recursive methods

no idea why I had not come across it before since they can be good

any way I tried to make a flood fill method what do you know I got stackover flow error

wonder if any of you guys have any ideas

I did look around online some suggested increasing the JVM stack size

but said that the best was to find a way to break out of th recursion

which is what I would like

below code more or less works except for large areas

color old= color(255);
void setup()
{
size(500,500);
background(255);
strokeWeight(5);
for(int i=0; i<30;i++)
{
line(random(height),0,0,random(width));
}
}
void draw()
{
}
void mousePressed(){
old=get(mouseX, mouseY);
Fill(mouseX,mouseY,old, color(random(200,255),255,200));
}
void Fill(int x,int y,color oldColor,color newColor){
if(get(x,y)!= oldColor)
return;
//&&x>height&&y>width&&x<0&&y<0
set(x,y,newColor);
Fill(x + 1, y, oldColor, newColor);
Fill(x - 1, y, oldColor, newColor);
Fill(x, y + 1, oldColor, newColor);
Fill(x, y - 1, oldColor, newColor);
}

Replies(5)

thomas.di..

yes, in java there's a limited stacksize. So too deep recursions (floodfill is a good example to show this) results
in a stackoverflow.

But, every recursion can be rewritten as a stack/queue based solution, which may seem a bit complicated at first, but really isnt as soon as the concept of a recursion is clear to you.

simply said:
the signature (argument-values) of the recursive function
"Fill(int x,int y,color oldColor,color newColor)"
is "pushed" on the stack for each call. when unwinding those values are "popped" from there.
when you look at the above line, it seems clear that you just need to make a class that can hold exactly those arguments.

// untested!
class Fill{
int x, y;
color oldColor, newColor; // maybe obsolete because doesnt change?
}

when searching for "floodfill java stack" the first link i get is this one:
http://stackoverflow.com/questions/2783204/flood-fill-using-a-stack
where your current version is used and is rewritten as a queue-based version.

GoToLoop

Re: flood fill with recursion

5 months ago

The way Processing deals w/ colors isn't as science proof as most might think.

Even when all used colors are 100% opaque, when a drawing is done above the other,

the resultant color can be slightly different from the 1 used for 1 or more RGB channels!

So, there's no 100% guarantee that the color used in set(x, y, newColor); ends up exactly as newColor!

I had to deal w/ it on the sample maze game below.

At 1st, I've only fixed the blue channel. Took me some time to fix the others.

For they needed compensation on color checking

for possible variations on each red, green & blue channels of the maze's walls:

http://forum.processing.org/topic/trying-to-display-a-character-on-top-of-my-maze

Also, take a look at this recent post about Processing's blending of colors and transparency:

http://forum.processing.org/topic/about-color-alpha-problem

amnon.owed

Re: flood fill with recursion

5 months ago

I just posted a queue-based floodfill implementation in Processing here:
https://forum.processing.org/topic/find-unreachable-parts-of-an-image#25080000002137225

jane38

Re: flood fill with recursion

5 months ago

truthfully already had something like that but the recursion was a lot simpler and it was a new concept me (very suprising I had not come across it before)

what I had before before

PS: thanks very much for the cool answers gonna take some time to read them all

public void Fill(int x, int y) {
if(get(x,y) != ReplacementColor) {
int PixelArray[] = new int[1920*1080];
int Arraysize = 0;
PixelArray[0] = (y << 16) + x;
Arraysize = 1;
set(x, y, ReplacementColor);
while (Arraysize > 0){
Arraysize--;
x = PixelArray[0] & 0xffff;
y = (PixelArray[0] >> 16) & 0xffff;
//ListSize--;
PixelArray[0] = PixelArray[Arraysize];
if ((x > 0&&x < width)&& (y>0 &&y < height)) {
if ((get(x-1, y) == TargetColor)) {
set(x-1, y, ReplacementColor);
PixelArray[Arraysize] = (y << 16) + x-1;
Arraysize++;
}
if ((get(x, y-1) == TargetColor)) {
set(x, y-1, ReplacementColor);
PixelArray[Arraysize] = ((y-1) << 16) + x;
Arraysize++;
}
if ((get(x+1, y) == TargetColor)) {
set(x+1, y, ReplacementColor);
PixelArray[Arraysize] = (y << 16) + x+1;
Arraysize++;
}
if ((get(x, y+1) == TargetColor)) {
set(x, y+1, ReplacementColor);
PixelArray[Arraysize] = ((y+1) << 16) + x;
Arraysize++;
}
}
}
}
}

PhiLho

Re: flood fill with recursion

5 months ago

See also https://www.google.com/search?as_sitesearch=processing.org&as_q=flood+fill
...
I particularly recall a thread: http://processing.org/discourse/yabb2/YaBB.pl?num=1138719727
where I adapted some existing code.
See also http://bazaar.launchpad.net/~philho/+junk/Processing/files/head:/_SmallPrograms/ShowFloodFill/

This algorithm works well, even on complex shapes.
Ah, looking again, it also uses a stack, not recursion...
And code could use a little update...

Top Reply