2014 | OriginalPaper | Buchkapitel
CGAL – Reliable Geometric Computing for Academia and Industry
verfasst von : Eric Berberich
Erschienen in: Mathematical Software – ICMS 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Cgal
, the Computational Geometry Algorithms Library, provides easy access to efficient and reliable geometric algorithms. Since its first release in 1997,
Cgal
is reducing the the gap between theoretical algorithms and data structure and implementations that can be used in practical scenarios.
Cgal
’s philosophy dictates correct results for any given input, even if intermediate round-off errors occur. This is achieved by its design, which separates numerical constructions and predicates from combinatorial algorithms and data structures. A naive implementation of the predicates and constructions still leads to wrong results, but reliable versions are shipped with the library.
Cgal
is successful in academic prototypical development and widely spread among industrial users. It follows the design principles of C++’s Standard Template Library.
Cgal
, now available in version 4.4, is already quite comprehensive. Nevertheless, it is still growing and improving.
We first introduce the library, its design and basics and then present major packages, such as triangulations and arrangements. We also illustrate showcases of how
Cgal
is used for real world applications asking for reliable geometric computing. The second part covers recent additions and contributions to the project: We discuss periodic and hyperbolic triangulations. The arrangement package has seen improvements for point location, rational functions and multi-part curves. It has also been extended with support for algebraic curves. This relies on several new packages that enable operations on (multivariate) polynomials and topology computation of such curves. Geometric objects in higher dimensions can now be represented using combinatorial maps; the instance for linear objects, namely the linear cell complex, is of particular interest.
Cgal
also provides data structures and algorithms for geometric sorting in arbitrary dimensions. Finally we present
Cgal
’s achievements to replace serial implementations with versions that support up-to-date multi-core architectures.