Article Preview
Buy Now
COLUMN
Seed Fill Algorithms
Different methods of implementing a "paint bucket" tool
Issue: 2.5 (May/June 2004)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 12,747
Starting Page Number: 34
Article Number: 2516
Resource File(s):
2516.zip Updated: 2013-03-11 19:07:58
Related Web Link(s):
http://www.strout.net/info/coding/rb/intro.html
Excerpt of article text...
Anyone who has ever used a paint program is familiar with the seed fill, whether they know it or not. Its most popular implementation is the paint bucket tool found in nearly all drawing programs, from the ancient MacPaint to a modern copy of Photoshop. Unfortunately, many developers, when confronted with the need for a paint bucket tool, don't know where to start.
The basic principle of the seed fill algorithm is very simple. It acts upon a grid of pixels and requires a "seed" point and a fill color. Beginning at the seed point, it changes the color of all pixels in a group contiguous with, and having the same color as, the seed pixel. The goal is achieved by visiting the neighbors of each pixel in turn. This is a very simple concept, but it turns out that
how you visit the neighbors makes a huge difference in the algorithm's efficiency.The first decision you must make is which neighbors to visit. There are two popular options. Visiting "4-connected" neighbors means to visit only those neighbors sharing a side with the pixel: above, below, to the left, and to the right. Visiting "8-connected" neighbors refers to visiting all neighbors surrounding the pixel, including those at a diagonal. Of the two, the 4-connected version of the algorithm is more popular, due to overflow issues with 8-connected neighbors. Consider the results shown in Figure 1! The 4-connected algorithm gives the results the user will expect. For the rest of this article, I will discuss only 4-connected solutions.
The simplest method for visiting each pixel is recursive. A recursive fill method would fill the indicated pixel, then call itself for each of the neighbors. Code for a RecursiveFill routine can be found in listing 1.
This is an incredibly simple and elegant solution. It is clear, short, and easy to understand. Unfortunately, it also possesses a tragic flaw. Recursion is very expensive in terms of stack space. Each time a function or method is called, your application must allocate a fixed amount of space for it on the stack. This means that, for any but the most basic, smallest areas, a recursive solution is likely to overflow the stack and crash your application.
Let's consider the sample application for a moment. (Download instructions are on page 4.) I determined, by viewing the compiled machine code for a sample application built for Mac OS X, that the sample's recursive fill routine requires 192 bytes on the stack per call. The stack in a REALbasic application is only 256K. That means that the recursion can go less than 1400 levels deep before the stack overflows. In my testing, the recursion in the sample application will go more than 22,000 levels deep before finishing, requiring a whopping 4 MB of stack space!
...End of Excerpt. Please purchase the magazine to read the full article.