CS 261 Homework 3 - Shape Decomposer

Due Fri Mar 01 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.

Edit: Note this assignment should be completed individually.

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 get in a little more practice with GUIs and graphics
To work on reading Java documentation (you should be able to figure out a class from the docs!)
To practice adapting and re-using existing code when writing a program from scratch.

Necessary Files

You will want a copy of the Hwk3.zip file which contains a number of "shape files" (text files with lists of points) that you can use in writing your program, as well as the README.txt file for this assignment. Hint: the box.txt class is a simple way to check that things are working (because you can do the math for it by hand!).

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 the Movie class, the ZISFrame class, the Bead lab (especially Bead, Necklace, and NecklaceFrame), and the linked-list example from class.

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.
Details about the project are listed below. 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.
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.
- 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.
- In addition to 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.
- 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 Movie class to work with these points, instead of with movies. You can use a JOptionPane to choose which file to load, but your life will likely be more pleasant if 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()). In order to make these text files available in Eclipse, you will need to export 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.
  - 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!
- In order to work with the slider, you'll probably want a kind of setSize() method that will call either trim or restore in order to change the shape pointcount to match the target. Then your slider can just call this method, passing 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. 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.
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. See the overall description for details on how to calculate the importance of a point. HINT: A helper method to computer the distance between two points (using the distance formula) will make your code more pleasant.
You will also need a GUI window to display your shape and the control slider. This DecomposerFrame will look very similar to the NecklaceFrame and the ZISFrame: extending a simple JFrame, with an inner class (e.g., ShapePanel) that extends JPanel and can be drawn on by overriding the paintComponent() method.
- The painting 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 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 (see also 'How to use Sliders' for a tutorial and examples).
  - JSliders are fairly straightforward: you instantiate the object with some parameters (e.g., make it range from 5 to 100, representing 5% to 100% of points shown), and then use some other 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
  - 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! 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.
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!
This is a sizable program, but each part is something that you have done before: file IO with the Scanner, JFrames, drawing panels, etc. There are a few new pieces (e.g., the JSlider), but 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.
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 Hwk3.zip file, and upload it along with your code!

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!

Submit your program to the Hwk3 submission folder on hedwig, following the instructions detailed in Lab A. You should upload all you classes, as well as the README.txt.

The homework is due at the start of class on Fri Feb 29.

Plan of Attack

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

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!

Grading

This assignment will be graded based 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 [10%]
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 [15%]
Your program uses a Slider to control the decomposition of the shape [10%]
Program demonstrates proper style, including cohesion/coupling and algorithmic efficiency [10%]
Program is fully documented with complete Javadoc comments [10%]
The README is completed [5%]