Introduction to Computational Geometry
600.459
Assignment 3
Due: Sunday (05/05/16)
CODE
You can download the code stub from here.
(Note that the code also includes the stub for the previous assignments.)
ASSIGNMENT
- 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.
To run the convex-hull code, you need to specify the number of points samples and the output convex hull:
% 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.
EVALUATION
Code and results will be evaluated based on correctness (and efficiency).
SUBMISSION
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.)
VISUALIZATION
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