Plotting Pictures in a 2D Data Structure

Alyce Brady
Kalamazoo College

 


Introduction

In this assignment you will implement methods for drawing in a two-dimensional grid by changing the colors of the cells in the grid.  This will give you practice with developing algorithms for two-dimensional data structures.

The two-dimensional data structure used in this lab is represented by a BoundedGrid object made up of rows and columns. A BoundedGrid object models a bounded rectangular grid that contains objects at various grid locations. Each cell contains zero or one objects.  In this program, cells that are not empty will contain color blocks (objects of the ColorBlock class).

  0 1 2 3 4 5 6 7 8
0
     
obj1
         
 
obj2
             
   
obj3
 
obj4
       
               
obj5
1
2
3

We refer to locations in the grid by their row and column numbers in parentheses, such as location (2, 7). Row and column numbers start at 0 rather than 1, so location (0, 0) refers to the first row and first column. Object obj1 in the grid shown above is in the first row and fourth column, or at location (0, 3). Object obj5 is at location (3, 8). (This is similar to the way Java array and ArrayList indices are numbered.)

In this assignment you will define methods for drawing in the two-dimensional grid by putting color blocks in the cells of the grid.



Getting Started

In this exercise you will be experimenting with the Grid Plotter program to see how it works.

Exercise Set 1: Becoming Familiar with the Existing Program

  1. In the GridPlotter folder you will see the following files and folders.
    • The Instructions folder contains this write-up (GridPlotter.shtml).
    • The grid.jar Java archive (jar) file contains a library of classes that can be used to model a two-dimensional grid as described above.
      • Grid and BoundedGrid (represent two-dimensional grids)
      • Location (class that represents the row and column positions of a location in the grid)
      • ColorBlock (class whose objects represent blocks of color put in a grid)
    • The GridPkgClassDocumentation folder contains the class documentation for the classes in the grid.jar library.
    • The JavaSourceFiles folder contains the source files for the Grid Plotter program in which we can draw pictures by placing (plotting) color blocks in a grid.
      • GridPlotter (the class you will be enhancing)
      • GridPlotterApp (contains the main method)
      • GridPlotterGUI (a class that implements the program's graphical user interface; you are not expected to read or understand this class)
    • You can find documentation for these files in the JavadocDocumentation folder.

    Note: All of the classes in the JavaSourceFiles folder and the grid.jar Java archive file are covered by the GNU General Public License.

  2. Compile and run the program. As the program starts up you will be asked for the dimensions (number of rows and columns) of the grid in which you will be drawing. For now you can go with the default values, since your purpose for this exercise is just to experiment with the user interface. Once you have chosen the grid dimensions, click on the "RowMajorFill" drawing button; you should see color blocks filling the locations of the grid in row-major (top-down, left-to-right) order. Experiment with the "Adjust Speed" slider while the program is drawing color blocks.

  3. Experiment with the program to discover what the "New Grid" and "ClearGrid" buttons and the "Background Color" and "Drawing Color" menus do. What does the "Help" menu do? What happens if you press the "RowMajorFill" button twice in a row?  Does the behavior appear different if you change the drawing color between "RowMajorFill" button presses?  What could explain this behavior?



Studying the Algorithms

The starting point of the Grid Plotter application is the GridPlotterApp class, which contains the main method. If you look over the class, you will see that it does remarkably little. It creates two constants that define the size of the window containing the graphical user interface, one that defines the smallest allowable grid cell size, and two more that define the extreme values for the speed adjustment slider. The class's main method creates a graphical user interface object, tells it to include a "Help" menu, and asks it to construct the window contents (this also makes the window visible on the screen).  Notice that the main method does not say anything about the "File" menu or the various buttons and pull-down menus on the graphical user interface; those are specified in the GridPlotterGUI constructor.

Exercise Set 2: Experimenting with the main Method

  1. Experiment with the constants defined at the top of the GridPlotterApp class to see how changing them affects the application.

We will not look at the GridPlotterGUI class, which includes some quite advanced features of Java. Instead, let's look at the GridPlotter class. The graphical user interface calls methods of this class whenever a user constructs a new grid, presses one of the drawing buttons, or presses the clear button.  As you read through the GridPlotter class you may wish to read the class documentation for some classes it uses from grid.jar, such as Grid, Location, ColorBlock, and ColorChoiceMenu.

Exercise Set 3: Reading and Understanding the GridPlotter Class

  1. What instance variables does a GridPlotter object have? How does it use them?

  2. What does the constructor do?

  3. What does the onRowMajorFillButtonClick method do? How do the statements in the onRowMajorFillButtonClick method ensure that the order in which the application colors cells will be row-major order? (Row-major order means stepping through a two-dimensional data structure row-by-row.  It first visits all the locations in row 0, then all the locations in row 1, and so on.  Within each row, it steps through the locations left-to-right.)

  4. What do the private ensureEmpty and placeColorBlock methods in the GridPlotter class do? How does a ColorBlock object get added to a particular location in a grid? What happens if a drawing method tries to place a color block in a location that already has a color block?
  5. Complete the implementation of the onClearGridButtonClick method, using the onRowMajorFillButtonClick method as a guide. Test your code by filling the grid and then clearing it. Make sure to test it with several different grids of different sizes, on both empty and filled grids, and using different colors.  You should not see it clear block-by-block — why not?

 



Adding New Drawing Methods

Now it's time to write some drawing methods of your own.

Exercise Set 4: Writing Your Own Methods

  1. Complete the onColMajorFillButtonClick method, using onRowMajorFillButtonClick as a guide. Test your class by running the program in several grids of various sizes and watching the traversal. Are the cells filled in left-to-right, going down each column?  (A traversal through a two-dimensional data structure is an algorithm that steps through all the elements of the data structure, visiting each element exactly once.  A traversal through a grid steps through all the locations in the grid.  Column-major order means stepping through a two-dimensional data structure column-by-column.  It first visits all the locations in column 0 top-to-bottom, then all the locations in column 1, and so on.)

  2. Write an onReverseRowMajorFillButtonClick method, using onRowMajorFillButtonClick as a guide. This algorithm should fill in cells bottom-up, going left-to-right across each row. In other words, the row order is reversed, but the column order is not. If your new method has the same number and type of parameter(s) and the same return type as the onRowMajorFillButtonClick method, and if its name follows the same on...ButtonClick pattern, then something magical will happen when you run the program —  a new button will appear as part of the graphical user interface!  (Actually, it's not magic, it's some advanced Java code in the GridPlotterGUI class.) Click on the button to test your new method.

  3. Write an onReverseColMajorFillButtonClick method, using onColMajorFillButtonClick as a guide. This algorithm should fill in cells right-to-left, going up each column from the bottom. In other words, both the row and column orders should be the reverse of onColMajorFillButtonClick. Test your new method.

  4. Write an onDiagonalButtonClick method. This algorithm does not fill the entire grid; instead, it should color cells along the diagonal from the upper-left corner towards the lower-right corner. It will actually end up in the lower-right corner only if the grid is square.  If it is not square, the algorithm steps down and to the right until it comes to the last column or the last row, depending on whether the grid is higher than it is wide or wider than it is high. The diagrams below show the behavior for a 5 x 5 grid, a 3 x 5 grid, a 5 x 3 grid, and a 1 x 1 grid.
    Before you attempt to write the code, list the locations that you want to fill. When you're done with the implementation, test your new method in various sized grids, such as the ones above.

    Hint: You do not need nested loops to implement the onDiagonalButtonClick method.

  5. Write an onTriangleButtonClick method. This algorithm should fill in all the cells on and below the diagonal you produced in the preceding exercise. (It will form a true triangle only if there are at least as many columns in the grid as there are rows.)  Before you attempt to write the code, list the locations that you want to fill. When you're done with the implementation, test your new class. The diagrams below show the behavior for a 5 x 5 grid, a 3 x 5 grid, a 5 x 3 grid, and a 1 x 1 grid.

  6. Write a second diagonal method similar to the first one, but going from the upper-right corner towards the lower-left corner.  (Again, whether it actually reaches the lower-left corner depends on whether or not the grid is square.)  Give your method an appropriate name and test it in a variety of grids.
  7. Write a method that draws an 'X' in the grid, giving it an appropriate name. Reuse existing methods as appropriate.  When you're done, test your new method. The diagrams below show the behavior for a 5 x 5 grid, a 4 x 5 grid, a 5 x 4 grid, and a 1 x 1 grid.

    Hint: The best implementation of this method consists of two statements, with no loops.

  8. Write a method that draws a border around the grid's perimeter. Before you attempt to write the code, list the locations that you want color in order to find a pattern. When you're done with the implementation, test your new method.  The diagrams below show the behavior for a 5 x 5 grid, a 2 x 5 grid, a 3 x 1 grid, and a 1 x 1 grid.

  9. Write three (or more) new methods that you could use to draw a picture.  For example, you could create a method that draws the walls of a house, a method that draws a roof, and a method that draws four windows.  A user could then use your methods to draw black walls, a red roof, and blue windows.  Your picture should draw in grids of different sizes, scaling up or down as necessary.  You may, however, specify a minimum size if you want; for example, this picture will only draw correctly in a grid that has at least 20 rows and at least 20 columns.  You may also want to specify that the grid has to be square, or that the number of columns must be twice as many as the number of rows.  Whatever your constraints are, be sure to document them in the javadoc documentation for the appropriate methods in the GridPlotter class!

  10. Provide appropriate documentation under the "Help" menu.  To do this, you will need to edit the GridPlotterApp class.  Look for the statement that constructs the "Help" menu.   Provide the appropriate information for the author(s), assistance, and date. Then create a document called GridPlotterHelp.html that contains information for users about what the program is, how it works, what it does, etc.  Be certain to provide a brief description of your new methods and how they can be used to draw a picture.  Document any assumptions that your methods make about the size and shape of the grid, as you did in the GridPlotter class. Save this file in the folder where you run the program.  Run it and test both menu items in the "Help" menu.