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

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

CS 261 Homework 4 - Shape Decomposer

Due Fri Oct 17 at 11:59pm

Overview

For this assignment, you will develop a system for viewing shape decompositions. The basic idea is that a shape (like a polygon) can be represented as a sequence of coordinates ("points") 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 (from L to P), 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 user is also able to restore removed points to the polygon (the slider goes in both directions). 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 developing a complete program from scratch
• 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 more practice with GUIs, graphics, and file IO

Necessary Files

You will want a copy of the cs261-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.
• Note that the points are such that the shape fits nicely in an 800x800 window.

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.

There are two pieces to this assignment: the DecomposableShape and the GUI to display it. You will probably want to work on these parts simultaneously so that you can test your program as you write it.

• 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 from lecture for illustrative examples.
  • PointNodes should be able to calculate their own importance---a value that you will also likely want to store as an instance variable of this class (to avoid doing more math later). See the above overview 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)
• Your DecomposableShape must support the following public interface:
  • public DecomposableShape()

    The constructor for the class. Instantiating a new DecomposableShape should prompt the user to select a file to build the Shape out of.

    • 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.
      • I recommend making a separate helper method to do the file parsing; keep your code tidy!
    • 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):
    • Helpful hint: Normally with double-linked lists we include both a head and a tail variable. But because this is a circular double-linked list, the tail is always just the Node immediately before the head (head.prev). Thus your code will be simpler if you avoid tracking the tail separately!
  • public int size()

    Returns the current number of points in the shape.

    • You'll probably want to also keep track of shape's "full size"---or how many nodes it has when nothing has been removed--in addition to the current size of the linked list.
  • public Polygon getPolygon()

    This method returns a Polygon representation of the current shape. This should be used to easily draw the shape.

    • See the above-linked Java documentation for details about creating a new Polygon object. You can make a new Polygon each time this method is called (you don't need to store it as an instance variable).
    • Note that once you have this method and your file parsing, you should get the GUI together and make sure your program displays correctly!
  • public void removePoint()

    This method removes the least important point from the shape.

    • 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!
    • I recommend "pre-computing" the importance of each node (e.g., in the constructor), and then simply searching on that attribute. You could even have Nodes implement Comparable!
    • You will need to recalculate the importance of a Node's neighbors after you remove it (since their distances have now changed).
    • Don't forget to adjust the size of your linked list when you remove somebody!
    • Important Style Tip: You should not use an int index when considering your DecomposableShape's linked list. 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 values in a particular order, so we could talk about the nth point. With the DecomposableShape, we don't care about which node is 3rd or 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, not for 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 to get to the ith node.
    • Make sure your program doesn't crash if you try and remove a point from an empty shape!
  • public void restorePoint()

    This method will restore the most recently removed point.

    • You will need to keep track of points that have been previously removed from the shape in order to restore them later. In order to do this, you will be using a stack. Each time you remove a node (in the previous method), you will push it onto the stack. Each time you want to restore a node, you can pop that node 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 very straightforward. 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)
    • Your removed points should remember their neighbors, making it trivial to add them back in the place where they were previously removed (because we're using a stack, we are assured that the neighbors will be in the list. Why is this the case?).
    • Don't forget to adjust the size of your linked list when you add somebody back in!
  • public void setSizeTo(double percentage)

    This method will adjust the size of the shape so that it includes the given percentage (a number between 0 and 1) of points. This may involve removing or restoring nodes.

    • You can calculate the target size (number of nodes) of your shape using the "full size" variable that you should have saved
    • Note that this method should be called by the slider (see below).
  • You are welcome to include additional methods as needed. For example, 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 buttons and slider. This DecomposerFrame will look very similar to previous GUIs: 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.

• Your GUI should save a reference to a single DecomposableShape object as an instance variable.
• You will need to do some layout work to get the components organized. A BorderLayout will work well here!
• Painting the shape should be very straightforward: just fetch the Polygon object from the DecomposableShape, and draw it using the Graphics2D draw(Shape) method (why can we do this?). 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.
• You should also create two JButtons: one for removing points and one for restoring points. Clicking each button should call the appropriate method on your DecomposableShape object.
  • Remember to call repaint() on your panel to refresh its display!
• The most complicated part of the GUI is adding in a slider to control the DecomposableShape. This should be a JSlider object--a GUI component you may not have seen before. Check out 'How to use Sliders' for a tutorial and examples. You will need to look at the JavaDoc for this class in order to determine how to use it!
  • JSliders are fairly straightforward: you instantiate the object with some parameters (e.g., make it range from 5 to 100, representing the percentages of possible indicies to choose from--5% to 100%). You then call a number of helper methods on it to specify its behavior. For example:
    • setOrientation(SwingConstants.VERTICAL) can be used to make the slider vertically aligned.
    • setPaintTicks(true) will cause the slider to show "tick" marks
    • setMajorTickSpacing(num) will specify how far apart each "tick" mark is
    • setPaintLabels(true) will cause the slider to show labels (numbers) next to each tick mark.
    • setSnapToTicks(true) will cause the slider to "snap" to the tick marks.
• A JSlider uses a ChangeListener in order to have the program react to the slider being moved. This is a Listener (just like an ActionListener or MouseListener) that you will need to implement. Remember to addChangeListener() to the JSlider object!
  • IMPORTANT: When a ChangeEvent occurs, you should make sure that the slider isn't currently being dragged, as this can cause errors in trying to add and remove points in the wrong order! You should use the getValueIsAdjusting() method to determine whether the slider is currently being moved--if it isn't, then you can adjust the size.
  • You can get the value that the slider currently shows using the getValue() method. Convert this value into a percentage (e.g., divide by 100), and then pass it to you DecomposableShape's setSizeTo() method to have it resize the shape!
  Be sure and call repaint() after you adjust the shape!

You can put your main method in the GUI frame class (just have it instantiate the Frame), or create a separate "tester" class.

Completing the Program

This is a sizable program (you can think of it as a "midterm project"), but most parts are something that you have done before: file IO with the Scanner, JFrames, drawing panels, linked lists, etc. There are a few new pieces (circular linked lists, JSliders), but you need to be comfortable looking at 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--use your buttons to do this! 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 homework zip file, and upload it along with your code!

Plan of Attack and Timeline

You 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, along with some deadlines to keep you on track:

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 vhedwig, following the instructions detailed in Lab A. 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 midnight on Fri Oct 17.

Grading

This assignment will be graded out of 37 points:

• Functionality (28pt)
• [3pt] Your program reads in a list of points from a file to construct a shape
• [1pt] Your program prompts the user for a file to decompose using a JFileChooser()
• [3pt] Your DecomposableShape uses a circular double-linked list to represent its points
• [1pt] Your DecomposableShape has a working size() method
• [2pt] Your DecomposableShape has a working getPolygon() method
• [1pt] You properly calculate the importance of nodes
• [3pt] Your program can remove the least important node of the shape
• [1pt] Successive removed points continue to be in order of least importance
• [1pt] You use a Stack to remember previously removed points
• [2pt] You are able to restore previous removed points
• [1pt] Your program doesn't crash if you try to remove or restore unavailable points
• [1pt] Your shape is drawn on the GUI as a polygon
• [2pt] You can remove and restore points using the buttons
• [2pt] Your GUI includes a properly formatted slider
• [1pt] Your slider doesn't remove points until it is done being dragged
• [3pt] Your slider adjusts the shape to the specified size
• Style (5pt)
• [1pt] You have used appropriate and descriptive variable names, including good use of CONSTANTS
• [2pt] You use appropriate encapsulation and helper methods in your classes
• [1pt] Your methods show proper algorithmic efficiency (e.g., don't iterate when you don't have to)
• [1pt] You use private helper methods to break up your code when appropriate
• Documentation (4pt)
• [1pt] All methods include JavaDoc comments with appropriate JavaDoc tags (@param and @return).
• [2pt] You have included sufficient inline comments explaining your code.
• [1pt] The README is completed

---

Joel Ross • jross@pugetsound.edu

Adapted from Koffman and Wolfgang 2010; Chapter 2 problem 7

Page Last Modified: 2014-10-07 10:15:31 -0700

Mathematics and Computer Science Department • University of Puget Sound