You are to write a C++ program to implement an algorithm for flood-filling a region of a surface. The purpose of flood-fill is to fill an arbitrary bounded space on the screen with a given color (which, for us, will be black).
To run a flood-fill algorithm, you need a grid of pixels (simply dots on a screen) each of which is either on or off, and a location within the grid, from which to flood-fill. The pixel at the start position should be off. The flood-fill algorithm sets the start position on, and all of its horizontal and vertical neighbors that are off, and all of their horizontal and vertical neighbors that are off, etc. This 'flooding' stops when a pixel that is already on is reached. You can think of the pixels that are initially on as walls, and of the start location as a hose pumping out water. The water fills as much area as it can, but it is stopped by the walls.
As an example, suppose that we were to flood-fill Figure 1 below on the left, starting from the pixel marked with a diamond. The result is shown in Figure 2. Notice that the flooding does not proceed diagonally; only the horizontal and vertical neighbors of a flooded cell that are not already on will be flooded:
As stated above, this assignment is intended to give you experience using recursion. Therefore, your program may not use any of C++'s iteration constructs (do, while, for and goto); all repetition must be accomplished using recursion. This applies to every repetitive operation in the program, even those which involve I/O.
umbc8[22]% hw3
What is the name of the input PBM file? example.pbm
This screen is 5 pixels wide by 4 pixels high.
Do you want to see the input [n]: y
Please enter characters for '1' and '0': * -
****-
*--*
**--*
*****
Please enter the x and y coordinates of the start pixel: a 5
@@@@+
@@@@@
@@@@@
@@@@@
umbc8[23]% cat outexample.pbm
P1
5 4
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
umbc8[23]%
P1';
this serves to identify the file as a PBM file (For those of you interested, the 2 character
pair at the start of a file is known in unix as the file's magic number).
The second item in the file is a pair of integers that indicate the size of the screen: first
the width, then the height (i.e., first the number of pixels in each row, then the
number of rows). The remaining lines of the file contain one digit for each pixel in the image.
A '1' means that the pixel is on, while a '0' means that the pixel is off. Here
is the sample file used above in PBM format:
P1
5 4
1 1 1 1 0
1 00 0 1
11 00 11 111 1
Note that neither the rows nor the bits in those rows are required to be separated by
whitespace. In particular, a newline is not required after each row (of the image).
Complete details about the PBM format may be obtained by reading the man page ('man pbm').
Two other points should be made about the PBM format. First, characters from a # to the end of the line are supposed to be ignored in a PBM file; however, we will not allow such comments in our PBM files. Second, no line is supposed to be over 70 characters long. We will ignore this requirement; however, if you decide you want to use the output of your program as the input to other programs that manipulate PBM files, you might want to observe it.
Another tool you might find useful is the 'bitmap' program. Bitmap allows you to draw a picture on a bitmap screen and flood-fill it. You can use bitmap to experiment with flood-filling, to verify that your program produces correct results, and to create new bitmaps for use as input to your program. Unfortunately, bitmap does not save its results in PBM format. It uses instead an alternative format called XBM. You can convert a PBM file into an XBMfile using the 'pbmtoxbm' program:
class PBM {
private:
int _rows; // number of rows in the image
int _cols; // number of columns in the image
int ** _bits; // the pixel settings for the image
// (will become 2 dimensional array)
public:
PBM (); // default constructor
PBM (int rows, int columns); // alternate constructor
~PBM (); // destructor
PBM (const PBM &); // copy constructor
PBM& operator= (const PBM &); // overloaded assignment operator
// Get status of an individual pixel
// Parameters: row and column position of the pixel
// Returns: 1 for on, 0 for off, -1 for outside of grid
int GetPixelStatus (int row, int column);
// Floodfill a region from specified starting position
// Parameters: row and column position of the start pixel
void FloodFill(int row, int column);
// Read PBM from a file
// Parameter: reference to file input stream
// Returns: true for success, false if the file is not
// in valid PBM format
int Load (ifstream& istr);
// Write PBM to a file
// Parameter: reference to file output stream
void Save (ofstream& ostr);
};
You may add other functions and data members to the class as needed.
Your source files should be named PBM.H, PBM.C,
and Proj3.C (contains main()). You may create
additional source files as needed.
You must also write and submit a makefile that runs with the
single command make.
Make sure that you adhere to the I/O specifications given in this handout (i.e., the order of inputs to your program) The precise wording of the program's prompts to the user is unimportant. If you do not adhere to these specifications, the automatic portions of the grading process will fail, and you will receive a poor grade.
cerr.
cout.
cout.