CS 215 - Fundamentals of Programming IISpring 2010 - Project 220 pointsOut: February 3, 2010Due: February 10, 2010Reminder: Programming Projects (as opposed to Homework problems) are to be your own work. See syllabus for definitions of acceptable assistance from others.For this project, you will develop a simplified version of an algorithm used in image processing to find objects in a scene. Problem Statement Consider a square grid, some of whose cells contain asterisks and others that contain periods. On an 8x8 grid, we might have the following two examples: **...... .**..*.. **..*..* ****.*.. ..**.**. ...**... ..**.**. .*.*..** .*..*..* .*...*.* ..**.**. .****... ..**.**. .*.**... .*..*..* .*.**...We define two cells to be contiguous if they are adjacent to each other in the same row or in the same column. Now suppose we define a blob as follows: ● A blob contains at least one asterisk ● If an asterisk is in a blob, then so is any asterisk that is contiguous to it. ● If a blob has more than two asterisks, then each asterisk in it is contiguous to at least one other asterisk in the blob. We would like a program that determines the number of blobs and the placement of these blobs in a grid. The left example above has 13 blobs and the right example has 5 blobs. We will indicate the placement of blobs by replacing the asterisks with a unique letter (starting with a and identifying them in order of the upper-leftmost asterisk in each blob) indicating which blob a cell belongs to. For the examples above, the output would be: 02/01/2010 Page 1 of 3aa...... .aa..b.. aa..b..c aaaa.b.. ..dd.ee. ...aa... ..dd.ee. .c.a..dd .f..g..h .c...e.d ..ii.jj. .cccc... ..ii.jj. .c.cc... .k..l..m .c.cc...Design Notes Here are some suggestions for how to structure this program. ● One can use an (n+2)X(n+2) array with properly marked cells. The two additional rows and columns constitute a frame of periods surrounding the entered square to simplify the implementation. For example, the examples above could be stored as: .......... .......... .**....... ..**..*... .**..*..*. .****.*... ...**.**.. ....**.... ...**.**.. ..*.*..**. ..*..*..*. ..*...*.*. ...**.**.. ..****.... ...**.**.. ..*.**.... ..*..*..*. ..*.**.... .......... ..........● The main idea is to traverse the grid row by row, and for each (unvisited) asterisk, call a function that processes the cell. The secret is to mark the cell by replacing the asterisk with the blob's identifying letter, and in using up to four recursive calls in the function for each unvisited contiguous asterisk.Assignment Write a program in a file named blobfinder.cpp that is given an input file name on the command line. This file will contain an integer on the first line that is the size of a square grid, followed by a square grid of that size of asterisks and periods as shown above. (Note this means that you should not test for end of file! You know exactly how many characters to read in.) You may assume that this grid will be no larger than 50x50, and that there will be no more than 26 blobs contained in the grid (to be marked from a up to possibly z). A few example input files are available on csserver in directory /home/hwang/cs215/project2 After reading the input grid from the input file, the program should determine the number of blobs and the placement of the blobs as indicated above. Finally, it should output the number of blobs found and the modified grid (without extra frame cells, if any) to the screen as shown below for the left example. (Note there is only one grid in each file. The examples above are displayed side-by-side to save space.)02/01/2010 Page 2 of 3There are 13 blob(s) in this file. aa...... aa..b..c ..dd.ee. ..dd.ee. .f..g..h ..ii.jj. ..ii.jj. .k..l..mThe blob processing must be done using a recursive function as indicated above. In addition, the output of the grid must be handled by a function that receives the grid to be printed. Note that this print function may be used a debugging tool by printing out the grid at various intermediate points, for example, after finding each blob. However, make sure such debugging code is removed or commented out before submitting your project. (Reminder: global variables are not allowed in the course.) Appropriate error checking of the number of command-line arguments and a successful file open is expected.You must submit a makefile named Makefile.project2 for your project that creates an executable named blobfinder. It should be a full makefile with separate targets for the compile and link phases. Submissions without complete makefiles will be assessed up to a 3-point penalty as indicated in the syllabus. It should conform to the examples given in the handout Very Basic make and demonstrated in class. REMINDER: Your project must compile for it to be graded. Submissions that do not compile will be returned for resubmission and assessed a late penalty. Submissions that do not substantially work also will be returned for resubmission and assessed a late penalty.Follow the program documentation guidelines in the C++ Programming Style Guideline handout as well as a consistent indenting and variable naming scheme. As stated in the syllabus, part of the grade on a programming project depends on how well you adhere to the guidelines. The grader will look at your code listing and grade it according to the guidelines. What to submit Electronically submit a tarfile containing Makefile.project2 and blobfinder.cpp as explained in the handout Submission Instructions for CS 215. Also hand in hard-copy printouts of these files as explained in the handout. Do not submit object files or executable files.02/01/2010 Page 3 of
View Full Document
Unlocking...