Introduction to Computational Geometry
600.459
Assignment 2
Due: Sunday (03/13/16)
CODE
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 Timer.h header that you will need for measuring performance.)
ASSIGNMENT
- 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.
Use these results to guess the (average) complexity of the convex hull of a set of points uniformly distributed within a disk and to determine whether the implementation is output-sensitive (and if so, how).
To run the code, you need to specify the number of points samples and the output convex hull:
% 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.
EVALUATION
Code and results will be evaluated based on correctness (and efficiency).
SUBMISSION
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.)
VISUALIZATION
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