Announcements

• See here if you are implementing Fortune's Algorithm.

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 ConvexHull3D and Delaunay2D executables by clicking on "Build" and then selecting "Build Solution".
  • The executables ConvexHull3D.exe and Delaunay2D.exe are compiled in Release mode for the 64-bit architecture and will be placed in the directory Bin/x64/.
• On a Unix Machine
  
  • Type make ConvexHull3D and make Delaunay2D to compile the ConvexHull3D and Delaunay2D executables.
  • The executables ConvexHull3D and Delaunay2D are compiled in Release mode and will be placed in the directory Bin/Linux/.

How the Programs Works

--count <input vertex count>

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

[--out <output 3D 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: Gift-Wrap
• 1: Incremental

[--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.

--count <input vertex count>

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

[--out <output 3D 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.

[--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 Incremental algorithm for computing the convex hull of a set of points by implementing the IncrementalAlgorithm function in ConvexHull3D.cpp
• Implement the Gift-Wrapping algorithm for computing the convex hull of a set of points by implementing the GiftWrapAlgorithm function in ConvexHull3D.cpp.
• Implement Edelsbrunner and Seidel's algorithm for computing the Delaunay Triangulation of a set of points by implementing the Delaunay function in Delauanay2D.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 Credit: Implement code that computes the Voronoi Diagram of a set of points in 2D. (Note: Beware of infinite eges.)
• Extra Credit: Implement Lloyd's algorithm for a set of points distributed inside a square. (Note: In computing the center of mass, if the Voronoi faces go outside the square you will need to "trim" them.)
• Extra Credit++: Implement Fortune's algorithm for computing the Voronoi Diagram and output its dual, the Delaunay Triangulation.

Evaluation

Submission