MP 4 Flood Fill

Checking Out the Code

To check out the provided code for MP4 from the class repository, run

svn up

from your cs225 directory.

This will update your working directory to contain a new directory called mp4.

Part 1 (Curated): Image Traversals

As you learned in lecture, there are many ways to traverse a tree. In this MP, you will use object-oriented programming techniques to develop classes that traverse an image in a generic way.

Developing an ImageTraversal

Consider a simple image of 16 pixels:

Every ImageTraversal will start at a provided Point. In this image above, suppose we start in the bottom-left corner (0, 3). The first pixel a traversal will “visit” will almost always be that starting point (0, 3).

As part of “visiting” a point, a traversal must add all of the neighbors that will be visited at some time in the future. Every point has up to four neighbors (and the neighbors must be added in the following order):

• The pixel to the right, (x + 1),
• The pixel below, (y + 1), and
• The pixel to the left, (x - 1).
• The pixel above, (y - 1),

As our starting point (0, 3) is a corner, it has only two neighbors (1, 3) and (0, 2):

After visiting the first point (the starting point), the next point visited is determined by our ImageTraversal. The logic in add and pop determines the order the nodes are visited. For example, if we visit the point that was most recently added, we create the following traversal:

Finally, in the image above, only orange pixels were visited. A point must NOT be visited in a traversal if either of the following statements are true:

1. The point has already been visited (a traversal never visits the same point twice), OR
2. The pixel at the point is greater than or equal to a given tolerance away from the pixel at the starting point. The function ImageTraversal::calculateDelta is provided for you to calculate the difference between two pixels.

Part 1a: Create a DFS ImageTraversal

Implement the traversal described above in imageTraversal/DFS.{cpp,h}. It is not necessary to implement the begin and end functions yet.

• Feel free to use a std::vector, std::list, std::stack, or std::queue if they would be helpful.

Part 1b: Create a BFS ImageTraversal

Implement the second ImageTraversal, BFS, by visiting the first earliest point that was added that has not yet been visited. It is not necessary to implement the begin and end functions yet.

• Feel free to use a std::vector, std::list, std::stack, or std::queue if they would be helpful.

Part 1c: Create the ImageTraversal::Iterator

Finally, create an iterator that uses the ImageTraversals that you have built. You need only to create the simplest of all the iterators – a forward iterator – which requires three operations:

• operator*, to access the current Point in the image traversal
• operator++, to advance to the next Point in our image traversal
• operator!=, to check if two iterators are different

A call to DFS::begin() or BFS::begin() must return an ImageTraversal::Iterator that starts at the starting point (eg: *(dfs.begin()) == startingPoint) and must move through the traversal you created in parts 1a and 1b.

As you work through this:

• You may assume the PNG image will not change after your object is created.
• Iterators must be independent (moving one iterator forward does not change other instances of an iterator).
• There are at least four very different ways to build your iterator. You may need to create a copy of your entire BFS or DFS object within your iterator, this is okay.
• Remember that begin() returns an iterator at the starting point, but end() returns an iterator one past the end.
• It is common for end() to be a sentinel value (eg: a NULL pointer, etc). It should not be necessary to run through the full traversal to get to one past the end.

Finally, simple test cases for this part can be run with the following command:

./test [part=1]

Extra Credit Submission

For extra credit, you can submit the code you have implemented and tested for MP4, Part 1. You must submit your work before the extra credit deadline as listed at the top of this page. Follow the handin instructions given at the bottom of this page.

Part 2 (Curated): Flood Fill

In this MP, you will be flood-filling an image using a ColorPicker and an ImageTraversal. You built ImageTraversal classes in Part 1 and we have provided some ColorPicker classes for you (including RainbowColorPicker, SolidColorPicker, and others).

The FloodFilledImage class outlines the three member functions you must implement for this part.

• Feel free to use a std::vector, std::list, std::stack, or std::queue if they would be helpful.

Part 3 (Creative): Your Flood Fill!

Finally, time to be creative with what you built! Two seperate things are required:

1. Create a new color picker called MyColorPicker, found in the colorPicker folder. This picker may be anything, but must be different than the color pickers we provided.

2. Modify main.cpp to create a FloodFilledImage using at least two flood fill operations (two calls to addFloodFill). Your main.cpp must save the last frame as myFloodFill.png.

Testing

convert

To run all of the tests for this MP:

make test
./test

Handing in Your Code

To commit your changes to the repository type:

svn ci -m "mp4 submission"

Grading Information

The following files are used to grade MP 4:

• imageTraversal/BFS.cpp (Part 1)
• imageTraversal/BFS.h (Part 1)
• imageTraversal/DFS.cpp (Part 1)
• imageTraversal/DFS.h (Part 1)
• imageTraversal/ImageTraversal.cpp (Part 1)
• imageTraversal/ImageTraversal.h (Part 1)
• FloodFilledImage.cpp (Part 2)
• FloodFilledImage.h (Part 2)
• colorPicker/MyColorPicker.cpp (Part 3)
• colorPicker/MyColorPicker.h (Part 3)
• main.cpp (Part 3)
• myFloodFill.png (Part 3)

All other files will not be used for grading.

Good luck!