Read this Whole Handout. And, of course, complete all the readings we ask you to do. We're not being mean. It'll help you understand and complete this program quickly, and it'll cut down on the time spent waiting in line for a TA.

Introduction

In this assignment you will be implementing a Graham Scan algorithm to find the convex hull of a set of points and update the hull as necessary as new points are added to the set. Your algorithm will be based on a CircularTree<K,V> that stores the points on the hull.

Setup

Installation

Just run the install script as always cs016_install convexhull

The Demo

To run the demo use the cs016_runDemo convexhull script

Reading

You must read the Convex Hull Help Session slides before coming to TA hours.

The following material will also be helpful in understanding various aspects of the assignment:

• Graham Scan Wikipedia Article
• Static Graham Scan Demo shows a static Graham Scan step-by-step on a set of points.
• Convex Hull Slides
• Convex Hull Supplement

Specifications

Purpose

The purpose of this assignment is to help you:
• Gain experience with basic computational geometry concepts.
• Design and implement a complex algorithm.
• Learn how much special and edge cases suck, but also how to deal with them.
• Understand the use of an auxiliary data structure.

Requirements

Incremental Graham Scan

You will write an implementation of interface support.convexhull.ConvexHull. This class will be your implementation of an incremental Graham Scan algorithm. When a point is added to the set, your algorithm will determine whether or not it belongs in the convex hull, and add it if necessary. To get full credit you must implement a Graham Scan rather than some other algorithm.

Further Specifications

• Given three collinear points, at most two of them can be on the convex hull. Note: Don't worry about coincident points (points that share the same x and y coordinate).
• The anchor point for the hull must be a point within the convex hull. We recommend that you determine the anchor point as soon as you have three points on the hull to guarantee that it is within the hull (before you have three points, just use the first point as your anchor), and that you use the midpoint of the three points as the anchor.
• Implement the calculation for determining the orientation of an angle (clockwise or counter-clockwise) in O(1) time.
• Store the set of points on the convex hull in O(n) space, where n is the number of points on the hull, not the total number of points on the screen.
• Implement an algorithm that will allow you to add a point to a convex hull in O(k log n) time, where k is the number of points removed from the hull to accommodate the new point, and n is the number of points on the hull prior to the insertion.
• Write a README as described in Section 6 of this handout.

Extra Credit: Static Graham Scan

Note that the Static Graham Scan method is extra credit, you are not required to implement it. The static Graham Scan takes in a set of points and finds the convex hull for that set all at once, rather than determining the convex hull as points are added. See a TA on hours if you have questions about this, or visit the wikipedia page for more information.

Visualization

Your class is required to implement the interface we defined exactly. You cannot change the method signature of any method in the stencil code. You can, however, add as many helper methods as you would like. Helper methods are encouraged!

As in the previous programs, the TAs will provide a visualizer for you. It is a hacked up concoction, but it has no known bugs.

The visualizer will not run until you implement the hull() method.
This method is found in the MyHull.java file that was installed using the steps outlined above. See the "Data Structures" section below for more information on visualization.

Design

Data Structures

The data structure you should be using is the CircularTree that we provide for you in the support.convexhull package. Please refrain from programming your own data structures! Everything will be simpler, easier, and quicker to code if you use what we have provided for you, and you'll be much happier in the end.

Note that, unlike in Queue and Heap, you are not designing a generic data structure for Convex Hull. Rather, you are instantiating the CircularTree class that is itself generic, so it is your responsibility to define the concrete classes the tree will use for its key K and value V.

In order for the visualizer to properly display your hull, it is required that the key be of type Angle and the value or element stored of type HullPoint.

NDS4 Javadocs are available at http://net3.datastructures.net/doc4/index.html

Orientation Test

You need to figure out how to judge if three ordered points are oriented clockwise or counterclockwise. The help session slides provide more explanation on this topic.

Given this, you need a standard for interpreting the results. You should have your orientation test return ints so that you can use the easily-readable built-in operators (<, >, ==, and so on).

The class support.convexhull.HullPoint maintains coordinate information about the point. HullPoints are created and passed into your insert method each time a point is added to the canvas of the visualizer. Your insert method must determine if these points are on the hull or not. The HullPoint class provides the coordinates that your orientation tester should be using when performing tests on points. See the definitions below.

Angles

You will be storing points in the CircularTree using the Angle between the new point and the anchor point as the Key. These Angles will keep them organized in counterclockwise order. See the help session slides for further clarification. Initially, the anchor point will be the first point you add to the Hull. This will change once you have added three points. When there are three points in the Hull (ie. not three collinear points), the new anchor point should be calculated by finding the midpoint of the three points currently in the Hull. You will then need to update the Angles of the points already in the Hull and reinsert them into the tree based on these new Keys.

To make a new Angle, you will instantiate a new instance of the Angle class, passing it the difference of the x-coordinates and the difference of the y-coordinates between the new point and the anchor point. See the help session slides for more information.

Remember that the upper left-hand corner is point (0,0). So points that are lower on the screen will have a higher y-value than the points above them, unlike the standard coordinate system the Angle class is based on (while the x-coordinates will be the same as the standard system). Think about how this will affect the computation of the Angles.

README

Answer the following questions in a text file entitled "README" in the same directory as your project; it will be handed in along with your code. (You can create a new text file by "opening" it in emacs or any other editor.) Each of the questions should be answered in about 2-4 lines, unless otherwise stated.
1. Give an overview of your design for ConvexHull.
2. Describe, briefly, any special cases which your insertion algorithm had to handle and how you chose to handle them.
3. If you have anything else noteworthy about your program you haven't mentioned yet, talk about it here (write as much or as little as you like).

Visualizer Usage

A window will show up with a column of buttons and a graphical background. Left click on the background to add points (make sure you don't move the mouse, or it won't register the click). The visualizer will connect the points with lines to draw the current convex hull. The hull will be drawn with red lines.

When a point is added, it is classified and colored as follows:

• Red - The point is outside the current convex hull and gets added to the convex hull.
• Blue - The point is inside or on the current convex hull, so nothing changes.
• Green - Error: the point is invalid. This can be caused by internal java errors (e.g. NullPointerExceptions) or by violating the requirements of this assignment. A working Convex Hull should not have any of these points.

You can also add a point by specifying its x and y coordinates in the boxes on the left side of the window. This is especially useful for checking special cases.

Right clicking anywhere on the background will display the x and y coordinates in the boxes on the right.

"Load File" is a slightly different beast. When you select "Load File," a dialog box will appear allowing you to select a file. The file consists of a pairs of x and y coordinates representing the points. For example:

100 100
100 50
234 453
74 222

This will create 4 points, with the coordinates {100,100}, {100,50}.... you get the idea. There should be only one pair of points per line, and there must be one pair of points on every line. That is, no blank lines are allowed in the file. Creating files is highly encouraged as it makes checking for special cases repeatedly very simple.

If at any time, you click on "Clear" it will remove all points currently in the drawing and allow you to start from scratch.

Handing In

Run the handin script cs016_handin convexhull . As always, save your README file in the same directory was your code and it will be handed in along with your file.

Support Code

See the Convex Hull documentation linked on the assignments page.

Closing

Come to the helpsession and do the reading before you even think about starting to code. There are quite a few resources available for this project – the textbook (and the textbook supplements), lecture slides, helpsession, Javadocs, and (last but not least, with the emphasis on last) your friendly TA staff – so use them! You may be sick of hearing this from CS15, but please do start early. Good luck!