Fill algorithm

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

 

Log in or Sign up to hide all adverts.

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

 

Log in or Sign up to hide all adverts.

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?

 

Log in or Sign up to hide all adverts.

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;
}

 

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

 

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.

 

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

-AntonK

 

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.