Monday, August 3, 2009

Implement color-filling of MS-Paint

This is one of the questions that I came across recently.
Question:
Implement the Color filling of MS-paint (when u click on an image.. all the pixels connected with the same color are filled with the choosen color). Given a matrix nXn having values of a color at each element.. try to implement the color filling when one of the element is selected and color c is given with which we have to fill.


Answer:
Given the starting pixel position, and the color

startX <- contains the starting row position (< M)
startY <-- contains the starting col position (< N)
image[M][N] are the pixels
oColor = image[startX][startY];
nColor <-- color value selected;

fillcolor(startX, startY);

fillcolor(x,y)
begin
if(x <>= M || y >= N)
return;
if (image[x][y] != oColor && image[x][y] != nColor)
return;

image[x][y] = nColor;
fillcolor(x-1, y);
fillcolor(x-1,y-1);
fillcolor(x, y-1);
fillcolor(x+1,y);
fillcolor(x,y+1);
fillcolor(x+1, y+1);
fillcolor(x+1, y-1);
fillcolor(x-1, y+1);
end;


Another Answer:
Let's say that the element (i,j), which was clicked, has color X, and we have to give it color Y.

Take an Empty Queue Q;
e.color = Y;
Q.Enqueue(e);

while(Q.IsNotEmpty())
{
.....element e = Q.Dequeue();
.....for all neighbours (Left,right,up,down,left-up,left-down,right-up,right-down)
..........if(neighbour.color == X)
...............neighbour.color = Y;
...............Q.Enqueue(neighour);
}


Which is Correct?

1 comment:

  1. > Which is Correct?
    Neither. Paint fill algorithms don't follow diagonals.

    ReplyDelete