QuickHull Assignment

Due Friday, March 25, 2011 by 11:59 p.m.

Write a C++ implementation of the quick hull algorithm. Your program must include, at a minimum, a class to represent a point, a class to represent a list of points (this must be implemented as a linked list), and a main driver program. The list class should be used to model both the set of points and the hull (actually the boundary of the hull). The convex hull should be a list of points in order around the boundary (two points in the list are adjacent if and only if they are endpoints of a line segment that makes up the boundary of the hull).

Input to the program should come from a file containing a list of x and y coordinates of points in the set. Each line will be the x coordinate followed by the y coordinate, separated by spaces. The coordinates will be type double. Output should be the list of extreme points of the set that make up boundary of the hull. They must be in order around the hull (either clockwise or counterclockwise).

Using Files in C++

The programs FileIO.cc and FileIOEOF.cc show how to open files, use them to read from and write to, and close them. Both read a sequence of integers, find the sum and average, and write the number of integers, the sum, and the average to another file. FileIO.cc assumes the first integer in the input file is the number of integers to be read so it reads that integer then reads and processes that many integers. FileIOEOF.cc assumes each integer in the file is a data value to be processed so it reads and processes until it reaches the end of the file.

Note that the file stream must be explicitly closed.

Requirement

Your program must be well-documented and adhere to good programming practice as described in this document.

REMINDER: This is an assignment so the work is to be your own without collaboration or consulting any other sources (including the internet) except for the instructor (you may ask as many questions as you want!).

Submit

A tar or zip file containing all files for your program including at least three test files.