Announcements

• Note that the polygon representation used in the code stores a list of vertex positions, and the triangles/polygons store the index of the associated vertex within the list. This is different from the polygon vertex class described in the notes which stores the position (not the vertex index) within each element of the linked list.
• 2/17/2020 The triangulation slides have been modified to remove bugs in the pseudocode.
• 2/20/2020 If you are compiling on a Mac, you may be running into trouble because the default compiler, Clang, does not support OpenMP. The Makefile in the archive has been updated. If you have trouble running it (e.g. because you don't have gcc-9 installed, you can either change lines 27 and 28 of the Makefile to reference the right version, or you can install an up-to-date version of gcc by typing:

  % brew install gcc

  or you can update to an up-to-date version of gcc by typing:

  % brew upgrade gcc

• 2/26/2020Added testing polygons.

Overview

• The code skeleton can be downloaded here.
• Three example polygons containing 23, 25, 49, and 99 vertices are provided for testing.

• Six additional polygons containing 4, 8, 16, 32, 64 and 128 vertices are provided for testing. (The vertices are guaranteed to have distinct y-coordinates.)
• Note that input and output geometry is in the PLY file format.

• 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. (Note that you will need to click on the "Wireframe" icon to see your triangulation. Also, if you try loading the input polygon into MeshLab you will see something of a mess because MeshLab does not compute a nice trangulation.)

  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.

Getting Started

/////////////////////////////
// You need to implement this
/////////////////////////////

After you download the files, the first thing to do is compile the program.

• On a Windows Machine
  Begin by double-clicking on Assignments.sln to open the workspace in Microsoft Visual Studios.
  • Compile the Triangulation executable by clicking on "Build" and then selecting "Build Solution".
  • The executable Triangulation.exe is compiled in Release mode for the 64-bit architecture and will be placed in the directory Bin/x64/.
• On a Unix Machine
  
  • Type make Triangulation to compile the Triangulation executable.
  • The executable Triangulation is compiled in Release mode and will be placed in the directory Bin/Linux/.

How the Program Works

--in <input polygon>

This string is the name of the file from which the polygon will be read.
The representation of the geometry is assumed to be in PLY format.

[--out <output triangulation>]

This string is the name of the file to which the triangulation will be written.
The representation of the geometry is assumed to be in PLY format.

[--viewable]

Enabling this flag will have the output be written as a triangle mesh in 3D (with the z-coordinate set to zero). This will allow you to use off-the-shelf mesh viewers for visualizaing your results.

What You Have to Do

• Implement the O(n²) algorithm for computing the triangulation of a polygon with n vertices by implementing the SlowTriangulate function in Triangulation.cpp
• Implement the O(n log n) algorithm for computing the triangulation of a polygon with n vertices by implementing the QuickTriangulate function in Triangulation.cpp. (You will need to modify this function so that it outputs true.) For this implementation you can assume that no two points have the same y-coordinate.
• Extra Credit: 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

Submission