Implement the “paint fill” function

Problem

Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.

Solution
Again, the solution falls in the bucket of recursion, backtracking.

Method 1 - Recursion

First, let’s visualize how this method works. When we call Paint Fill (eg, “click” paint fill in the image editing application) on, say, a green pixel, we want to “bleed” outwards. Pixel by pixel, we expand outwards calling PaintFill on the surrounding pixel. When we hit a pixel that is not green, we stop. Surrounding green pixels may still be painted if they are touched by another Paint Fill operation.

Base case: the point is at the border. Do nothing.
Recursion: check the up, down, left and right point to see if we can fill in.

Java code

public static void paintFillRecur(Color\[\]\[\] screen,  
        int x, int y, Color origin, Color toBeFilled) {  
    if (screen\[x\]\[y\].equals(origin)) {  
        screen\[x\]\[y\] = toBeFilled;  
   
        if (x - 1 >= 0)  
            paintFillRecur(screen, x - 1,  
                    y, origin, toBeFilled);//left  
        if (x + 1 < screen.length)  
            paintFillRecur(screen, x + 1,  
                    y, origin, toBeFilled);//right  
        if (y - 1 >= 0)  
            paintFillRecur(screen, x,  
                    y - 1, origin, toBeFilled);//top  
        if (y + 1 < screen\[0\].length)  
            paintFillRecur(screen, x,  
                    y + 1, origin, toBeFilled);bottom  
    }  
}

**References **
http://tianrunhe.wordpress.com/2012/03/27/implement-the-paint-fill-function/

See also