Archived

This topic is now archived and is closed to further replies.

miikkal

Replacing color with another one

Recommended Posts

miikkal    122
Hi Take a look this picture So I'm asking the fill function. I have done something like this, but it doesn't work, I don't know why? This function works about 90% of time. pseudo code...
      
Fill(x,y)
{
  block[x][y]=-block[x][y]

  for( j<height )
  {
    for( i<width )
    {
      if( block[i][j]<0 )
      {
        if in left,right,top or bottom block has same value than block[x][y]
        then
          block[found_x][found_y] = -block[found_x][found_y]

        block[i][j]=fill_color

        i=j=0 //Start from beginning

        
      }
    }
  }
}
  
Miikka Laakso www.miikkalaakso.net [edited by - miikkal on October 21, 2002 8:26:17 AM]

Share this post


Link to post
Share on other sites
civguy    308
Uhh.. I understand the algo but it''s *really* slow. It should work if your map consists only of positive signed values (int, char), so the problem is probably in the code or in the data you use.

And I presume this

  
if in left,right,top or bottom block has same value than block[x][y] then

should be

  
if in left,right,top or bottom block has same value than -block[x][y] then

(grammar errors ignored)

Share this post


Link to post
Share on other sites
miikkal    122
Well I decided to do it another way. I think it''s a lot faster than previous one, here it is:


  

//function Fill( where x,y is coordinates, and c is color we want to replace )


void Fill( int x, int y, int c )
{
if( game.block[x_limit(x)][y_limit(y)].c == c )
{
game.block[x_limit(x)][y_limit(y)].c = fill_color;

Fill( x-1, y, c );
Fill( x+1, y, c );
Fill( x, y-1, c );
Fill( x, y+1, c );
}
}

Share this post


Link to post
Share on other sites
Michalson    1657
The big problem with recursive fill functions is that while they look good on paper or to a uni professor who has never actually touched a computer, they tend to cause a stack overflow on anything but the smallest images.

Share this post


Link to post
Share on other sites
miikkal    122
Although I have small image and it work's fine, what would be the ideal solution for the fill-function?

Miikka Laakso
www.miikkalaakso.net

[edited by - miikkal on October 23, 2002 6:20:52 AM]

Share this post


Link to post
Share on other sites
ragonastick    134
What I have done when I need a fill function is to create my own "stack", I rarely need these functions, so this is possibly not the quickest method, but usually is consists of some type of container (such as an array or a vector) which stores the pixels which need to be updated. Every iteration of the fill function goes through and does what is needed for each pixel in the container and with the new pixels filled form the contents of the container for the next iteration. When that container is empty, the thing is filled.

The reason you need to create your own stack is because the size of the stack allocated for your program will usually not be very large because it isn''t designed for these huge recursive functions. By doing it this way, you decide how much memory to allocate and can reallocate at any time.

Trying is the first step towards failure.

Share this post


Link to post
Share on other sites
civguy    308
Something like this might work (not tested, maybe won''t compile or work without some
tweaking)

  
#include <utility>

#include <stack>


void Fill( int x, int y, int c )
{
int replacedColor = game.block[x][y].c;
game.block[x][y].c = c;
std::stack<std::pair<int,int> > open;
open.push(std::make_pair(x, y));

while (open.size()) {
std::pair<int, int> topPair = open.top();
x = topPair.first;
y = topPair.second;
open.pop();
if (game.block[x_limit(x+1)][y].c == replacedColor) {
game.block[x_limit(x+1)][y].c = c;
open.push(make_pair(x_limit(x+1), y));
}
//do the same for all 4 directions, not just x+1

}
}

Share this post


Link to post
Share on other sites