Project : geometrica

Section: New Results

Geometric computing and Cgal

Rounding of polygons

Participants : Olivier Devillers, Philippe Guigue.

One way to address robustness issues in geometric algorithms is to follow the exact computation paradigm that asks to evaluate all predicates exactly. Recent work has proved that this approach can be made very efficient for most single geometric algorithms. However, in some applications, it is necessary to embed the result in some representable space (say the grid of floating numbers) : we are then faced with the problem of rounding the result in accordance with the computed (possibly in an exact way) combinatorial output. This issue is especially critical when several algorithms are cascaded, i.e. when the output of an algorithm is used as input for another algorithm in a repeated way. For such use, one needs to round intermediate results while preserving some geometric properties. We have developed algorithms for boolean operations on polygons in the plane with guarantees on the inclusion between the true result and the rounded result and also guarantees on the distance and the number of vertices of the rounded result [12].

Visualization

Participants : Radu Ursu, Laurent Rineau.

cgal now has a 2D visualization tool based on the Qt software from TrollTech. It has been chosen because of the portability feature (Windows/Unix). All 2D cgal packages now have at least one demonstration program based on this tool.

Windows support

Participant : Radu Ursu.

Support for the Windows platform has been considerably improved in cgal 3.0. In particular, the newest version of the Visual C++ compiler is supported. The user has now access to a standard installation tool Install Shield, and the use of the integrated development environment provided by Microsoft Developer Studio has been greatly facilitated.