convexhull
Class MyHull

java.lang.Object
  convexhull.MyHull

All Implemented Interfaces:

ConvexHull

public class MyHull
extends Object
implements ConvexHull

An implementation of an incremental convex-hull implemented with an ordered dictionary. For this particular implementation, that ordered dictionary is a red-black tree, but this choice of data structure is not essential to the functionality of the hull. The x-coordinates of the points are used as keys. Be certain that your running times match those specified in the program documentation! Feel free to add additional comments.

Constructor Summary

MyHull()
Set up and initialize the instance variables, adding new ones at the top of the file if necessary or desired.

Method Summary

Iterator<Entry<Integer,HullPoint>>	bottomChain() Get an Iterator containing all Entry<Integer, HullPoint> in the bottom chain of the hull.
void	clear() When the user clicks on the "Clear" button, the HullHelper class will call this method.
void	insert(HullPoint vertex) This method will be called by the HullHelper when a user clicks on the screen to add a vertex.
static void	main(String[] args) WARNING: Program mainline.
Iterator<Entry<Integer,HullPoint>>	topChain() Get an Iterator containing all Entry<Integer, HullPoint> in the top chain of the hull.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MyHull

public MyHull()

Set up and initialize the instance variables, adding new ones at the top of the file if necessary or desired.

Method Detail

main

public static void main(String[] args)

WARNING: Program mainline. Do not modify this method!

insert

public void insert(HullPoint vertex)

This method will be called by the HullHelper when a user clicks on the screen to add a vertex. When the GUI calls this method, the ConvexHull should decide if the new vertex should be on the hull or not. If the new point is on the hull, the ConvexHull should add it to the hull and then adjust the hull so that it is now convex. This method must run 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. WARNING: This can be a tricky running time to implement, but it is an essential feature of the project. Do *not* consistently traverse the entire hull to insert a point or you will violate running time requirements and lose points! Examine the methods of RobotRBTree carefully to see what is available to you. The lecture slides and supplementary materials may offer suggestions as to how to approach this problem.

Do not call this method explicitly! The visualizer does this!

Specified by:

insert in interface ConvexHull

Parameters:

vertex - the newly created vertex resulting from a user click

clear

public void clear()

When the user clicks on the "Clear" button, the HullHelper class will call this method. The GUI will hide all of the points and erase all of the lines. The ConvexHull should reset its internal state. If you wish, you may rely on Java's garbage-collection to implement a "quick-and-dirty" reset method. Think about ways you might code this method and see a TA on hours if you don't see an efficient solution.

Do not call this method explicitly! The visualizer does this!

Specified by:

clear in interface ConvexHull

topChain

public Iterator<Entry<Integer,HullPoint>> topChain()

Description copied from interface: ConvexHull

Get an Iterator containing all Entry<Integer, HullPoint> in the top chain of the hull.

Specified by:

topChain in interface ConvexHull

Returns:

an Iterator containing all the HullPoints in the upper chain of the hull

bottomChain

public Iterator<Entry<Integer,HullPoint>> bottomChain()

Description copied from interface: ConvexHull

Get an Iterator containing all Entry<Integer, HullPoint> in the bottom chain of the hull.

Specified by:

bottomChain in interface ConvexHull

Returns:

an Iterator containing all the HullPoints in the lower chain of the hull