Announcements

Overview

• The code skeleton can be downloaded here.
• Some input point sets can be downloaded here.
• Note that input and output geometry is in the PLY file format.

• To compute the dual Delaunay Triangulation you need to specify an output PLY file. Otherwise, if one is not specified, an OpenGL viewer will pop up, allowing you to visualize the implementation as the sweep-line advances.

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 ConvexHull3D and Delaunay2D executables by clicking on "Build" and then selecting "Build Solution".
  • The executables ConvexHull3D.exe and Delaunay2D.exe are compiled in Release mode for the 64-bit architecture and will be placed in the directory Bin/x64/.
  Note that the Bin/x64/ directory contains the files glut32.lib and glut64.dll which should be enough to get you running on Windows.
• On a Unix Machine
  
  • Type make to compile the VoronoiDiagram2D executable.
  • The executables ConvexHull3D and Delaunay2D are compiled in Release mode and will be placed in the directory Bin/Linux/.
  Note that you will likely need to install the glut libraries on you machine, as well as the JPEG, PNG, and ZLIB libraries for the code to compile.

How the Program Works

--in <input 2D point set>

This string specifies the name of the file from which the 2D sites are read.
The representation of the geometry is assumed to be in PLY format.

[--out <output Delaunay Triangulation>]

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

[--stepSize <step size>=0.1]

This optional floating point value indicates the size of the steps used to advance the sweep-line forward when visualizing using constant step sizes instead of advancing directly to the next event.

[--ascii]

If this arugment is provided the output PLY file will be written out in ASCII, making it easy to read using a standard text editor. Otherwise it will be written out in binary to save space.

[--verbose]

If this arugment is provided the executable will provide verbose output about the state of the algorithm (including running the sanity checker after each event to ensure that the beach-line is self-consistent.)

What You Have to Do

Evaluation

Submission