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);
}
}
Iterative FloodFill or alternative.
Author
Hi,
Does anyone know how to implement an iterative FloodFill? Or can suggest an alternative algorithm which fullfills the same task?
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
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
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:
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 :)
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 :)
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
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
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.
Author
Hi sorry for taking a while to reply.
Thanks for offering your advice, Zahlman your solution is very nice! There is a typo here:
which should read
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:
but that caused no noticable speed difference.)
Thanks for offering your advice, Zahlman your solution is very nice! There is a typo here:
if (filled.find(neighbours) != notFound) {which should read
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.)
The code we did use in an old Win32 virtual printer device:
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,
#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,
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.
It supports filling with pattern, including pattern with one of colors equal to color of area to be filled.
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.
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.
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 :) )
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 :) )
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
