Solo MP

This MP, as well as all other MPs in CS 225, are to be completed without a partner.

You are welcome to get help on the MP from course staff, via open lab hours, or Piazza!

Checking Out the Code

From your CS 225 git directory, run the following on EWS:

git fetch release
git merge release/mp4 -m "Merging initial mp4 files"

If you’re on your own machine, you may need to run:

git fetch release
git merge --allow-unrelated-histories release/mp4 -m "Merging initial mp4 files"

Upon a successful merge, your MP4 files are now in your mp4 directory.

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):

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.

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.

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:

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:

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

make test
./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.

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.

You just made something awesome that never existed before -- you should share your animation!

If you share your art on Facebook, Twitter, or Instagram with #cs225, I will or the post as soon as I see it. I think many of your peers will too!

As with MP1 and MP2, I will look at every animiaton and, together with course staff, we'll award +1 extra credit to animations that stand out! I'm looking forward to seeing the awesome animations you create!   — Wade



Note that you must have ImageMagick installed if you’re developing on your personal machine. You can test for this requirement by running


in your terminal. Windows users should visit ImageMagick to download the latest binary. OSX users can use homebrew or MacPorts to install it if missing. Linux users likely already have it installed. If not, then you can install it via your system’s package manager.

To run all of the tests for this MP:

make test

MP 4: Submission

Our grading system will checkout your most recent (pre-deadline) commit for grading. Therefore, to hand in your code, all you have to do is commit it to your GitHub repository.

Be sure your working directory is the mp4 folder that was created when you checked out the code. To hand in your code, you first need to add the new files you created to the working copy of your repository by typing:

To commit your changes to the repository type:

git add -u
git commit -m "<your message>"
git push origin master
Guide: How to submit CS 225 work using git

Grading Information

The following files are used to grade MP 4:

All other files will not be used for grading.

Good luck!