The Flood-fill and boundary-fill algorithm come under the category of area filling algorithm. The crucial differing point in these algorithms is that the flood-fill first checks whether a random pixel is having the region’s original colour or not. Conversely, the boundary-fill examines for boundary pixel and it has already been filled or not.
Area or region filling is a process of colouring a specific image area or region. These areas can be described based on the pixels or geometric level.
Content: Flood-fill Algorithm Vs Boundary-fill Algorithm
|Basis for comparison||Flood-fill Algorithm||Boundary-fill algorithm|
|Basic||It can have an area containing several colours.||It defines the area with a single colour.|
|Painting process ||A random colour can be used to colour the interior portion then the old one is replaced with a new one.||Interior points are coloured by continuously searching for the boundary colour.|
|Algorithm complexity||Simple relatively||Complicated|
Definition of Flood-fill Algorithm
The flood-fill algorithm works by filling or recolouring a specific area containing different colours at the interior portion and the boundary of the image. It can be illustrated by an image having an area bordered by various distinct colour regions. To paint such regions we can replace a particular interior colour rather than discovering for a boundary colour value. This is the reason the approach is known as the flood-fill algorithm.
The algorithm starts working from a certain point (x, y) and reallots all the pixel values that are currently fixed at a given interior colour with the required filling colour. In a condition of multiple interior colours, the pixel values are realloted so as a result, all the interior points will contain the same colour.
Now, there are two methods that can be used for creating a continuous boundary by connecting pixels – 4-connected and 8-connected approach. In the 4-connected method, the pixel can have at maximum four neighbours that are positioned at the right, left, above and below the current pixel. On the contrary, in the 8-connected method, it can have eight, and the neighbouring positions are checked against the four diagonal pixels. So, any of the two methods can be used to repaint the interior points.
Definition of Boundary-fill Algorithm
Boundary-fill algorithm follows an approach where the region filling begins from a point residing inside the region and paint the interior towards the boundary. In case the boundary contains single colour the fill algorithm continues in the outward direction pixel by pixel until the boundary colour is encountered. The boundary-fill algorithm can be mainly implemented in the interactive painting packages, where the interior points are easily chosen.
The functioning of the boundary-fill starts by accepting the coordinates of an interior point (x,y), a boundary colour and fill colour as the input. Beginning from the (x,y) the process checks neighbouring locations to identify whether they are the part of the boundary colour or not. If they are not from the boundary colour, then they are painted with the fill colour, and their adjacent pixels are tested against the condition. The process ends when all the pixels up till the boundary colour for the area are checked.
Key Differences Between Flood-fill and Boundary-fill Algorithm
- The flood-fill algorithm can process images painted by more than one boundary colours. On the other hand, the boundary-fill algorithm can function only the images created by a single boundary colour.
- The colouring in flood-fill is done just by replacing every point colour with the designated colour. In contrast, the boundary fills algorithm checks for the boundary colour at the time of painting an area.
- Memory requirements in the flood-fill are higher as it does not guarantees the number of sub-fills generated. Conversely, boundary-fill requires less amount of memory comparatively.
- Boundary-fill algorithm is faster and complicated than the flood-fill algorithm.
The flood-fill and boundary-fill algorithms are used for different purposes or in different scenarios. Flood-fill works better with the object having no uniformly coloured boundaries. As against, the boundary-fill can elegantly be operated on an arbitrarily shaped region having a single boundary colour.
Leave a Reply