600.459

Assignment 2

Due: Sunday (03/13/16)

You can download the code stub from here.

(Note that the code also includes the stub for the previous assignment, as well as the additional

- Implement the Quick-Hull algorithm in the
__QuickHullAlgorithm__stub in*ConvexHull2D.cpp* - Implement Graham's algorithm in
__GrahamsAlgorithm__stub in*ConvexHull2D.cpp* - Measure the running times of the three implementations (your two, plus the included naive implementation) on random point samples of the unit disk and plot:
- The output size as a function of the input size.
- The running time as a function of input size.
- The running time as a function of the output size.

`% ConvexHull2D --count <number of random samples to generate> --aType <algorithm type> --out hull.ply`

(The default value for the algorithm type is 0, corresponding to the naive implemenation, which is provided.)

Note that the output geometry is in the PLY file format.

Note also that, by default, samples are generated on the 256x256 lattice. If you need higher resolution (e.g. to get more samples) you can bump up the grid resolution using the `--res`

flag.

Code and results will be evaluated based on correctness (and efficiency).

Please email your implemented source code and write-up of performance estimates to me. (The code should compile under Windows/Linux and should not require any additional libraries.)

To visualize/debug the results of your convex hull calculation, you can run the executable with the

`--viewable`

flag and use the PLY viewer here to view the results.
HOME