Ok, here''s the story: Lets say i have an image, consisting of pure, rectangular raster data. I know the exact ''pixel'' or ''image unit'' or whatever we''ll call it, where to start a floodfill. What''s the most efficient way of accomplishing this? Note: the raster data is in this format (number = position in memory array): Example is a 4x4 image. 1 4 8 12 2 5 9 13 3 6 10 14 4 7 11 15 Any ideas?

The easiest way to do a flood fill is to use recursion:

  // color all adjacent pixels that same color as colAt[x][y] to// new color col; // assumes a global array of colors colAt[maxx][maxy]void startFloodFill(int x, int y, int col){  if(col==colAt[x][y]) return;   doFloodFill(x,y,colAt[x][y],col);}void doFloodFill(int x, int y, int col1, int col2) {  // check if we''re out of bounds or we''re the wrong color  if(x<0 || x>=maxx|| y<0 || y>=maxy || colAt[x][y]!=col1)     return;  colAt[x][y] = col2;  // now look adjacent; don''t worry about repetition since  // once we get to a square we will recolor it and it won''t  // be valid anymore  doFloodFill(x-1,y,col1,col2);  doFloodFill(x+1,y,col1,col2);  doFloodFill(x,y-1,col1,col2);  doFloodFill(x,y+1,col1,col2);}  

HTH

Thank you, man.
Rather clever algorithm

At Byondo's request:

Think about it Byondo, you're going to make 4 function calls per pixel!

Just changing the algorithm so that you test
if(x<0 || x>=maxx|| y<0 || y>=maxy || colAt[x][y]!=col1)
before you make the function call instead of afterwards would make it faster!


A good floodfill would use both algorithms, recursively calling this on the edges... if you've ever watched a flood fill on a slow computer this looks like how they do it. It fills in a closed shape, then goes and checks around the edges to see if we missed a dip and fills those in.

          //Note this only works on simple polygons//If you want a true floodfill, i think you have to use recursion//If you want to fill a closed simple shape, this is slightly fasterScanline_FloodFill(int x, iny y, int col)	{	int org;	if(col==colAt[x][y])		return;	else		org = colAt[x][y];	for(int j=y;j<maxY;j++)		for(int i=x+1;i<maxX;i++)			{			if(colAt[ i][j]!=org)				break;			else				colAt[ i][j]=col;			}	for(int j=y;j<maxY;j--)		for(int i=x-1;i<maxX;i--)			{			if(colAt[ i][j]!=org)				break;			else				colAt[ i][j]=col;			}	}          

Edited by - Magmai Kai Holmlor on November 12, 2000 3:19:38 PM

I admire your passion, and appreciate your response!

quote: Original post by Magmai Kai Holmlor

Think about it Byondo, you're going to make 4 function calls per pixel!

Just changing the algorithm so that you test
if(x<0 || x>=maxx|| y<0 || y>=maxy || colAt[x][y]!=col1)
before you make the function call instead of afterwards would make it faster!

Okay, but that falls into the category of "anal optimizations" that shouldn't even be considered until the algorithm is completely set in stone. I concur that it is a negligeable overhead in the grand scheme of things, but if you'd like to do some timing tests involving function calls I'd be glad to look at the results.

In truth, the quickie-recursion method could be optimized a lot more, because depending on the direction of search, part of the "if" statement won't have to be evaluated. But again, I think that is nitpicking and won't change the performance.

The reason why the recursive algorithm is acceptable is that it makes at worst 4N calls, where N is the number of pixels that will be filled in. While each of these calls may be slower than the iterative counterpart (which would avoid the function call), this effect will most likely be negligeable once you realize that the bottleneck in the code is going to be the action of actually filing in the pixel on the screen (or in the memory bitmap or whatever). So, yes, it's not necessarily optimal, but in almost all implementations it won't matter.

Your algorithm is not acceptable because, as you noted, it doesn't actually do a flood fill. It's easy to say, "do this and then call the recursion on the edges", but to me that's just restating the problem. Which edges? How are you tracking them? What if your center point isn't an enclosed polygon but floods into one? Is that case done efficiently? My point in the other thread was that tracking these issues is what makes the interative version hackier (and in many cases more inefficient) than the simple recursion.

Besides, your argument was that recursion is unnecessary for most cases (something about depths > 2, although I don't think I understood the argument there). Does this qualify? It would do your case a lot more good if you did this completely with iteration, but methinks that's pretty tricky!

***

I should note that my original recursion algorithm is pretty bad, but not for the efficiency reasons you noted. Rather, its quite easy to get a stack overflow when doing a block fill of large empty spaces. One solution is to do some sort of pre-fill, as you've illustrated, but I think that a malicious user can make test cases that would stump any simple iterative routine. A better solution, in my opinion, is to simply manage the stack depth yourself. When the stack depth is infinite, we have pure recursion; when it is 1, we have (poorly implemented) iteration.

Here is an improved version of the recursive algorithm with a fixed stack size:

  // example parameters#define maxx 1000#define maxy 1000#define maxdepth 32  // how deep can we go?int colAt[maxx][maxy];#include <math.h>static int doFloodFill(int x, int y, int col1, int col2, int depth) {	// check if we're out of bounds or we're the wrong color	if(x<0 || x>=maxx|| y<0 || y>=maxy || (colAt[x][y]!=col1 && colAt[x][y]!=-1))		return 0;	if(depth==maxdepth) {		colAt[x][y] = -1; // mark for next round so we don't overflow stack		return 1; 	}	colAt[x][y] = col2;	// now look adjacent; don't worry about repetition since	// once we get to a square we will recolor it and it won't	// be valid anymore	return doFloodFill(x-1,y,col1,col2,depth+1)|		   doFloodFill(x+1,y,col1,col2,depth+1)|		   doFloodFill(x,y-1,col1,col2,depth+1)|		   doFloodFill(x,y+1,col1,col2,depth+1);}// color all adjacent pixels that same color as colAt[x][y] to// new color col; // assumes a global array of colors colAt[maxx][maxy]static void startFloodFill(int x, int y, int newCol){	int oldCol = colAt[x][y];	if(oldCol==newCol) return;	int repeat = doFloodFill(x,y,oldCol,newCol,0);	while(repeat) {		repeat = 0;		for(y=0;y<maxy;y++) {			for(x=0;x<maxx;x++) {				if(colAt[x][y]==-1) {					repeat |= doFloodFill(x,y,oldCol,newCol,0);				}			}		}	}}void main(){	startFloodFill(0,0,1);}  

This example tests the worst-possible scenario: filling a massive space completely. On my machine, it performs quite speedily. Again, the bottleneck will almost be guaranteed to be in the actual GDI fill.

I've gone at at length here because I think it's important for people to realize that recursion is a valuable asset if used properly. These examples have been coded hastily, but even they seem to perform relatively well. One should never discard potential powerful tools just because there may be slightly more optimal alternatives; readibility, ease of use, and simplicity are often more important factors than overall speed, espeically when the bottleneck lies elsewhere!

Edited by - byondo on November 12, 2000 12:34:32 AM