# Iterative FloodFill or alternative.

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

## 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 (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 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 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 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 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) != notFound) {          exposed.insert(neighbours);        }      }    }  }}

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 on other sites
Hi sorry for taking a while to reply.
 if (filled.find(neighbours) != notFound) {

 if (filled.find(neighbours) == 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 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 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 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; // not sure I got that right        if (!filled[neighbours.first][neighbours.second])          exposed[neighbours.first][neighbours.second] = true;          workingSet.push_back(neighbours);        }      }    }  }}

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 :) )

1. 1
2. 2
3. 3
frob
20
4. 4
Rutin
20
5. 5

• 32
• 13
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
632560
• Total Posts
3007086

×