Friday, March 28, 2014

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/

0 comments:

Post a Comment