0
Explain Flood Fill Algorithm for 4 connected and 8 connected. What are its advantages over boundary Fill algorithm

Mumbai University > Information Technology > Sem 5 > Computer graphics and vitual reality

Marks: 10M

Year: May 2016

flood fill algorithm • 21k  views
0
0
  • Polygon is an ordered list of vertices as shown in the following figure. For filling polygons with particular colors, you need to determine the pixels falling on the border of the polygon and those which fall inside the polygon. In this chapter, we will see how we can fill polygons using different techniques.

enter image description here

Flood Fill Algorithm

  • Sometimes we come across an object where we want to fill the area and its boundary with different colors. We can paint such objects with a specified interior color instead of searching for particular boundary color as in boundary filling algorithm.
  • Instead of relying on the boundary of the object, it relies on the fill color. In other words, it replaces the interior color of the object with the fill color. When no more pixels of the original interior color exist, the algorithm is completed.
  • Once again, this algorithm relies on the Four-connect or Eight-connect method of filling in the pixels. But instead of looking for the boundary color, it is looking for all adjacent pixels that are a part of the interior.

enter image description here

Boundary Fill Algorithm

  • The boundary fill algorithm works as its name. This algorithm picks a point inside an object and starts to fill until it hits the boundary of the object. The color of the boundary and the color that we fill should be different for this algorithm to work.
  • In this algorithm, we assume that color of the boundary is same for the entire object. The boundary fill algorithm can be implemented by 4-connected pixels or 8-connected pixels.

4-Connected Polygon

  • In this technique 4-connected pixels are used as shown in the figure. We are putting the pixels above, below, to the right, and to the left side of the current pixels and this process will continue until we find a boundary with different color.

enter image description here

Algorithm

Step 1 − Initialize the value of seed point (seedx, seedy), fcolor and dcol.

Step 2 − Define the boundary values of the polygon.

Step 3 − Check if the current seed point is of default color, then repeat the steps 4 and 5 till the boundary pixels reached.

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 − Change the default color with the fill color at the seed point.

setPixel(seedx, seedy, fcol)

Step 5 − Recursively follow the procedure with four neighborhood points.

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

Step 6 − Exit

There is a problem with this technique. Consider the case as shown below where we tried to fill the entire region. Here, the image is filled only partially. In such cases, 4-connected pixels technique cannot be used.

enter image description here

8-Connected Polygon

  • In this technique 8-connected pixels are used as shown in the figure. We are putting pixels above, below, right and left side of the current pixels as we were doing in 4-connected technique.
  • In addition to this, we are also putting pixels in diagonals so that entire area of the current pixel is covered. This process will continue until we find a boundary with different color.

enter image description here

Algorithm

Step 1 − Initialize the value of seed point (seedx, seedy), fcolor and dcol.

Step 2 − Define the boundary values of the polygon.

Step 3 − Check if the current seed point is of default color then repeat the steps 4 and 5 till the boundary pixels reached

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 − Change the default color with the fill color at the seed point.

setPixel(seedx, seedy, fcol)

Step 5 − Recursively follow the procedure with four neighbourhood points

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

Step 6 − Exit

The 4-connected pixel technique failed to fill the area as marked in the following figure which won’t happen with the 8-connected technique.

enter image description here

Recursive method for flood fill algorithm by using 8 – connected method:

enter image description here

Advantages Flood Fill

  • Flood fill colors an entire area in an enclosed figure through interconnected pixels using a single color.
  • It is an easy way to fill color in the graphics. One just takes the shape and starts flood fill.
  • The algorithm works in a manner so as to give all the pixels inside the boundary the same color leaving the boundary and the pixels outside. Flood Fill is also sometimes referred to as Seed Fill as you plant a seed and more and more seeds are planted by the algorithm.
  • Each seed takes the responsibility of giving the same color to the pixel at which it is positioned. There are many variations of Flood Fill algorithm that are used depending upon requirements.

Boundary Fill

  • Boundary Fill is another algorithm used for the purpose of coloring figures in computer graphics.
  • It is so similar to Flood Fill that many are confused as to whether it is another variation of it. Here area gets colored with pixels of a chosen color as boundary this giving the technique its name.
  • One can see the difference in the conditions that are there for planting the seeds. Boundary fill fills the chosen area with a color until the given colored boundary is found.
  • This algorithm is also recursive in nature as the function returns when the pixel to be colored is the boundary color or is already the fill color.
0

copy paste...!!! from https://www.tutorialspoint.com/computer_graphics/polygon_filling_algorithm.htm

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more