Introduction to Computational Geometry
600.459
Assignment 1
Due: Sunday (02/21/16)
CODE
You can download the code stub from here.
ASSIGNMENT
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.

EXTRA CREDIT #1
Implement the O(n log n) algorithm for computing the triangulation of a polygon with n vertices.
EXTRA CREDIT #2
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.

EVALUATION
Code will be evaluated based on correctness (and efficiency).
SUBMISSION
Please email your implemented source code to me. (The code should compile under Windows/Linux and should not require any additional libraries.)
VISUALIZATION
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.

HOME