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:
- the Kernel with geometric primitives such as points, vectors, lines,
predicates for testing things such as relative positions of points, and
operations such as intersections and distance calculation.
- the Basic Library which is a collection of standard data structures
and geometric algorithms, such as convex hull in 2D/3D, (Delaunay)
triangulation in 2D/3D, planar map, polyhedron, smallest enclosing circle,
and multidimensional query structures.
- the Support Library which offers interfaces to other packages, e.g.,
for visualization, I/O, and other support facilities.
Programme.
Tuesday 30/11
- 9h30 (room B13) : Introduction to CGAL (Monique Teillaud) (slides) and
Introduction to Generic Programming (Sylvain Pion) (slides)
- 14h00 (room B13) : Robustness issues in CGAL : arithmetics and the kernel (Sylvain Pion) (slides)
Wednesday 1/12
- 9h30 (room A008) : Triangulations in CGAL (Monique Teillaud) (slides)
- 14h00 (Salle Callot, St Fiacre) : exercises
Thursday 2/12
- 9h30 (Salle Callot, St Fiacre) : exercises
Participants.
- Fabien Boutantin, LORIA ALICE
- Isabelle Debled-Rennesson, LORIA ADAGE
- Laurent Dupont, LORIA VEGAS
- Hazel Everett, LORIA VEGAS
- Laurent Fousse, LORIA SPACES
- Marc Glisse, LORIA VEGAS
- Xavier Goaoc, Eindhoven University
- Sylvain Lazard, LORIA VEGAS
- David Ledez, LORIA ALICE
- Kassiana Mesquita Da Costa, DEA Nancy
- Patrick Pelissier, LORIA SPACES
- Maria Pentcheva, LORIA VEGAS
- Sylvain Petitjean, LORIA VEGAS
- Laurent Provot, DEA Nancy
- Jan Rendek, LORIA QGar
- Mark Schroders, Eindhoven University
- Damien Stehle, LORIA SPACES
- Linqiao Zhang, McGill University / LORIA VEGAS
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
)
-
CGAL=/local/isa/outils/CGAL-3.1-I-199
-
CGAL_MAKEFILE=$CGAL/make/makefile_i686_Linux-2.6.8.1_g++-3.3.2
-
PATH=$PATH:/usr/local/geomview-1.8.2/bin
(to find geomview
)
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 :
-
cp -r $CGAL/demo/Triangulation_2 .
Then go into the directory, and compile one of them :
cd Triangulation_2 ; make delaunay_triangulation_2
And run one of them :
-
./delaunay_triangulation_2
(click on the "Input Point" icon...).
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.
- 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.
- 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.
-
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.
-
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).
-
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.
- Modify the program such that
- a left click inserts a point in Delaunay (unchanged)
- a right click triggers the display of the entered point in blue (unchanged)
- at each middle click, we enumerate the neighbors of the blue point in the triangulation :
- first click, the nearest neighbor,
- second click, the second nearest neighbor,
- third click, the third nearest neighbor,
- ...
- To do more :
- Modify the triangulation to add a color to the points (red or blue)
- Modify the display of the triangulation in accordance
- Left click = insert a red point
- Right click = insert a blue point
- Middle click = display the closest red and the closest blue points
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.
- change
float
to double
and observe that it is
possible to put more points.
- generate a naughtier example by inserting first an enclosing box, then
random points on a line segment (a piece of plane), and observe that it
crashes even with
double
.
- use an exact number type
- use a filtered kernel
- compare execution times of these different solutions in a hard case, and
in an easy case (random points).
Solutions for dimension 2 and dimension 3.
Some of the exercises are courtesy of
Olivier Devillers
and Steve Oudot