CS 261: Computer Science II • Spring 2014 • University of Puget Sound

Quick Links: Home • Calendar • Labs • Homeworks • Resources

CS 261 Homework 4 - Shape Decomposer

Due Mon Mar 03 at 9:00am

Overview

For this assignment, you will write a system for viewing shape decompositions. The basic idea is that a shape (like a polygon) can be represented as a sequence of coordinates in Euclidean space--connecting these points in order produces the outline of the shape. If we start algorithmically removing points from this outline, we start "decomposing" the shape and producing a more abstract polygon. For example:

The above images show the original picture on the left, and then the picture with 90% of its "least important" points removed. Importance here is determined using the following simple algorithm (described in more detail in the Koffman text, page 146):

Given a point P and its neighbors L and R, compute the distances LP, PR, and LR. Importance is measured as LP + PR - LR

Your task is to write a program that loads a sequence of points from a file, displays those points as a polygon on the screen, and allows the user to remove unimportant points in order to deform the polygon using a slider. Furthermore, the slider goes in both directions, enabling the user to also restore removed points to the polygon. You will be writing this system from scratch, though I will give you some guidance below.

This assignment should be completed individually. You are welcome to ask for help from me, or from your classmates (but remember to follow the Gilligan's Island rule)!

Objectives

• To practice with linked lists (specifically: circular double-linked lists) and stacks
• To practice using a mix of data structures in a single program
• To practice learning and working with built-in Java classes based on the official API (you should be able to figure out a class from the docs!)
• To get in a little more practice with GUIs, graphics, and file IO

Necessary Files

You will want a copy of the Hwk4.zip file which contains a number of "shape files" (text files with lists of points) that you can use in writing your program.

• Important hint: the box.txt file is an excellent way to test that things are working. You can do the math to calculate point importance by hand, in order to confirm that (a) your program is measuring importance correctly, and (b) that it is removing points in the correct order.

The zip file also contains the README.txt for this assignment--be sure and answer the questions thoroughly for full credit!

You may also want to have old code on hand to provide you with examples and a starting point. In particular, you will likely draw from your BabyName assignment (the NameDatabase class for file IO, and the NameFrame/NameGraph classes for drawing), the Bead lab (for making a linked list), and the linked-list example from class (which can be found on Moodle).

Assignment Details

Read through all of these instructions carefully before you begin! They detail the specifics of what you will need to implement to complete this assignment.

This is a large project, but think about how you can break this into small, achievable steps. If you get stuck, there is a spoiler plan of attack at the bottom.

DecomposableShape

• The most significant class in your program will represent the DecomposableShape. This class will organize the shape as a linked list (not using a linked list, the class will be a linked list). In fact, your DecomposableShape should be a circular, double-linked list. It is circular because the outline is connected (so we can consider the line between the first point and the last), and a double-linked list will let us easily talk about the points both before and after (the L and R in the above description) a given point.
  • Do you think this class should be generic? Are we going to be keeping a list of a specific type or do we need to handle a general type?
• In order to make your DecomposableShape work as a double-linked list, you'll need some kind of "node" class, like a PointNode class. This should probably be a private static inner class of the DecomposableShape class, so that you can access its fields (e.g., prev, next, point) directly. Look at your Bead class and our Node class for illustrative examples.
  • PointNodes should be able to calculate their own importance---a value that you will also likely want to store as an attribute (to avoid doing more math later). See the overall description for details on how to calculate the importance of a point.
  • HINT: A helper method to compute the distance between two points will make your code more pleasant. You can calculate distance using the distance formula: dist = sqrt((x2-x1)2+(y2-y1)2)
• Extra hint! You'll probably want to keep track of shape's "fullsize"---or how many nodes it has when nothing has been removed--in addition to the current size of the linked list.
• Important note: I highly recommend you do not use an int index when considering your DecomposableShape's linked lied. Although we use indices when talking about the generic linked list, this is because we wanted to consider them as a list--a set of valeus in a particular order, so we could talk about the nth point. With the DecomposableShape, we don't care about which node is 3rd of 5th or 120th. All we really care about is finding the particular node that we want to remove. So track your head, and then use traverals (with while loops) to go searching for the node you're interested in. Use a pointer to keep track of your current position, not some index!
  • This will let your code be cleaner and more efficient--you won't have to spend as much time doing traversals
• In addition to the regular parts of the double-linked list that will organize the points, you'll need to keep track of points that have been previously removed from the shape in order to restore them if the slider is moved up. In order to do this, you will be using a stack. Each time you remove a node, you will push it onto the stack. Each time you want to restore a node, you can pop it off the stack. This ordering will mean that the neighbors of the node you are restoring will always be in the graph, making restoring nodes incredibly easy. Note that you are welcome and encouraged to use the built-in java.util.Stack class for this purpose. (e.g., make a Stack that is an instance variable of your DecomposableShape)
• In order to construct your double-linked list, you will need to read in the points from a file. This is a pretty simple file parsing process; think about how you can adapt the code from the NameDatabase class to work with these points, instead of with name data. Your final submission must use a JFileChooser to choose which file to load, but I recommend that for testing you just hard-code in the name of the file you want to run (e.g., use that to construct a File object as a parameter to the Scanner, rather than using chooser.getSelectedFile()). This will make your life much more pleasant. Remember, in order to make these text files available in Eclipse, you will need to import them; put them inside your Java project, but not in the src folder (see screenshot below):
• Be sure to initialize your linked-list properly: make sure you set the size variable, that your head and tail are pointed at the right nodes, and that your head and tail are linked to make the list circular!
• The most complicated method of your DecomposableShape (and it isn't that complex) other than the linked-list handling will be the trim functionality. This is the method that will remove points until your shape reaches a target size. Adapting from the book, your algorithm for this should look something like:

  while the number of points is greater than n
      find the least important point
      remove that point (and push it onto the stack of removed points)
      recalculate the importance of the neighbors

  You will of course need to have computed the initial importance of all the points, likely in your constructor when you initialize the list.
  • Finding the least important node should be a basic 'king-of-the-hill' linear search algorithm. Just keep a pointer to the current "king", and use that to compare!
  • Don't forget to adjust the size of your linked list when you remove somebody!
• Along with your trim method, you'll need a restore functionality. This will let you add points that you previously removed back into the list. Because each trimmed point should remember its neigbors, it will be trivial to add it back in where it was removed (because we're using a stack, we are assured that the neighbors will be in the list. Why is this the case?). Just remember to do one point at a time, a manner somewhat the reverse of your trim method.
  • The stack makes this method incredibly simple. It took me around half a dozen lines of code. Just remember that once you add a point back in, you'll need to recalculate the importance of the neighbors.
  • Don't forget to adjust the size of your linked list when you add somebody!
• To make life easier, you'll probably want a kind of setSizeTo(target) method that will call either trim or restore in order to change the shape pointcount to match the given parameter. Then your slider can just call this method, passing in the target size.
• The easiest way to draw this shape on the screen will be to convert it into a Polygon object, which can then be directly drawn onto a Graphics2D context using the draw(Shape) method (why can we do this?). Thus your DecomposableShape may want a toPolygon() method that returns a Polygon representation of the points, so you can have your ShapePanel ask the DecomposableShape what it looks like. See the Java documentation for details about creating a Polygon object.
• Finally, you'll likely want some print or toString() methods to help with printing and debugging your list. These are not required method, but they will make programming more delightful.

The GUI Interface

You will also need a GUI window to display your shape and the control slider. This DecomposerFrame will look very similar to the NecklaceFrame: it will extend a simple JFrame and draw a ShapePanel that will extend JPanel and that can be drawn on by overriding the paintComponent() method. Note that you can make the ShapePanel an inner class, as in the NecklaceFrame from the Bead lab.

• Painting the shape should be very straightforward: just fetch the Polygon object from the DecomposableShape, and draw it using the Graphics2D draw() method. Remember to cast the Graphics parameter into a Graphics2D object! Hint: you can test this functionality even without the DecomposableShape simply by making a basic Polygon object and making sure it shows up! Note that the included shapes are sized to appear nicely in an 800x800 window.
• The other complex part of the Frame will be the slider that controls the DecomposableShape. This should be a JSlider object, similar to the one we used in the Card Lab.
  • You might instantiate your JSliders with parameters to give it a range from 5 to 100, (representing 5% to 100% of points shown). You can also use further methods to specify how it appears. Specifically, you may be interested in: setOrientation(), setMajorTickSpacing(), setPaintTicks(), setPaintLabels(), and setSnapToTicks(). All of these (and more methods!) are detailed in the Java documentation
  • The JSlider's ChangeEvents should cause your DecomposableShape to set its size based on the value of the JSlider (so resizing the polygon), and then call repaint() on the drawing panel.
    • When handling the ChangeEvents, You should make sure that the JSlider isn't currently being dragged. You can check this using the getValueIsAdjusting() method. That way you won't have to worry about points only getting half removed before you tell the Shape to trim again!
    • Don't forget to call repaint!
• You can make a separate Tester class (recommended!), or simply put the main() method inside the DecomposerFrame. Just be sure to indicate which class is your main class so I can run your program!

Completing the Program

This is a sizable program, but each part is something that you have done before: file IO with the Scanner, JFrames, drawing panels, JSliders, etc. While we might be using classes in new ways, you need to be comfortable looking at the Java documentation to figure out these classes.

• The trickiest part of this program is getting the double-linked list to work. Take time to think through how the methods will interact with the list: draw lots of pictures and "play computer" to figure out what is going on and what should be happening. Don't skimp the details! forgetting to do things like assign the tail or increment the list size can throw off your program in surprising ways.
• GET STARTED EARLY I am happy to answer questions, but you need to ask them early enough so that you have time to implement things! This is the kind of program you should be able to write.

Be sure and TEST your program to make sure it works!

• Start testing with the box, and make sure it removes each point in the right order (you'll need to work out what that order should be)! You may also want to print out (or inspect via the debugger) the "importance" values calculated for each point, so you can check that all the math is correct.
• Once you've gotten the box working, you can double-check that the other shapes (e.g., the deer, the terrier) work. Make sure to remove points and add them back in. Try removing all the points and adding them all back. Try removing some and adding them back. Try removing some, adding a few, removing a bit more, adding a few more back, etc. Test thoroughly.

As always, once you're finished, be sure that all your code is fully documented. This means full Javadoc comments on each method you create, and lots of comments explaining your code. Remember to explain the why of the code, not the what.

Finally, be sure to complete the README.txt that you found in the Hwk4.zip file, and upload it along with your code!

Plan of Attack and Timeline

You really should be able to figure out how to write a program of this size on your own. Try doing it by yourself, and see if you can make any progress. But if you get stuck, below is a rough ordering for how to attack the problem:

Show Plan

This assignment is much larger than the last. In fact, this is the kind of "full sized program" that we will be writing for the rest of the semester. Do not put it off. Try to make a little progress each day, and if you get stuck, ask for help early!

Extensions

• Simple extensions may be to play with the output somewhat: maybe draw the polygon in an interesting color (a Gradient?) or use a BasicStroke object to make the lines show up thicker (and easier to see).
• Make your own shape that can be decomposed; you might create something in a vector graphics program like Inkscape and then export the list of coordinates to a text document (check Google for details how to do this).
• The ideal extension to this file would be to have your program not just load a text file of points, but to parse an SVG file and extract a shape from that to deform. This task is well beyond the scope of our class, but you may find it interesting to explore, if you are excited about this kind of program.
• Shape manipulation and decomposition is a wide topic of research (particularly when you talk about 3D surfaces, in which case this is surface simplification). You might consider looking at some of that research for more project ideas!

Submitting

BEFORE YOU SUBMIT: make sure your code is fully documented and functional! If your code doesn't run, I can't give you credit! Your name should be in the class comment at the top of each class.

Submit your program to the Hwk4 submission folder on hedwig. Make sure you upload your work to the correct folder!. You should upload your entire src folder with all your classes. Be sure to complete the provided README.txt file with details about your program.

The homework is due at the start of class on Mon Mar 03. Note that we have the first exam that day; getting the homework done earlier will give you more chance to study!

Grading

This assignment will be graded on approximately the following criteria:

• Your program is able to read in a list of points from a file to construct a shape [10%]
• Your program represents the graphical shape using a circular double-linked list [20%]
• Your list can be trimmed by removing the least important nodes [20%]
• Your list can be restored to a previous size by replacing removed nodes [10%]
• Your program has a graphical window that displays the Decomposable shape, with a slider to control the decomposition [25%]
• Program demonstrates proper style, including cohesion/coupling and algorithmic efficiency [5%]
• Program is fully documented with complete Javadoc comments [5%]
• You have completed the included README.txt file [5%]

---

Joel Ross • jross@pugetsound.edu

Adapted from Koffman and Wolfgang 2010; Chapter 2 problem 7

Page Last Modified: 2014-03-07 16:46:50 -0800

Mathematics and Computer Science Department • University of Puget Sound