Archived

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

Replacing color with another one

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

Recommended Posts

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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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  }}

• Forum Statistics

• Total Topics
628686
• Total Posts
2984229

• 13
• 13
• 13
• 10
• 10