600.459

Assignment 3

Due: Sunday (05/05/16)

You can download the code stub from here.

(Note that the code also includes the stub for the previous assignments.)

- 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`

(The default value for the algorithm type is 0, corresponding to the incremental implemenation.)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.

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