Introduction to Computational Geometry
Assignment 1

Due: Sunday (02/21/16)

You can download the code stub from here.
Implement the O(n^2) algorithm for computing the triangulation of a polygon with n vertices.
To do, this you will need to implement the Triangulate function in Triangulation.cpp.

To run the code, you need to specify the input polygon name and the output triangulation name:

% Triangulate --in poly.ply --out triangulation.ply

Three example polygons containing 23, 49, and 99 vertices are provided for testing.

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

Implement the O(n log n) algorithm for computing the triangulation of a polygon with n vertices.
Write code that takes n distinct points on the integer lattice (not necessarily in general position) and returns a polygon that has those points as its vertices.

Code will be evaluated based on correctness (and efficiency).
Please email your implemented source code to me. (The code should compile under Windows/Linux and should not require any additional libraries.)
To visualize/debug the results of your triangulation, you can run the executable with the --viewable flag and use an application like MeshLab to view the results.

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 triangulation.ply --noLight --boundary --edges

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