Sign in to follow this  

Iterative FloodFill or alternative.

This topic is 4689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, Does anyone know how to implement an iterative FloodFill? Or can suggest an alternative algorithm which fullfills the same task?
void FloodCopy(int x, int y) {
	if (x<1) return;
	if (y<1) return;
	if (x>(greywidth-1)) return;
	if (y>(greyheight-1)) return;
	if (objFrame[x+y*greywidth]) return; //already visited
	if (greyFrame[x+y*greywidth]==0) {
		objFrame[x+y*greywidth]=255;
		FloodCopy(x+1,y);
		FloodCopy(x-1,y);
		FloodCopy(x,y+1);
		FloodCopy(x,y-1);
	}
}
I've tried just increasing the stack size in the compiler, but it never seems to be enough.. Thanks.

Share this post


Link to post
Share on other sites
You need an iterative algorithm. Definetly.

Theres one, that is one of mine (look in my profile), it is "Commonly used algorithms" or something like that. That has an implementation of an iterative floodfill, along with heaps of nicve stuff.

Please go and add something there too, even if its just advise on which algorithm to implement.

From,
Nice coder

Share this post


Link to post
Share on other sites
Nice Coder could you post a link? I'm having trouble finding it after going through your posts...

As for my own ideas, the simplest way to make it iterative is to use a queue and push positions you want to fill next onto it.

Pseudocode since I'm actually procrastinating on studying for an exam:


FloodCopy(int x, int y) {
if (out of bounds) return;

queue positions;
positions.push(x, y);

while (positions not empty) {
x, y = positions.pop();

// flood or do something to x, y

// push neighbors of x, y
positions.push(x+1,y);
positions.push(x-1,y);
positions.push(x,y+1);
positions.push(x,y-1);
}
}




The recursive algorithm isn't really safe since image size is limited by stack space. This approach can be improved, hopefully someone else can help here :)

Share this post


Link to post
Share on other sites
Second topic from the top

I would recommend a list to store the data.

All of the data is stored sorted, allowing o(log2 n) read time.

It also stops your app from going in circles and dying (which yours will do, sorry to say).

You go and you keep a pointer to the end of where you've been. (you start it off with two elements, one that its already seen, and one that it hasn't).

When decommisioning an item, you go and you increment the pointer for the one that you have already seen, and you swap the item for the thing you want to decomission.

i would recomment a vector to keep the data, and it will eventually be quite big...

From,
Nice coder

Share this post


Link to post
Share on other sites

void floodFill(int initialX, int initialY, bool(*fillCondition)(int, int)) {
// The passed in function should fill the specified point and return true
// if it should be filled; otherwise it should just return false.

// Containers to store the set of points that we need to fill around, and
// the set of points we've already filled.
typedef std::set<std::pair<int, int> > PointContainer;
PointContainer exposed, filled;
exposed.insert(make_pair(initialX, initialY));

while(!exposed.empty()) {
// Remove one of the 'exposed' points and examine it, extracting coordinates
PointContainer::iterator pi = exposed.begin();
int x = pi->first; int y = pi->second; exposed.erase(pi);
// If we can fill this spot, fill it, add it to filled set,
// and add unfilled neighbours to exposed set.
if (fillCondition(x, y)) {
// Add to filled set
filled.insert(make_pair(x, y));
// Generate the neighbours
std::pair<int, int>[4] neighbours = {
make_pair(x-1, y), make_pair(x+1, y),
make_pair(x, y-1), make_pair(x, y+1)
};
PointContainer::iterator notFound = filled.end();
for (int i = 0; i < 4; i++) {
if (filled.find(neighbours[i]) != notFound) {
exposed.insert(neighbours[i]);
}
}
}
}
}



Warning: off the top of my head, not at all guaranteed. Made reference to STL docs for std::set. It seemed like an appropriate datatype because of how I phrased the pseudocode description, and because a lot of lookups are done, plus the need for uniqueness of contents. However, you might find it makes more sense to keep the map for the 'exposed' list, but use a boolean array to check for filled-ness.

Share this post


Link to post
Share on other sites
Hi sorry for taking a while to reply.
Thanks for offering your advice, Zahlman your solution is very nice! There is a typo here:

if (filled.find(neighbours[i]) != notFound) {

which should read

if (filled.find(neighbours[i]) == notFound) {


Unfortunately Zahlmans generic solution was a bit slow for my application so I took nice coders advice of using a list to store the data (exposed). I also used my second buffer to replace the need for the 'filled' list. This gave me a fair speed boost but it's still a little slow, which I think is the fault of the 'std::list'.

Actually I just realised that a deque will do the job nicely, which I just tried, so now I pritty much ended up with mutex's solution. (it is a lot faster than a list)

So thanks everybody for thier help!

(I have tried replacing the std::pair with:

typedef struct {
short x,y;
} intpair;

but that caused no noticable speed difference.)

Share this post


Link to post
Share on other sites
The code we did use in an old Win32 virtual printer device:

#include <deque>
#include "Image.h"

template <class PIXEL>
void floodFill(const Image& img, const Point& pt, PIXEL oldcolor, PIXEL newcolor)
{
std::deque<COORD> fillStack;
PIXEL *ptr;
PIXEL *dataPtr;
Point coord;

fillStack.push_back(pt);

dataPtr = reinterpret_cast<PIXEL*>(Image.dataPtr);
while (!fillStack.empty()) {
coord = fillStack.front();
fillStack.pop_front();
ptr = dataPtr + coord.y * img.widthAlign + coord.x;
if (*ptr == oldcolor) {
*ptr = newcolor;
fillStack.push_back(Point(coord.x, coord.y + 1));
fillStack.push_back(Point(coord.x, coord.y - 1));
fillStack.push_back(Point(coord.x + 1, coord.y));
fillStack.push_back(Point(coord.x - 1, coord.y));
}
}
}


This code may need some extra work to be faster than it is. It also assume that we are using interleaved images - which may not be the case. If genericity is needed, something better should derived from this.

Anyway, I like Zahlman (change the function pointer to a functor perhaps).

Regards,

Share this post


Link to post
Share on other sites
I wrote very efficient floodfill some time ago, but it is in pascal...
it works per-scanline and have very small memory requirements. But is, indeed, quite complicated.

procedure Tgraph.Fill(x,y:longint);
type TfillPoint=record
y:longint;
lx,rx:longint;
lxs,rxs:longint;
dir:boolean;{up=true;down=false}
end;
type TdrawPoint=record lx,y,rx:longint; end;
TdrawArray=array[1..MaxFillLines] of Tdrawpoint;
type Farray=array[boolean,1..MaxFillLines] of {array[1..MaxFillLines] of} Tfillpoint;
PFarray=^Farray;
var AreaColor:dword;
a:PFarray;
drps:^TdrawArray;
drpsn:longint;
m:array[boolean] of longint;
_cur,LastP,newP,_dir:boolean;
var lx,rx,lxs,rxs:longint;
cx,CY,cy2:longint;
n:longint;
function ColorOK(x,y:longint):boolean;
begin
colorOk:=(x>=0)and(x<=Max.X)and(y>=0)and(y<=Max.y)and(GetPixel(x,y)=AreaColor);
end;
procedure StorePoint;
begin
inc(m[not _cur]);
if m[not _cur]>=MaxFillLines then begin
FontBack:=1;
Writeln('Too many filling points!!(more that ',MaxFillLines,')');
end;
a^[not _cur,m[not _cur]].lx:=cx;
a^[not _cur,m[not _cur]].lxs:=lx;
a^[not _cur,m[not _cur]].rx:=cx;
a^[not _cur,m[not _cur]].rxs:=rx;
a^[not _cur,m[not _cur]].y:=cy2;
a^[not _cur,m[not _cur]].dir:=_dir;
end;
procedure Scan(lx,rx:longint);
begin
{if xl>xr then exit;}
if (cy2 <= max.y)and(cy2>=0)and(lx<=rx) then
begin
cx:=lx;
if ColorOk(cx,cy2) then begin
dec(cx);
while ColorOk(cx,cy2) do dec(cx);
inc(cx);
StorePoint;
cx:=lx;
ScanE(cx,cy2,max.x,AreaColor);
{if ColorOk(cx,cy2)and(cx<rx) then begin Writeln('Cycle bug E1 ');readln;end;}
a^[not _cur,m[not _cur]].rx:=cx-1;
with a^[not _cur,m[not _cur]] do FillLine(lx,y,rx{-lx});
end;
while cx<=rx do begin
ScanNE(cx,cy2,rx,AreaColor);
if cx>rx then break;
{ if not ColorOk(cx,cy2) then begin Writeln('Cycle bug NE ,cx=',cx);readln;end;}
StorePoint;
ScanE(cx,cy2,max.x,AreaColor);
{ if ColorOk(cx,cy2)and(cx<rx) then begin Writeln('Cycle bug E2 ,cx=',cx);readln;end;}
a^[not _cur,m[not _cur]].rx:=cx-1;
with a^[not _cur,m[not _cur]] do FillLine(lx,y,rx{-lx});

end;{cycle}
end;
end;
var TempColor,LastColor:dword;
LastPattern:pFillpattern;
TempLineRQ:boolean;
begin
NormalizeColor(CurColor);
FontBack:=1;
AreaColor:=GetPixel(x,y);
if (AreaColor=CurColor)and(Pattern=nil) then exit;
TempLineRQ:=(CurColor=AreaColor)or((BackColor=AreaColor)and(Pattern<>nil));
LastPattern:=pattern;
if TempLineRQ then begin TempColor:=not(AreaColor);pattern:=nil; end else TempColor:=CurColor;
NormalizeColor(tempColor);
LastColor:=CurColor;
CurColor:=TempColor;
new(a);
new(drps);
drpsn:=0;
while ColorOk(x,y+1) do inc(y);
_cur:=true;
m[_cur]:=1;
a^[_cur,1].lx:=x;
a^[_cur,1].rx:=x;
a^[_cur,1].y:=y;
with a^[_cur,1] do begin
while ColorOk(lx-1,y) do dec(lx);
while ColorOk(rx+1,y) do inc(rx);
hLine(lx,y,rx);
end;
a^[_cur,1].lxs:=x;
a^[_cur,1].rxs:=x;
a^[_cur,1].dir:=true;
repeat
m[not _cur]:=0;
for n:=1 to m[_cur] do begin
cy:=a^[_cur,n].y;
lx:=a^[_cur,n].lx;
rx:=a^[_cur,n].rx;
lxs:=a^[_cur,n].lxs;
rxs:=a^[_cur,n].rxs;
_dir:=a^[_cur,n].dir;

{Scanning}
{ if GetPixel(lx,cy)<>TempColor then Writeln('???? error');
if GetPixel(rx,cy)<>TempColor then Writeln('???? error');}

if _dir then cy2:=cy-1 else cy2:=cy+1;
scan(lx,rx);

if _dir then cy2:=cy+1 else cy2:=cy-1;
_dir:=not _dir;
scan(lx,lxs-1);
scan(rxs+1,rx);
end; {cycle}

if TempLineRQ then begin
CurColor:=LastColor;
Pattern:=LastPattern;
for n:=1 to drpsn do with drps^[n] do FillLine(lx,y,rx);
drpsn:=m[_cur];
for n:=1 to drpsn do with a^[_cur,n] do begin drps^[n].lx:=lx;drps^[n].rx:=rx;drps^[n].y:=y; end;
Pattern:=nil;
CurColor:=TempColor;
end;
_cur:=not(_cur);{swap buffer}
{debug
MoveTo(0,460);
Write('Borders=',m[_cur]:6,' ');
delay(100);
}
if m[_cur]>MaxFronts then MaxFronts:=m[_cur];
until m[_cur]=0;
Pattern:=LastPattern;
CurColor:=LastColor;
for n:=1 to drpsn do with drps^[n] do FillLine(lx,y,rx);
dispose(a);
dispose(drps);
end;



It supports filling with pattern, including pattern with one of colors equal to color of area to be filled.

Share this post


Link to post
Share on other sites
After thinking about it some more...

Use an array of 2 bits per tile to indicate "exposed"/"filled"-ness, and also keep a list of exposed tiles. Then we can easily check for set membership immediately, and don't need a 'set' for the exposed tiles - a vector will be fine, being used as a stack. (Of course it is still better to keep this list rather than scanning the array every time to look for an exposed tile!)

Also, I'm going to template the fillCondition 'hook' so it can take either a function pointer or functor object.


template <typename T>
void floodFill(int initialX, int initialY, int width, int height, T fillCondition) {
// The passed in function should fill the specified point and return true
// if it should be filled; otherwise it should just return false.

// Containers to hold flags for which tiles are exposed and filled
// Initializing all of this to false may well be the slow part :/
vector<vector<bool> > exposed(width, vector<bool>(height, false));
vector<vector<bool> > filled(width, vector<bool>(height, false));

// List of exposed tiles
vector<pair<int, int> > workingSet;

workingSet.push_back(make_pair(initialX, initialY));
exposed[initialX][initialY] = true;

while(!workingSet.empty()) {
// Remove one of the 'exposed' points and examine it, extracting coordinates
pair<int, int> current = workingSet.back(); workingSet.pop_back();
int x = current.first; int y = current.second;
exposed[x][y] = false;
// If we can fill this spot, fill it, add it to filled set,
// and add unfilled neighbours to exposed set.
if (fillCondition(x, y)) {
// Mark as filled
filled[x][y] = true;
std::pair<int, int>[4] neighbours = {
make_pair(x-1, y), make_pair(x+1, y),
make_pair(x, y-1), make_pair(x, y+1)
};
for (int i = 0; i < 4; i++) {
int[2]& neighbour = neighbours[i]; // not sure I got that right
if (!filled[neighbours[i].first][neighbours[i].second])
exposed[neighbours[i].first][neighbours[i].second] = true;
workingSet.push_back(neighbours[i]);
}
}
}
}
}



And yeah, std::pair isn't the bottleneck here - it effectively is the struct you tried replacing it with. (But feel free to try it with shorts instead of ints anyway :) )

Share this post


Link to post
Share on other sites

This topic is 4689 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this