Introduction to Computational Geometry
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 Timer.h header that you will need for measuring performance.)
To run the code, you need to specify the number of points samples and the output convex hull:
- 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:
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).
- 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
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.