MCS 481: Compiling a CGAL example

The first MCS 481 homework assignment is to demonstrate that you have access to a working CGAL installation and compatible C++ build environment, and then to email a screenshot of you running one of the example programs to ddumas@math.uic.edu.

The following screenshot is an example of what a completed assignment might look like on a computer using Debian or Ubuntu GNU/Linux:

(See the full-size version.)

This page simply explains what is happening in the sample screenshot.

Setting

We are working in a terminal on pieri.math.uic.edu, a computer running Debian GNU/Linux and where the packages for CGAL and for a C++ compiler have already been installed.

The same steps listed below should work on a recent Ubuntu GNU/Linux system after installing the necessary packages, which (as of Ubuntu 12.04) can be accomplished with the following commands:

sudo apt-get update
sudo apt-get install g++ cmake libcgal-demo

All of the commands shown in the screenshot are run in the user's home directory.

Steps

Let's look at each of the commands in the screenshot. By default the source code for the CGAL example programs is installed as a compressed archive in a documentation directory. Thus, we decompress the archive with the first command:

tar --gzip -xf /usr/share/doc/libcgal-demo/examples.tar.gz

The command does not display any output, but the decompressed source code is now located in a subdirectory named examples. If we wanted a list of the files as they are decompressed, we could add the verbose flag, as in tar --gzip -xvf /usr/share/doc/libcgal-demo/examples.tar.gz.

Next we move into the subdirectory containing examples related to 2-dimensional convex hulls:

cd examples/Convex_hull_2

Now we compile an example program called ch_from_cin_to_cout which reads a list of vertices from standard input (also known as "cin")and writes a list of convex hull vertices to standard output ("cout"):

g++ -lCGAL -lgmp -frounding-math ch_from_cin_to_cout.cpp

This runs the GNU C++ compiler, g++, with options:

• -lCGAL, to link against the library (-l) named CGAL
• -lgmp, to also link against gmp (the GNU Multiple Precision Arithmetic Library, which CGAL requires)
• -frounding-math, which allows the program to make adjustments to the way floating-point types are handled (as CGAL requires). Without this option, CGAL programs will fail when they detect problems adjusting the floating-point environment.
• ch_from_cin_to_cout.cpp, the name of the C++ source file to compile.

By default the compiler writes the executable program to a.out, but it is a good practice to give it a more meaningful name. We could have done that with an option like:

• -och_from_cin_to_cout, so that the compiler's output (-o) would be called ch_from_cin_to_cout, which is the name of the source file with its .cpp extension removed.

We run the compiled program on a sample dataset:

./a.out < ch_from_cin_to_cout.cin > hull.txt

This runs the executable program a.out in the current directory (./). If run without any additional parameters on the command line, this program would read its input from the terminal, requiring us to type vertex coordinates. Instead, we want to read these from a file, and we want to write the output to another file. We use input and output redirection for this:

• < ch_from_cin_to_cout.cin : Standard input should read from the existing file named ch_from_cin_to_cout.cin, a dataset included with the CGAL examples for demonstration purposes. (You can look at the list of vertices in this file with a command like cat ch_from_cin_to_cout.cin.)
• > hull.txt : Standard output should write to a (new) file named hull.txt.

Because of the output redirection, this command produces no output in the terminal window.

Finally we do a very basic check on the results, comparing the number of vertices in the input file and the output file:

wc -l ch_from_cin_to_cout.cin

500 ch_from_cin_to_cout.cin

This output means that the text file ch_from_cin_to_cout.cin has 500 lines. Each line contains the coordinates of one input point, so our dataset has 500 points. This is the data the convex hull program read in the last step. The command wc counts the number of lines, words, or characters in a file. The option -l indicates we want a count of lines.

wc -l hull.txt

55 hull.txt

Similarly, the output of the convex hull program has 55 lines, containing the 55 vertices of the convex hull. While this is not a very careful check of the output, it is a good sign that the number of lines is greater than zero (an empty output file would indicate some kind of problem) and less than the number of input points.

Examining the input and output

While it is beyond the scope of the assignment, using a graphing utility such as gnuplot we can visualize the input and output of the convex hull program:

The first image was created with the following gnuplot script:

set term png
set output "input.png"
set title "Points"
set size square
set key off
set xrange [-1000:9000]
set yrange [-1000:9000]
plot "ch_from_cin_to_cout.cin" w p ps 0.25

The second image was created by first making a file hull_closed.txt containing the list of convex hull vertices followed by a repeated line containing the first vertex, using the shell commands

cp hull.txt hull_closed.txt
head -1 hull.txt >> hull_closed.txt

and then using a gnuplot script:

set term png
set output "output.png"
set title "Convex Hull"
set size square
set key off
set xrange [-1000:9000]
set yrange [-1000:9000]
plot "ch_from_cin_to_cout.cin" w p ps 0.25, \
     "hull_closed.txt" w p ls 3, \
     "" w l

Up: MCS 481