600.459

Assignment 1

Due: Sunday (02/21/16)

You can download the code stub from here.

Implement the O(

To do, this you will need to implement the

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.

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.

HOME