| Section | Date Out | Due In |
|---|---|---|
| Mr. Baumgarten's Sections | Monday, March 15, 1999 | Friday April 9, 1999 |
| Mr. Edelman's Sections | Monday, March 15, 1999 | Sunday April 11,1999 |
There are 3 main objectives in this assignment:
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]% more 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.
There are a couple of tools that you might find useful when working on this assignment. The 'xv' program can display pictures that are stored in a variety of formats, including PBM. Because the standard X-windows manager imposes a minimum window width, very small PBM pictures will be stretched when they are displayed by xv. You can unstretch such pictures by changing the size of the xv window (for instance, by dragging the lower right-hand corner of the window with the mouse).
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 class constructor
PBM(int rows, int columns); // alternate class constructor
~PBM(); // class destructor
PBM (const PBM &); // copy constructor
PBM& operator= (const PBM &); // overload assignment operator
//returns status of an individual pixel
// 1 for on, 0 for off, -1 for outside of grid
int GetPixelStatus(int row, int column);
// floodfill a region from a specified starting position
// parameters are x, y coordinates of starting pixel
void floodfill(int, int); // floodfill a region
// extract PBM from a file
// Return Value = 1 (true) for success and 0 (false) for
// any failure to read successfully
int Load (); //reads a PBM from a file
//Write PBM to a file
// return value = 1 (true) on successful write
// and 0 (false) on any failure
int Save ( ); //writes a PBM to a file
//display image on screen
void Display();
};
You may add other functions to the class, if you wish to. If you do
so, you may not change the public interface to the PBM class
You might also wish to implement overloaded << and >> file functions to read
and write pbm files, but that is not a required part of this project.You should have 2 header files: the first header file declares the PBM class; the second one declares all of the functions used by function main.
You will also code 3 .C files: the implementation files for the headers you wrote, and also a file that contains function main and very little else.
The reason for this partitioning is to cultivate the habit of writing modular programs.
In addition to this, you must also write and submit a makefile that runs with the single command make.
You must submit all of your .C and .h files, together with your Makefile. The Makefile must correctly compile your homework upon issue of the make command with no arguments. You may name your files as you wish, but the executable created by the make command must be named Proj3. Your Makefile will be used to compile your submitted code, so be sure it works. A simple Makefile that just does the compilation is fine.
You may submit your program more than once, but only the last version you submit will be graded. Submissions made by midnight on the due date are considered on--time. Projects received after that date are late, and will be penalized.
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 questions 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.