# Fill algorithm

Discussion in 'Computer Science & Culture' started by AntonK, Jul 31, 2003.

Not open for further replies.
1. ### AntonKTechnomageRegistered Senior Member

Messages:
1,083
Here's a question for you guys...more of a challenge really. I have something that already works so if no one comes up with anything its okay. But here goes:

What do you think the best fill (think floodfill) algorith is that is NOT recursive. We all know you can simply do the basic

pseudo:
Code:
fill(x,y,old_color,new_color)
if ( image(x,y) == old_color)
image(x,y) = new_color
fill(x+1,y)
fill(x,y+1)
fill(x-1,y)
fill(x,y-1)

That of course always works...but it is slow and fills the call stack too easily and can crash. What do you guys think the best one is?

-AntonK

to hide all adverts.
3. ### okinrusRegistered Senior Member

Messages:
2,669
I think you could do something like this for linkedlist L of neighbors and let n be the number of nodes we found neighbors of. As long as the linkedlist is implemented so that it allocates most of the memory in chunks, I don't think it would be that slow.

1. n = 0
2. Add the starting position to L
3. For L.get(n), add all the neighbors in the vertical and horizontal directions to L.
4. n++
5. if n < L.size() goto 3 else terminate

to hide all adverts.
5. ### CrystalRegistered Senior Member

Messages:
50
What in the hell are you talking about.

Where in the hell do I learn about algorithms.

Is that above calculus? Is it a math at all or more of a logic and computer programming thing?

to hide all adverts.
7. ### okinrusRegistered Senior Member

Messages:
2,669
hmm maybe I will try to re-explain it. Sometimes it's easier to read an algorithm as a set of well defined directions in order to make a recipe. Basically this algorithm is how you would do it with pencil and paper. If you trace out the steps it should work.

Probably you would start out with insertion sort, merge sort and quick sort. Then maybe depth first search, which is what the algorithm AntonK just posted is basically.

Here's some code though. You might want to change it so that it considers diagonal nodes as neighbors.

Code:
#include <iostream>
using std::cout;
using std::endl;

struct Point {
int x; int y;
Point() : x(0), y(0) { }
Point(int xx, int yy) : x(xx), y(yy) { }
};

const int M = 10;
const int N = 10;

void floodFill(int grid[][N], int x, int y, int oldColor, int newColor)
{
Point lst[M * N];
int n = 0;
int sz = 0;

if (grid[y][x] == oldColor) {
grid[y][x] = newColor;
lst[sz++] = Point(x, y);
}

while(n < sz) {
x = lst[n].x;
y = lst[n].y;

// add neighboring nodes
for (int i = 1; i + x < N; ++i) {
if (grid[y][i + x] == oldColor) {
lst[sz++] = Point(i + x, y);
grid[y][i + x] = newColor;
} else {
break;
}
}

for (int i = 1; x - i >= 0; ++i) {
if (grid[y][x - i] == oldColor) {
lst[sz++] = Point(x - i, y);
grid[y][x - i] = newColor;
} else {
break;
}
}

for (int i = 1; i + y < M; ++i) {
if (grid[y + i][x] == oldColor) {
lst[sz++] = Point(x, i + y);
grid[y + i][x] = newColor;
} else {
break;
}
}

for (int i = 1; y - i >= 0; ++i) {
if (grid[y - i][x] == oldColor) {
lst[sz++] = Point(x, y - i);
grid[y - i][x] = newColor;
} else {
break;
}
}

n++;
}
}

void printGrid(int grid[][N])
{
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cout << grid[i][j] << ' ';
}
cout << '\n';
}
}

int main(void)
{
int grid[M][N] =
{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

cout << "before floodfill" << endl;
printGrid(grid);
floodFill(grid, 5, 5, 1, 2);
cout << "after floodfill" << endl;
printGrid(grid);

return 0;
}


8. ### AntonKTechnomageRegistered Senior Member

Messages:
1,083
Ill give that a try...I think mine may be a bit faster. Anyone else have any ideas?

Crystal? How old are you? You've never heard the world algorithm? Perhaps you're in the wrong forum.

Please Register or Log in to view the hidden image!

But really, look into some basic books. Algorithms can be far more complex than mathematical functions because they can include logical decision making within the functions themselves. Try to get a lowlevel computer science book.

-AntonK

9. ### malkiriRegistered Senior Member

Messages:
198
You could always use the recursive version but use your own stack:

Push first cell onto the stack
While stack not empty,
Pop off the top cell -> current location
Fill current location
Push current location's appropriate neighbors

The stack will be the size of the frontier, which can vary depending on where you start.

Last edited: Aug 1, 2003
10. ### AntonKTechnomageRegistered Senior Member

Messages:
1,083
Thats what im currently doing. And since my own stack is pretty fast, the algorithm is pretty fast. Anyone know of anything faster?

-AntonK

11. ### malkiriRegistered Senior Member

Messages:
198
How much faster do you want?

Please Register or Log in to view the hidden image!

To fill an entire area, you'll have to color each cell, so you can't do better than the size of the area. Both recursive versions are of linear complexity. The only way I can see that you can save anything is to do some sort of preprocessing. For example, to get rid of the conditional that would make sure a neighbor is the color to replace, you'd need a list of all the cells you want to fill.