CODEWITHSUNDEEP
javaalgorithm
giulio
giulio

Reputation: 659

Implementation of a paintFill function

I have a couple of questions about the code below from McDowell to implement a paintFill function (similar to image editing programs).

1- Why do we use the ordering screen[y][x] instead of screen[x][y]? The author says this is characteristic of graphical problems, but why?

2- The author compares this approach to a depth first approach and says it could overflow the stack very quickly. An alternative would be to implement a variant of breadth first search. Isn't it already a bfs approach? Since for each pixel we color the neighboring pixels first before looking outward of them? If not, what would be the idea of the bfs approach and why wouldn't it overflow as well?

  enum Color{
    Black, White, Red, Yellow, Green
  }

  boolean paintFill(Color[][] screen, int x, int y, Color ocolor, Color ncolor){
    if (x < 0 || x >= screen[0].length||
            y < 0 || y >= screen.length){
      return false;
    }

    if (screen[y][x] == ocolor){
      screen[y][x] = ncolor;
      paintFill(screen, x-1, y, ocolor, ncolor);
      paintFill(screen, x+1, y, ocolor, ncolor);
      paintFill(screen, x, y-1, ocolor, ncolor);
      paintFill(screen, x, y+1, ocolor, ncolor);
    }
    return true;
  }

  boolean paintFill(Color[][] screen, int x, int y, Color ncolor){
    if (screen[y][x] == ncolor){
      return false;
    }
    return paintFill(screen, x, y, screen[y][x], ncolor);
  }

Upvotes: 0

Views: 566

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109547

  1. Image formats and screen devices use horizontal scan lines, so a vertical array of horizontal lines. So [y][x]. See analog TV signal, BMP format.

  2. A visualization of DFS would be thunder strikes, whereas BFS would be growing bacteria colony in a Petri dish. As any search is not directed, DFS has many partial candidate paths which curl in any direction and are hence longer. BFS is more natural. The same as if you would maintain the outer contour with which to grow. In another view: BFS grows restricted by an outer border, whereas DFS starts with wildly unrestricted curly paths. These paths are longer, possibly exponentionally more inefficient. The max path length B*W would be the recursion depth. In C one could have defined a small stack, but stack overflow seems a bit overdone.

Upvotes: 2

IVlad
IVlad

Reputation: 43477

1- Why do we use the ordering screen[y][x] instead of screen[x][y]? The author says this is characteristic of graphical problems, but why?

I am guessing y represents the position on the vertical axis. In that case, you cannot use screen[x][y], as the first dimension is the one relevant to the vertical axis. Therefore, it must be indexed with y.

2- The author compares this approach to a depth first approach and says it could overflow the stack very quickly. An alternative would be to implement a variant of breadth first search. Isn't it already a bfs approach? Since for each pixel we color the neighboring pixels first before looking outward of them? If not, what would be the idea of the bfs approach and why wouldn't it overflow as well?

It's not BFS because your calls are recursive depth first calls. This means that you don't color all neighboring pixels, you color one (the left one in your case) through a recursive call:

paintFill(screen, x-1, y, ocolor, ncolor);

And then you color this one's left neighbor (due to the same kind of recursive call), then that one's left neighbor and so on until you reach a pixel at the edge of the screen with no left neighbor. Then you backtrack to the last pixel you colored, and do the second recursive call from there:

paintFill(screen, x+1, y, ocolor, ncolor);

Coloring the right neighbor (which has probably been colored already since you came from the right, so this will return fast in this case). This goes on until everything has been colored.

As you can see, it is depth first, because you move in a certain direction until you can no longer move in that direction for some reason. For breadth first, you'd have to use a FIFO queue: insert one pixel position in the queue and color it. Then repeat while there are elements in the queue: remove the first element from the queue, color its neighbors and insert their neighbors in the queue.

This will avoid recursive calls and will have an effect similar to what happens if you drop a can of paint on the floor: color will expand from a single point uniformly outwards.

Depth first will look similar to what happens if you try to color a piece of paper under the restriction that you should only change the direction your hand moves when not doing so would cause you to break the paper's bounds. The current algorithm is DFS.

Upvotes: 1

Related Questions