How does fill work in paint apps?

Question

All drawing programs, regardless of how simple or complex they are, come with a fill tool. This basically replaces the color of the closed area with another color. I know there are different APIs for this, but I'm interested in the algorithm. What will be an effective algorithm for implementing this tool?

A few things I can think about quickly:

• Convert the image to a binary map, where the pixels in the color to be replaced are 1 , and all other colors are 0 .
• Find the enclosed area around the point you want to change so that all the pixels inside are equal to 1, and all neighboring pixels are equal to 0.

Image example

Answer 1

Many implementations run as a recursive conquest and division algorithm. If you quickly use Google for the “fill fill algorithm”, you will find many resources, including an excellent theme wikipedia page.

Answer 2

The most commonly used Flood Fill algorithm. Below is a naive version of it from my old university textbook, Computer Graphics with OpenGL, Hearn Baker, 3rd ed .:

 void floodFill4 (int x, int y, int fillColor, int interiorColor) { int color; /* Set current color to fillColor, then perform the following operations */ getPixel(x, y, color); if (color == interiorColor) { setPixel(x,y); // Set color of pixel to fillColor. floodFill4(x + 1, y, fillColor, interiorColor); floodFill4(x - 1, y, fillColor, interiorColor); floodFill4(x, y + 1, fillColor, interiorColor); floodFill4(x, y - 1, fillColor, interiorColor); } } 

However, for large images, the above will probably give you an error due to recursion for each pixel. Often this algorithm is modified so that it uses iteration to fill in a row of pixels, and then recursively fills the rows above and below. As @kasperjj said, Wikipedia has a good article on this.

Answer 3

These types of algorithms are discussed in detail in Computer Graphics: Principles and Practice . I highly recommend this book if you are interested in understanding how to rasterize lines, fill polygons, write 3d code without using DirectX or OpenGL APIs. Of course, for real-world applications, you probably want to use existing libraries, but if you are interested in how these libraries work, this is an awesome read.

Answer 4

If you need a time-efficient algorithm that doesn't really care about memory efficiency, you can do this:

1) saving boolean memory about which cells you have already visited: Vis[]

2) saving the list of points that you have already visited, but have not yet marked the neighbors for: Busy[]

3) run both of them as empty

4) add a starting point to Busy

5)

 while you have a point P in Busy: { for each neighbour N of the point P for which Vis[N] is still false { if appropriate (not crossing the boundary of the fill region) { set Vis[N] to true update the colour of N in the bitmap add N to the end of Busy[] } remove P from Busy[] } } 

Answer 5

Also read about labeling related components. This is an effective way to find connected pixels only by visiting each pixel twice.

Wikipedia article.

The advantage of this is that the pixel values ​​do not have to be the same or the function that describes the pixels as connected may be something other than an raw value gradient.

Answer 6

The general idea is described as a Flood Fill Algorithm and there are various modifications. General is scanning. See a related question. How do 2d scan-based rendering mechanisms work?