Announcements

Overview

• The code skeleton can be downloaded here.
• Note that input and output geometry is in the PLY file format.

• To visualize/debug the results of your convex hull computation, you can run the executable with the --viewable flag and use an application like MeshLab to view the results. (If you did things right, your result should be a convex polygon so MeshLab should not have trouble visualizing it.)

  Alternatively, you can try to compile the PLY viewing code here (which requires that GLUT be installed). You can invoke the viewer by calling:

  % PLYViewer convexhull.ply --noLight --boundary

  which will show both the boundary of the polygon and the edges of the triangles.

Getting Started

/////////////////////////////
// You need to implement this
/////////////////////////////

After you download the files, the first thing to do is compile the program.

• On a Windows Machine
  Begin by double-clicking on Assignments.sln to open the workspace in Microsoft Visual Studios.
  • Compile the ConvexHull2D executable by clicking on "Build" and then selecting "Build Solution".
  • The executable ConvexHull2D.exe is compiled in Release mode for the 64-bit architecture and will be placed in the directory Bin/x64/.
• On a Unix Machine
  
  • Type make ConvexHull2D to compile the ConvexHull2D executable.
  • The executable ConvexHull2D is compiled in Release mode and will be placed in the directory Bin/Linux/.

How the Program Works

--count <input vertex count>

This integer specifies the number of points in the point set.

[--out <output 2D hull>]

This string is the name of the file to which the convex hull will be written.
The representation of the geometry is assumed to be in PLY format.

[--aType <algorithm type>=0]

This integer specifies the type of algorithm used to generate the convex hull. Options include:

• 0: Naive (provided for you)
• 1: QuickHull
• 2: Graham's algorithm

[--sRand <random seed>=0]

This integer specifies the seed for the random number generator.

[--res <grid resolution>=1024]

This integer specifies the resolution of the grid used for generaing the random samples. (Note that as the generated point samples are distinct, the resolution should be large enough to ensure there are enough different possible points.)

[--viewable]

Enabling this flag will have the output be written as a triangle mesh in 3D (with the z-coordinate set to zero). This will allow you to use off-the-shelf mesh viewers for visualizaing your results.

What You Have to Do

• Implement the QuickHull algorithm for computing the convex hull of a set of points by implementing the QuickHullAlgorithm function in ConvexHull2D.cpp
• Implement Graham's Algorithm for computing the convex hull of a set of points by implementing the GrahamsAlgorithm function 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 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).
• Extra (Half) Credit: Implement the incremental algorithm.
• Extra (Half) Credit: Implement the divide-and-conquer algorithm.

Evaluation

Submission