Article Preview
Buy Now
| Print: | |
| PDF: |
Feature
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): 7,112
Starting Page Number: 34
RBD Number: 2516
Resource File(s):
2516.sit Updated: Friday, May 14, 2004 at 10:00 AM
Related Web Link(s):
http://www.strout.net/info/coding/rb/intro.html
Known Limitations: None
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.
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
