Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Flood Fill question

Posted on 1999-01-25
5
Medium Priority
?
671 Views
Last Modified: 2013-11-20
I obtained a flood fill algorithm from the net. It is a recursive function :

void floodFill(int x, int y, int fill, int old)
{
     if ((x < 0) || (x >= raster.width)) return;
     if ((y < 0) || (y >= raster.height)) return;
        if (raster.getPixel(x, y) == old) {
            raster.setPixel(fill, x, y);
            floodFill(x+1, y, fill, old);
            floodFill(x, y+1, fill, old);
            floodFill(x-1, y, fill, old);
            floodFill(x, y-1, fill, old);
        }
}

i would like to apply this function into program where can flood fill a map with a tile. But i encounter 1 problem, that is when the map size is huge (say 1000x1000), since this is recursive function, it might call itself 1000x1000 times, and thus it blown out the stack and crashes the program.
How am i going to solve this problem ?
0
Comment
Question by:eugeneng
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
5 Comments
 
LVL 3

Expert Comment

by:_Scotch_
ID: 1328287
You either need to rewrite it into a nonrecursive loop or section
your map into smaller pieces and floodFill them individually.
0
 
LVL 1

Expert Comment

by:dd_b
ID: 1328288
write your own stack using file & push all local variable when u call the function & pop on return.
0
 
LVL 1

Accepted Solution

by:
sunj earned 50 total points
ID: 1328289
Here is a non-recursive solution. Starting from a initial point(marked with FILLED), the function will enter a loop. For each loop, it scans through all the pixels in your map. Once it finds one pixel is marked with FILLED, it will try to mark some of its four neighbors as FILLED if they have the same color (just take care of the boundary). The loop terminates when there is no more change made to the map.

0
 
LVL 1

Expert Comment

by:arbitrary
ID: 1328290
u can enlarge the size of each pixel by drawing rects instead of lighting pixels.
say 4x4 of 8x8 or something similar it will save you time .
or you can save the old coordinates and draw a big rect, and then restore what you had before , which will do the same trick even better.
both - ways you save time and effort , if you like more details please notify.
0
 

Author Comment

by:eugeneng
ID: 1328291
hi arbitrary, actually my map contains tiles instead of pixel, but basically they are the same. can you method still applicable to my program ? because i gotto check tile's data, not only color? if you method is still applicable, can you give me more detail of it.
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Here is how to use MFC's automatic Radio Button handling in your dialog boxes and forms.  Beginner programmers usually start with a OnClick handler for each radio button and that's just not the right way to go.  MFC has a very cool system for handli…
Introduction: The undo support, implementing a stack. Continuing from the eigth article about sudoku.   We need a mechanism to keep track of the digits entered so as to implement an undo mechanism.  This should be a ‘Last In First Out’ collec…
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Visualize your data even better in Access queries. Given a date and a value, this lesson shows how to compare that value with the previous value, calculate the difference, and display a circle if the value is the same, an up triangle if it increased…

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question