CGAL course in Nancy
(30/11/04 - 02/12/04)

Monique Teillaud and Sylvain Pion
(INRIA Sophia Antipolis)

Abstract.

CGAL is an Open Source Project started as a collaborative effort of several sites in Europe and Israel. The goal is to make the most important of the solutions and methods developed in computational geometry available to users in industry and academia in a C++ library, by providing easy access to useful, reliable geometric algorithms.

The CGAL library contains:



Programme.

Tuesday 30/11

Wednesday 1/12

Thursday 2/12



Participants.

Emails : teillaud@sophia.inria.fr, pion@sophia.inria.fr, Fabien.Boutantin@loria.fr, Isabelle.Debled-Rennesson@loria.fr, Laurent.Dupont@loria.fr, Hazel.Everett@loria.fr, Laurent.Fousse@loria.fr, Marc.Glisse@loria.fr, Xavier.Goaoc@loria.fr, Sylvain.Lazard@loria.fr, David.Ledez@loria.fr, Kassiana.Mesquita-Da-Costa@loria.fr, Patrick.Pelissier@loria.fr, Maria.Pentcheva@loria.fr, Sylvain.Petitjean@loria.fr, Laurent.Provot@loria.fr, Jan.Rendek@loria.fr, M.F.A.Schroders@tue.nl, Damien.Stehle@loria.fr, Linqiao.Zhang@loria.fr



Exercises.

Exercise #0 : Setup your CGAL environment

You first need to have a working environment for CGAL.
CGAL is installed on the machine amande.loria.fr, in the directory /local/isa/outils/CGAL-3.1-I-199.
Version 3.1-I-199 is almost the same as the next public release 3.1, to be released soon.

Please check that you have the following environment variables correctly set:

Under a Bourne shell (e.g. bash, but not tcsh)

Check that you have access to the documentation installed here.
Note that the documentation of the current public release (3.0.1) can be found here.

Now let us make an attempt at compiling one of the demos coming with CGAL.
Copy the 2D triangulations demos in your working directory :

Then go into the directory, and compile one of them :

And run one of them :

You can try other demo programs, as well as example programs located in $CGAL/examples/.

Don't forget to cleanup the disk space after you are done !



Exercise #1 : beginning with CGAL

Get the initial program and compile it with the makefile.

The left mouse button inserts a point in the Delaunay triangulation,
the middle button prints the coordinates of the entered point,
and the right button displays the entered point.

The triangulation and the last entered point (right click) are displayed after each click.

You will need the documentation of CGAL.

  1. Modify the program so that the right button triggers the display of the entered point in blue, as well as its nearest neighbor within the Delaunay triangulation vertices in green.
  2. Modify the program so that the middle button triggers the display, in orange, of the triangle containing the entered point as well as its circumscribing circle in black.
  3. Modify the program so that the interior of the triangles are colored in light red if the ratio (area of the triangle / area of the circumscribing circle) is less than 0.3, and in light green otherwise.
  4. During a right click, display as well all the incident triangles to the nearest neighbor of the entered point (successively after a 1 second pause between each triangle).
  5. During a middle click, display all triangles crossed by a horizontal line passing through the entered point.

Here are some elements of the solution (of the first 3 questions).



Exercise #2 : 3D alpha shapes

Alpha shapes are a generalization of the convex hull of a finite point set.

Let S be a set of points in R3 and alpha a real number. We'll restrict to the case alpha>0.
3 points p, q, r in S form a facet of the alpha shape of S iff there exists an open ball of radius sqrt(alpha) empty of any point of S and whose boundary contains p, q, r.

Propose a simple method to compute the alpha shape of S from the Delaunay triangulation of S.
Implement the computation of the alpha shape using CGAL.
You can start from the frame.C skeleton, and you can use the various sets of points provided in a few files here.

One possible solution can be found here. You should obtain the following kind of result under Geomview:



Exercise #3 : More Delaunay

This is a folluw-up of exercise #1. First, get the initial program and compile it with the makefile. You will need the CGAL documentation. Here is the solution (first question). solution (second question).
STL hint :

class Dist_order
{
  const Delaunay *t;
  const Point *p;

public:
  Dist_order(const Delaunay *tr, const Point *po)
    : t(tr), p(po) {}

  bool operator()(VertexH v1, VertexH v2) const
  {
    return CGAL::compare_distance_to_point(*p, v1->point(), v2->point()) == CGAL::SMALLER;
  }
};

typedef std::set<VertexH, Dist_order> Queue;


Exercise #4 : Robustness issues

The provided programs crash in dimension 2 and dimension 3 for a sufficiently high number of points. Solutions for dimension 2 and dimension 3.

Some of the exercises are courtesy of Olivier Devillers and Steve Oudot