• Implement the Incremental algorithm in the IncrementalAlgorithm stub in ConvexHull3D.cpp
• Implement the Gift-Wrapping algorithm in the GiftWrapAlgorithm stub in ConvexHull3D.cpp
• Implement Edelsbrunner and Seidel's algorithm in the Delaunay stub in Delaunay2D.cpp
• Measure the running times of the two convex-hull implementations 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.

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

To run the Delaunay-Triangulation code, you need to specify the number of points samples and the output triangulation:

% Delaunay2D --count <number of random samples to generate> --out dt.ply

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

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

EXTRA CREDIT #1
Implement code that computes the Voronoi Diagram of a set of points in 2D. (Note: beware of infinite edges.)

EXTRA CREDIT #2
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 #3
Implement the half-edge datastructure (for the inrcemental algorithm) without using a hash-table.

NOTES:

• For the implementation of the half-edge datastructure in the incremental algorithm, you should be careful in following the implementation in the notes. That code was designed for the case when you have a mesh, described in terms of vertices and triangles, and you want to construct a single half-edge representation. In this code, you want a half-edge represenation that supports dynamic updates. In particular, you will likely need to store vertices/edges/faces as arrays of pointers so that you can add and remove vertices/edges/faces from the convex hull representation without invalidating references.
• To support dynamic update of the convex hull, you should consider having your half-edge class store an additional member that is a pointer to the new triangle that connects the half-edge on the visibility boundary to the vertex that is incrementally added, and having your vertex class store an additional member that is a pointer to the new half-edge that links the vertex on the visibility boundary to the vertex that is incrementally added.
• After each step of incremental update, make sure to clean up your vertex/edge/face lists so that only pointers to geometry that is on the current hull exist.
• If you want more guidance on constructing a datastructure that supports the incremental algorithm, look at Section 4.3 in O'Rourke's Computationl Geometry in C book.