Assignment 2: Convex Hull - Java

The convex hull of a set of points is the set of points which induce the smallest convest polygon around the points of the set. There are many different mechanisms for solving the convex hull problem, but one of the most efficient algorithms (in amortized analysis) is known as Quick Hull. This algorithm is innately recursive, and is probably the easiest algorithm to implement in ML.

Details

For this assignment, you are required to implement the following interface:

import java.awt.geom.Point2D;

public interface ConvexHullInterface {
    //*****************************************************************
    // Pre:  Takes a well defined Point2D.Float object
    //Post:  Adds that point to the set of points considered for the
    //       convex hull. 
    //*****************************************************************
    public void addPoint(Point2D point);

    //*****************************************************************
    // Pre:  The attribute storing the points is well defined
    //Post:  Returns an array of Point2D object, which represent ALL of
    //       the points on the convex hull.
    //*****************************************************************
    public Point2D[] getHull();

    //*****************************************************************
    // Pre:  The attribute storing the points is well defined
    //Post:  Returns an array of Point2D object, which represent ALL of
    //       the points stored in this object.
    //*****************************************************************
    public Point2D[] getPoints();

    //*****************************************************************
    // Pre:  None
    //Post:  Returns an integer representing the number of points
    //       currently stored inside of the attribute storing the
    //       points.
    //*****************************************************************
    public int getNumPoints();

    
}

This interface is required, as a visualization program will be provided which will display the convex hull you have created. as such, order of the points returned is now important!!!!!. You should return a sequence of points which, when connected, displays the convex hull.

You may use any additional classes and methods as you wish, but you MUST implement the above interface.

Note: The Point2D class is built into the Java extended libraries. However, creating a new Point2D is weird. There are two sub-clases of the Point2D abstract class, which are the only objects you can instantiate. As such, to create a new Point2D for the purposes of this project, you need to:

Point2D my_new_point = new Point2D.Float(1, 2);

Algorithm

Included from the previous assignment, in case you need a refresher.

The Quick Hull algorithm is an inherently recursive definition that relies on the fact that certain points can be computed that MUST be on the convex hull. At a broad level, the algorithm involves:

1. Find two points which must be on the convex hull. These two points are those with the maximum and minimum x-coordinates. If there are several points with the same maximum or minimum coordinates, the tie is broken using the maximum/minimum y-coordinates.
2. Compute the line that passes through these two points. This line divides the set of points into two sets, which are recursively processed by:
   1. Find the point that is farthest from the base line that created the set. That point MUST be on the convex hull.
   2. Compute two lines, one that joins the end points of the base line to this new point. This creates 3 sets: The points inside the triangle, the points to the left of the triangle, and the points to the right of the triangle. Recursively process the points on the left and right sets until they are empty. The points inside the triangle cannot possibly be in the set.

Grading

Your programs will be graded on a scale split across both functionality (80%) and style (20%). Style points are earned from proper documentation (described above), and appropriate usage of object oriented techniques.

Submission

Submit your ConvexHull.java file to inquire by March 21^st, 2016.

Notes

Assignments are to be done individually. You may ask class members, lab assistants, and others for help with system questions (e.g., "How do I compile a Java program?" or "How do I get a printout of my program?") or general information about a topic covered in class (e.g. "What is the symbol for boolean AND?") provided you can do so without divulging or receiving information specific to the solution of the assignment problem. You may not discuss any aspect of the design or coding of a program with anyone except the instructor. See the syllabus for more information.