Android polygon region recursive seed filling algorithm example code

Planar region filling algorithm is a very important algorithm in the field of computer graphics. Region filling gives the boundary of a region (or no boundary, but only the specified color). It is required to modify all pixel units within the boundary to the specified color (or pattern filling). Polygon filling is the most commonly used in region filling. In this paper, we discuss several polygon region filling algorithms.

1、 Seed filling algorithm

If the region to be filled is given in the form of image metadata, seed filling algorithm is usually used for region filling. Seed filling algorithm needs to give the region of image data and a point in the region. This algorithm is more suitable for image filling operation in human-computer interaction, and is not suitable for computer automatic processing and color filling judgment. According to the definition of image region boundary and the color modification of points, seed filling can be divided into several categories, such as flood fill algorithm, boundary fill algorithm and scan line seed filling algorithm improved to reduce the number of recursion and stacking, etc.

The core of all seed filling algorithms is actually a recursive algorithm, which starts from the specified seed point, searches in all directions, and processes it pixel by pixel until it meets the boundary. Various seed filling algorithms are only different in the way of processing color and boundary. Before introducing the seed filling algorithm, we first introduce two concepts, namely "4-unicom algorithm" and "8-unicom algorithm". Since search involves the direction of search, starting from any point in the region, if any pixel in the region is reached only by searching in the up, down, left and right directions, the region filled with this method is called four connected domain, and this filling method is called "4-connected algorithm". If you start from any point in the region and reach any pixel in the region through all eight directions: up, down, left, right, top left, bottom left, top right and bottom right, the region filled by this method is called eight connected domain, and this filling method is called "8-connected algorithm". As shown in Figure 1 (a), assuming that the blue point in the center is the point currently processed, if it is "4-unicom algorithm", only four points with blue marks around it will be searched and processed. If it is "8-unicom algorithm", four points with red marks will be searched and processed in addition to the four points with blue marks above, below, left and right. The filling effects of the two search algorithms are shown in Figure 1 (b) and figure 1 (c) respectively. If the filling starts from the yellow dot, the "4-unicom algorithm" only searches the area filling the lower left corner as shown in Figure 1 (b), while the "8-unicom algorithm" fills the areas filling the lower left corner and the upper right corner as shown in Figure 1 (c).

Figure (1) "4-unicom" and "8-unicom" filling effect

Just because of the filling effect in Figure 1, it is not considered that the "8-unicom algorithm" must be better than the "4-unicom algorithm". The Unicom search method should be selected according to the application environment and actual needs. In many cases, only the "4-unicom algorithm" can get the correct results.

1.1 flood fill algorithm

The injection filling algorithm does not particularly emphasize the boundary of the region. It just starts from the specified position and replaces all points of a specified color in the connected region with another color, so as to achieve the filling effect. Injection filling algorithm can realize functions such as color replacement, which has been widely used in image processing software. The implementation of the injection filling algorithm is very simple. The core is recursion and search. The following is an implementation of the injection filling algorithm:

The for loop realizes the recursive search to 8 Unicom directions, and the secret is in the direction_ 8 definition of:

This is a common skill in search algorithms. There is no need to explain it too much. In fact, just replace it with the following direction_ 4, the algorithm can be changed into four Unicom direction filling algorithms:

Figure 2 shows the filling effect of "4-unicom" and "8-unicom" realized by using this algorithm:

Fig. (2) implementation of injection filling algorithm

1.2 boundary fill algorithm

The essence of boundary filling algorithm and injection filling algorithm is the same. They are both recursion and search. The only difference is the confirmation of boundary, that is, the end conditions of recursion are different. The injection filling algorithm does not have the concept of boundary, but only replaces the specified color in the connected area, and the boundary filling algorithm just emphasizes the existence of the boundary. As long as the points in the boundary, no matter what color, are replaced with the specified color. The boundary filling algorithm is also widely used. The "paint bucket" function in the drawing software is an example of the boundary filling algorithm. The following is an implementation of the boundary filling algorithm:

About direction_ Please refer to the previous section for the description of 8. Figure 3 is the filling effect of "4-unicom" and "8-unicom" implemented by this algorithm (the point with color value of 1 is the specified boundary):

Figure (3) implementation of boundary filling algorithm

The above is the whole content of this article. I hope the content of this article has a certain reference value for your study or work. If you have any questions, you can leave a message. Thank you for your support for programming tips.