Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to CGAL.
Nothing was collected or created yet.
from Wikipedia
| CGAL | |
|---|---|
| Developer | CGAL Open Source Project |
| Initial release | 1996 |
| Stable release | 6.1
/ 1 October 2025 [1] |
| Repository | |
| Written in | C++ |
| Operating system | Linux, macOS and Microsoft Windows |
| Type | Libraries |
| License | License |
| Website | www |
The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) are also available.[2][3]
The software is available under dual licensing scheme. When used for other open source software, it is available under open source licenses (LGPL or GPL depending on the component). In other cases commercial license may be purchased, under different options for academic/research and industrial customers.[4]
History
[edit]The CGAL project was founded in 1996, as a consortium of eight research institutions in Europe and Israel: Utrecht University, ETH Zurich, Free University of Berlin, INRIA Sophia Antipolis, Martin-Luther-University Halle-Wittenberg, Max Planck Institute for Informatics Saarbrücken, Johannes Kepler University Linz, and Tel-Aviv University. The original funding for the project came from the ESPRIT project of the European Union.[5] Originally, its licensing terms allowed its software to be used freely for academic purposes, with commercial licenses available for other uses. CGAL Releases 3.x were distributed under the QPL license. Starting with CGAL 4.0, released in 2012, CGAL is distributed under the GPL version 3. As of 2013[update] it is managed by a thirteen-member editorial board, with an additional 30 developers and reviewers.[6]
The project started in 1996 as the pooling of the previous efforts of several project participants:PlaGeo and SpaGeo from Utrecht University, LEDA of the Max-Planck-Institute for Informatics and C++GAL of INRIA Sophia Antipolis. The LEDA library encompasses a broader range of algorithms. A comparison of the two libraries is provided by Kettner and Näher.[7] Three CGAL User workshops held in 2002, 2004, and 2008 highlighted research results related to CGAL,[8] and many additional papers related to CGAL have appeared in other conferences, workshops, and journals.[9]
In 2023 the project won the SoCG Test of Time Award[10]
Scope
[edit]The library covers the following topics:
- Geometry kernels - basic geometric operations on geometric primitives
- Arithmetic and algebra
- Convex hull algorithms
- Polygons and polyhedra
- Polygon and polyhedron operations
- Arrangements
- Point set triangulations
- Delaunay triangulations
- Voronoi diagrams
- Mesh generation
- Geometry processing
- Search structures (k-d tree)
- Shape analysis, fitting, and distances
- Interpolation
- Kinetic data structures
Platforms
[edit]The library is supported on a number of platforms:[11]
- Microsoft Windows (GNU G++, Microsoft Visual C++, Intel C++ Compiler)
- GNU g++ (Solaris, Linux, Mac OS)
- Clang
The CGAL library depends on the Boost libraries, and several CGAL packages on the Eigen C++ library.
See also
[edit]- OPEN CASCADE
- OpenSCAD (uses CGAL)
- GDAL (similar lib for Geo)
- PostGIS (uses CGAL and GDAL)
References
[edit]- ^ "CGAL 6.1 released".
- ^ CGAL bindings, developed at GeometryFactory.
- ^ CGAL Scilab bindings, developed at Scilab and INRIA by Edyta Przymus, Naceur Meskini and Sylvain Pion.
- ^ CGAL license
- ^ CGAL Project History.
- ^ CGAL Project Members.
- ^ Kettner, L.; Näher, S. (2004). "Two computational geometry libraries: LEDA and CGAL". Handbook of Discrete and Computational Geometry. pp. 1435–1464..
- ^ CGAL User Workshop program Archived 2007-09-07 at the Wayback Machine, 2nd CGAL User Workshop program Archived 2007-07-02 at the Wayback Machine and 3rd CGAL User Workshop program Archived 2008-06-24 at the Wayback Machine.
- ^ As of 2010[update], Google scholar lists 137 papers with CGAL in their titles.
- ^ "Awards - CG Week 2023 - the University of Texas at Dallas".
- ^ CGAL Supported Platforms
External links
[edit]from Grokipedia
CGAL (Computational Geometry Algorithms Library) is an open-source C++ software library that provides easy access to efficient and reliable algorithms and data structures for computational geometry in two and three dimensions.[1]
The library encompasses a wide range of geometric primitives and operations, including kernels for exact and approximate arithmetic on points, segments, and other basic objects; basic structures such as polygons, polyhedra, and arrangements of curves; and advanced algorithms like Delaunay triangulations, Voronoi diagrams, convex hulls, mesh generation, and Boolean operations on solids.[2] It also includes a support library with utilities for spatial sorting, random point generation, and interfaces to external tools like the Boost Graph Library and Qt for visualization.[2]
Originating in the early 1990s, CGAL emerged from independent geometry libraries developed by European research groups seeking robust tools for geometric computing.[3] In 1996, an international consortium of seven research sites, including institutions from France, Germany, Switzerland, the Netherlands, and Israel, formed under European Union funding to consolidate these efforts into a unified project.[4] The first version was released in 1997, with the library transitioning to a fully open-source model under a dual license (GPL/LGPL for free use and commercial options) in 2003 alongside the launch of version 3.0.[4] Today, CGAL is maintained by GeometryFactory—a company founded by project coordinator Andreas Fabri—and an active community of contributors from academia and industry, with regular releases ensuring compatibility with modern C++ standards, including the latest release, version 6.1, in October 2025.[1]
Widely adopted in fields such as computer graphics, geographic information systems, medical imaging, and robotics, CGAL emphasizes certified numerical robustness through exact predicates and certified constructions, making it suitable for both research and production environments.[5] In 2023, the project received the Test of Time Award from the Symposium on Computational Geometry for its enduring impact on the field.[4]
Since version 6.0 released in 2024, CGAL requires a C++17-compliant compiler, marking a shift to leverage modern language features for improved efficiency and code maintainability.[61] In version 6.1, support for older compilers such as GCC versions below 12 was dropped to focus on more recent toolchains with better optimization and standard adherence.[51][9]
Essential third-party dependencies include the Standard Template Library (STL) provided by the compiler, and Boost version 1.74 or later (headers-only).[9][51] For exact arithmetic, GMP version 5.0.1 or later is optional but recommended, paired with MPFR version 3.0.0 or later for interval computations.[9] Other optional dependencies, such as Eigen version 3.3.7 or later for linear algebra and CGAL_ImageIO for image handling in graphics-related packages, enhance functionality without being required for core usage.[9] CMake version 3.22 or later is necessary for building and configuring projects with CGAL.[9]
Introduction
Overview
CGAL is an open-source C++ software library that provides efficient and reliable algorithms and data structures for computational geometry.[1] It aims to offer easy access to geometric computing tools while ensuring robustness through support for exact arithmetic, including integration with the GMP library for arbitrary-precision rational numbers.[6] As of November 2025, the latest stable release is CGAL 6.1, released in October 2025; the library has been header-only since version 5.0 and requires a C++17-compliant compiler or later.[7][8][9] For broader accessibility, CGAL provides interfaces through bindings for Python, Java, and Scilab.[10][11]Purpose and Scope
The Computational Geometry Algorithms Library (CGAL) serves as a foundational C++ software library aimed at facilitating the development of robust and reliable geometric applications by providing a wide array of efficient algorithms, data structures, and primitives for computational geometry in 2D, 3D, and higher dimensions.[1] Its core purpose is to enable researchers and developers in industry and academia to implement solutions for complex geometric problems, such as arrangements of geometric objects and optimization tasks, while ensuring numerical stability and correctness in computations.[12] This focus addresses real-world challenges in fields including computer-aided design, medical imaging, robotics, and geographic information systems, where precise handling of geometric entities is essential.[1] The scope of CGAL encompasses exact, robust, and generic programming paradigms, supporting a variety of kernel models—including Cartesian, homogeneous, and those with exact predicates—to model geometric primitives like points, lines, and surfaces accurately across dimensions.[12] It provides certified algorithms with provable properties, such as worst-case optimality, for tasks like convex hull computation, ensuring outputs meet theoretical guarantees even in degenerate cases.[13] Boundaries are defined by its emphasis on geometric computation, integrating seamlessly with the Standard Template Library (STL) for interoperability without extending to unrelated domains.[14] Central to CGAL's design are key concepts like generic programming through traits classes, which allow adaptable algorithms by specifying required geometric operations and enabling customization for different kernel types or precision needs.[13] However, CGAL deliberately excludes general-purpose numerical libraries or algorithms outside geometry, such as graph theory beyond geometric embeddings, and prioritizes computational reliability—via exact arithmetic where necessary—over raw performance in scenarios prone to floating-point errors or ambiguities.[14][12]History
Origins and Founding
The CGAL project was established in 1996 as a collaborative effort among eight research institutions in Europe and Israel, aiming to develop a unified computational geometry software library. The founding consortium included Utrecht University (Netherlands), ETH Zurich (Switzerland), Freie Universität Berlin (Germany), INRIA Sophia-Antipolis (France), Martin-Luther-Universität Halle-Wittenberg (Germany), Max-Planck-Institut Saarbrücken (Germany), RISC Linz (Austria), and Tel Aviv University (Israel).[15] This partnership was coordinated by Utrecht University as the prime contractor, with the goal of pooling expertise to create robust geometric algorithms suitable for both academic research and industrial applications.[15] The motivations for CGAL's creation stemmed from the growing need for standardized, reliable libraries in computational geometry, as individual research groups had developed fragmented tools that lacked interoperability and certification. It built directly on predecessor projects, including PlaGeo and SpaGeo from Utrecht University, the geometric components of LEDA from the Max-Planck-Institut Saarbrücken, and C++GAL from INRIA Sophia-Antipolis, integrating these to form a cohesive C++-based framework.[16] This approach addressed the challenges highlighted in contemporary reports on the field, such as the demand for efficient, verifiable algorithms in areas like geographic information systems (GIS) and computer-aided design (CAD).[3] Initial development was supported by the European Union's ESPRIT Project 21957, which ran from October 1996 to July 1998 and provided funding for 21 months to focus on basic 2D geometric algorithms, data structures, and supporting features like input/output and visualization.[16][15] The project emphasized collaboration with industrial partners, including entities like Philips Research and Tecnomatix, to ensure practical applicability.[15] The first beta release, version 0.9, was made available in June 1997, marking the initial public distribution of the library and promoting open collaboration among developers to certify and refine algorithms through rigorous testing and peer review.[7] This early version laid the groundwork for CGAL's subsequent evolution into a fully open-source project.[16]Development Milestones
Following the initial funding from the ESPRIT IV CGAL project, development continued through subsequent European initiatives that expanded the library's core capabilities and research scope. The GALIA project (1998–2000) focused on advancing generic programming paradigms for geometric algorithms, building on the foundational work to enhance modularity and reusability in CGAL's design.[17] This was followed by the ECG project (2001–2004), which emphasized research in exact computational geometry, supporting refinements to predicates and kernel implementations for robust numerical handling.[18] The ACS project (2005–2008) introduced new packages for handling complex shapes, including advancements in mesh generation and optimization algorithms.[19] Concurrently, the Aim@Shape project (2004–2008) integrated CGAL tools for 3D shape analysis and repositories, enabling semantic modeling and retrieval of geometric objects.[19] Later, the ERC-funded GUDHI project (2014–2019) extended CGAL's applicability to higher-dimensional geometry, incorporating topological data analysis structures like simplicial complexes.[20] Licensing evolved to balance academic accessibility and commercial viability. Prior to 2003, CGAL was freely available for academic use without a formal open-source license.[21] In 2003, GeometryFactory was founded to manage commercial licensing, allowing proprietary integrations while sustaining development.[22] Open-source adoption began in November 2003 with the release of CGAL under the GPL and LGPL, enabling broader community contributions.[23] This dual-licensing model was formalized thereafter, with GeometryFactory handling commercial agreements alongside the free licenses.[24] Major releases marked significant architectural and standardization milestones. Versions 3.x, released prior to 2012, operated under the QPL for most packages and LGPL for core components, emphasizing stability in 2D and 3D primitives.[23] CGAL 4.0 (2012) transitioned to GPL v3 and LGPL v3, introducing unified licensing and enhancements like improved 3D mesh processing.[25] Version 5.0 (late 2019) adopted a header-only structure for easier integration and required C++14 compliance, alongside new support for periodic meshes.[26] CGAL 6.0 (2024) mandated C++17, adding advanced optimization packages and better parallelism.[27] The subsequent 6.1 release (October 2025) incorporated compiler updates for enhanced portability across modern toolchains.[7] In 2023, the CGAL project received the SoCG Test of Time Award for its enduring contributions to geometric computing, recognizing its impact on algorithms and software reliability over nearly three decades.[28] Governance involves an editorial board of 13 members as of 2013, overseeing package reviews and quality assurance, supported by over 30 developers and reviewers.[29] Open contribution rules were published in 2005 to standardize submissions, ensuring rigorous testing and documentation for new algorithms.[21]Design and Architecture
Core Components
CGAL employs a generic programming model based on C++ templates and concepts to achieve flexibility and reusability in its algorithms and data structures. This paradigm allows components to be parameterized by user-provided types that satisfy specific concept requirements, such as the Kernel model, which defines traits for fundamental geometric entities like points, vectors, and predicates. By leveraging traits classes, CGAL enables the adaptation of its core functionality to various number types and representations without altering the underlying code, promoting interoperability with the Standard Template Library (STL).[30][17] At the heart of CGAL's architecture is the kernel system, which provides an abstraction for geometric computations and serves as the foundational layer for higher-level packages. Kernels are interchangeable models of the Kernel concept, including Simple_cartesian for efficient but non-robust computations using floating-point types like double, and Exact_predicates_inexact_constructions_kernel for robust predicate evaluations with inexact constructions. These kernels support exact arithmetic through integration with external libraries such as GMP for multiprecision integers and rationals, and MPFR for floating-point arithmetic, allowing users to select appropriate trade-offs between speed and precision. The kernel handles representations of geometric objects, including points, segments, triangles, and affine transformations like translations and rotations, while providing predicates for orientation, intersection detection, and distance computations.[31][32] To ensure robustness in geometric algorithms, CGAL incorporates certified mechanisms that mitigate floating-point errors, particularly in handling degeneracies where points are collinear or coplanar. Exact predicates, computed using algebraic number types from GMP/MPFR, guarantee correct decision-making in such cases, while constructions often rely on approximate arithmetic for performance. Filtered predicates, such as those using Interval_nt for interval arithmetic, implement lazy exactness by first applying fast floating-point approximations and resorting to exact computations only when the result is uncertain, thus balancing efficiency and reliability. This approach enables certified algorithms that produce topologically correct outputs without sacrificing computational speed in non-degenerate scenarios.[33][34] Since version 4.0, CGAL has integrated with Boost for utility components like graph algorithms and property maps, enhancing its generic programming capabilities, and with Eigen for linear algebra operations, providing efficient matrix and vector handling as a replacement for deprecated alternatives. These dependencies extend the kernel's functionality, allowing seamless use of advanced numerical methods within geometric contexts while maintaining the library's modular design.[25][9]Data Structures and Algorithms
CGAL provides a variety of robust data structures for representing geometric entities, including arrangements for planar maps, which are implemented in the 2D Arrangements package as a framework for constructing and querying subdivisions of the plane induced by curves.[35] These arrangements support operations like point location and zone computation, leveraging halfedge data structures to maintain topological relations efficiently.[35] Search structures such as AABB trees, available in the 2D and 3D Fast Intersection and Distance Computation package, enable efficient intersection and distance queries on static sets of geometric objects in 2D and 3D, with bounding volume hierarchies optimized for ray shooting and proximity computations.[36] Similarly, KD-trees in the dD Spatial Searching package facilitate range searching and nearest neighbor queries in arbitrary dimensions, using a balanced binary space partition tree constructed via median splitting for logarithmic query times on average.[37] For meshes, the 3D Polyhedral Surface package offers a halfedge data structure to represent orientable 2-manifolds, including polyhedra with boundaries or holes, where vertices, edges, and facets are linked through incidence relations to support Euler operations and topological queries.[38] In terms of algorithms, CGAL includes optimization techniques such as computing the Euclidean minimum spanning tree on a point set, achieved by interfacing triangulation data structures with the Boost Graph Library and applying Kruskal's algorithm to the Delaunay triangulation graph, which ensures a tree connecting all points with minimal total edge length.[14] Boolean operations on polygons and solids are handled through arrangement-based methods; for 2D polygons bounded by x-monotone curves, the 2D Regularized Boolean Set-Operations package constructs a planar arrangement using a sweep-line algorithm to compute intersections, unions, differences, and complements, extracting results as polygons with holes in optimal time for sparse inputs.[39] In 3D, Boolean operations on Nef polyhedra employ cell-complex representations bounded by halfspaces, supporting topological queries alongside set operations via sweep-line variants. CGAL's frameworks extend to spatial sorting, implemented in the Spatial Sorting package to order points in 2D, 3D, or higher dimensions using lexicographic sorting or Hilbert curve traversals, which preserve locality to accelerate incremental constructions like triangulations by reducing expected insertion times.[40] For dynamic scenarios involving moving objects, kinetic data structures in the Kinetic Data Structures package maintain combinatorial structures such as Delaunay triangulations under continuous motion, employing exact event handling through an algebraic kernel to process certificates and updates with provable failure rates bounded by simulation parameters. Performance characteristics highlight CGAL's efficiency, with 2D convex hull computations achieving O(n log n) worst-case time using algorithms like Akl-Toussaint or Graham-Andrew scans on point sets.[41] Select packages support parallelization via Intel Threading Building Blocks (TBB), such as in 3D triangulations where multi-core insertion and location operations scale with thread count for large inputs.[42] A representative example is the 2D Delaunay triangulation, constructed incrementally in the 2D Triangulations package by inserting points and restoring the empty circumcircle property through an O(1) amortized flip algorithm per insertion, bolstered by exact predicates from the geometric kernel to ensure robustness without floating-point errors.[43]Features and Packages
2D and 3D Geometry
The CGAL library provides a suite of packages dedicated to fundamental 2D geometric computations, enabling efficient handling of triangulations, arrangements, polygons, and Voronoi diagrams. The 2D Triangulations package supports the construction and manipulation of Delaunay and regular triangulations from point sets, including features for point location queries and extraction of the dual Voronoi diagram.[44] These triangulations are built using incremental insertion algorithms that ensure conformity to the Delaunay property, with regular variants incorporating weights for applications like offset surfaces. The 2D Arrangements package constructs planar subdivisions induced by intersecting curves, accommodating general curve segments such as line segments, circular arcs, and conic sections, while supporting operations like point location and overlay of multiple arrangements.[35] For polygons, the 2D Polygons package offers a robust representation with operations including Boolean set operations (union, intersection, difference) on general polygons with holes, leveraging arrangement-based computations for exact results. Additionally, polygon offsetting is handled via the 2D Straight Skeleton and Polygon Offsetting package, which computes inward or outward offsets using straight skeleton constructions to manage self-intersections and produce valid offset polygons.[45] The 2D Voronoi Diagrams are addressed through specialized graphs: power diagrams emerge as duals to regular triangulations, partitioning the plane based on additive weights, while Apollonius diagrams (additively weighted Voronoi for disks) are computed via the 2D Apollonius Graphs package, supporting nearest-neighbor queries among circles of varying radii.[46][44] In 3D, CGAL's packages extend these primitives to volumetric computations, focusing on triangulations, mesh generation, Boolean operations, and optimization. The 3D Triangulations package enables Delaunay and regular triangulations of 3D point sets, including periodic variants for simulations on tori, with multi-core parallelization for insertion and refinement to accelerate large-scale computations.[47] Mesh generation is facilitated by the 3D Mesh Generation and 3D Surface Mesh Generation packages, which produce isotropic simplicial meshes from polyhedral domains or implicit surfaces, employing Delaunay refinement to ensure quality metrics like element shape and size grading from input polyhedra or level sets.[48] The 3D Boolean Operations on Nef Polyhedra package supports exact constructions of cell complexes through union, intersection, and difference on polyhedral solids, maintaining topological integrity via a Nef polyhedron representation that handles non-manifold features. For optimization, the 3D Linear Programming solver, part of the broader optimization framework, computes feasible points or optima in polyhedral feasible regions defined by linear inequalities, using randomized incremental construction for efficiency. Shared across dimensions, CGAL includes alpha shapes for extracting density-based boundaries from triangulations: the 2D and 3D Alpha Shapes packages compute alpha-complexes as subcomplexes of Delaunay triangulations, filtering edges and faces based on a radius parameter to delineate concave hulls or porous structures. Convex hull computations are unified in 2D and 3D via quickhull-inspired algorithms, producing boundary facets or extreme points from point sets with O(n log n) expected time complexity, supporting both static and dynamic updates.[49][41] These packages interoperate seamlessly by relying on the core 2D and 3D Linear Geometry Kernel for predicates and constructions, and the arrangement framework for overlay operations, allowing users to combine triangulations with Boolean results or embed Voronoi edges into polygonal meshes without data conversion overhead.[50] In recent versions, CGAL 6.1 enhances 3D support with optimized parameters for mesh generation, including custom initial point sets and surface-only modes, yielding faster convergence and reduced runtime for volumetric meshing tasks.[51][48]Advanced Topics
CGAL provides advanced capabilities for geometry processing, enabling the reconstruction and refinement of surfaces from point data. The Poisson surface reconstruction package implements an algorithm that reconstructs watertight surfaces from oriented point sets by solving a Poisson equation to estimate an implicit function, whose level set forms the surface; this method is particularly effective for dense, uniformly sampled data and was introduced in CGAL 3.5. In CGAL 6.1, it was enhanced with a newPoisson_mesh_domain_3 class incorporating optimizations for improved performance.[52] Complementing this, the advancing front surface reconstruction package employs a greedy approach to grow a triangular mesh from a seed facet, advancing across the point set while optimizing local geometry; it handles unoriented points and is suitable for sparse or noisy data, added in CGAL 4.7. For surface refinement, the 3D surface subdivision methods package supports schemes such as Catmull-Clark, Loop, Doo-Sabin, and √3 subdivision, which hierarchically refine control meshes to produce smooth approximations while preserving features; these were integrated in CGAL 4.11. Additionally, the triangulated surface mesh parameterization package facilitates mapping disk-homeomorphic surfaces to a plane using techniques like As-Rigid-As-Possible and Tutte barycentric methods, aiding in texture mapping and simplification; it has been available since CGAL 3.2. A new 3D Isosurfacing package, introduced in CGAL 6.1, provides algorithms such as Marching Cubes, Topologically Correct Marching Cubes, and Dual Contouring to extract isosurfaces from scalar fields defined on volumetric grids.[53]
In point set processing, CGAL offers tools for analyzing and refining unorganized clouds of points. The point set processing package, introduced in CGAL 3.5, includes functions for outlier detection via statistical analysis of distances to nearest neighbors, removing a specified fraction of points exceeding a threshold (e.g., 5% based on average spacing).[54] Density estimation is supported through average spacing computation to the k-nearest neighbors, providing a scale measure for parameter tuning in subsequent operations. For registration, the package integrates the Iterative Closest Point (ICP) algorithm via the PointMatcher library, enabling local alignment of point sets after initial global registration with Super4PCS; this process iteratively minimizes point-to-point distances, with customizable filters for robustness to noise and outliers. In CGAL 6.1, a new function CGAL::poisson_eliminate() was added for downsampling point sets while preserving the Poisson disk sampling property.
Higher-dimensional extensions in CGAL support computations beyond 2D and 3D, focusing on simplicial complexes and hulls. The dD triangulations package models simplicial complexes as pure simplicial decompositions of point sets in arbitrary dimensions d, using a triangulation data structure that maintains connectivity and geometric embeddings; it enables Delaunay triangulations, whose dual facets define the convex hull boundaries, and was enhanced in CGAL 4.6 to replace the deprecated dD convex hulls package.[55] A new dD Fréchet Distance package, added in CGAL 6.1, computes the Fréchet distance between polygonal curves in arbitrary dimensions, useful for trajectory analysis and shape matching.[56] For arrangements, the 2D arrangements package constructs planar maps from curves and supports extensions to higher dimensions through traits classes, though full ND implementations remain limited. Convex hulls in dD are computed incrementally via the Delaunay triangulation, leveraging beneath-beyond style updates during point insertion to maintain the hull as the boundary of finite cells.
Other specialized packages address periodic and topological structures. The 3D periodic triangulations package, added in CGAL 3.5, computes Delaunay triangulations on a 3D flat torus by replicating points across periodic domains, useful for crystallography; a 2D variant followed in CGAL 4.3. In CGAL 6.1, the 2D Triangulations on Hyperbolic Surfaces package was introduced, enabling Delaunay triangulations on hyperbolic surfaces such as the Bolza surface (genus 2), extending periodic concepts to non-Euclidean geometries.[57] Topological maps are handled by the surface mesh topology package (CGAL 5.1), which computes shortest non-trivial loops and performs homotopy tests on orientable surfaces represented as simplicial complexes. Optimization over arrangements, such as shortest paths, is supported in the 2D arrangements package via sweep-line frameworks that query geodesic distances amid obstacles.
Emerging features in recent releases integrate dynamic and analytical tools. The kinetic surface reconstruction package, introduced in CGAL 6.0, employs a kinetic space partition to decompose bounding boxes into convex polyhedra guided by moving planes, facilitating dynamic simulations of evolving point sets.[58] For shape analysis, the shape detection package (enhanced post-CGAL 5.0) uses RANSAC-based methods to identify primitives like planes and spheres in point clouds, providing a foundation for machine learning pipelines through extensible region-growing and classification APIs.[59]
Despite these advances, higher-dimensional features exhibit limitations, particularly beyond 3D, where computational complexity grows exponentially—e.g., triangulating 100 points in 12D requires over 2,000 seconds and 7 GB of memory—rendering them experimental for high-d applications without specialized hardware.[60] ND arrangements lack comprehensive support, relying on 2D extensions that may not scale efficiently.[12]
Platforms and Dependencies
Supported Operating Systems and Compilers
CGAL supports a range of modern operating systems, including various distributions of Linux, macOS, and Windows (primarily through Visual Studio integration).[9] These platforms are chosen to ensure broad compatibility for computational geometry applications while maintaining performance and reliability.[51] The library is continuously tested via continuous integration on GitHub Actions across these operating systems using the specified compilers, ensuring stability for releases like 6.0 and 6.1.[9][51]| Operating System | Supported Compilers |
|---|---|
| Linux | GNU g++ 12.2.0 or later (C++17); Clang 20.1.6 or later (C++17)[9] |
| macOS | GNU g++ 12.2.0 or later (C++17); Apple Clang 12.0.5, 14.0.0, or 15.0.0 (C++17)[9] |
| Windows | GNU g++ 12.2.0 or later (C++17); MS Visual C++ 15.9, 16.10, or 17.14 (from Visual Studio 2017, 2019, or 2022) (C++17)[9] |
Installation and Build Process
CGAL can be obtained by downloading source archives, such as the tarball for version 6.1, from the official website at cgal.org or from the project's GitHub releases page.[62][63] These archives include the headers, examples, and demos necessary for setup. Alternatively, users can clone the repository from GitHub for the latest development version, though stable releases are recommended for production use.[64] Since version 5.0, CGAL operates primarily as a header-only library, allowing direct inclusion of headers in user code without compiling or linking against pre-built libraries for the core functionality.[8] This simplifies integration, as applications can simply add the include path to the CGAL headers during compilation. However, dependencies like GMP and MPFR must still be installed separately, as they are not header-only.[8] To enable header-only mode explicitly during configuration, the CMake option-DCGAL_HEADER_ONLY=ON can be used.[8]
The recommended method for building and installing CGAL from source is using CMake. After extracting the source archive, create a build directory, navigate into it, and run cmake .. to configure the project, followed by make (or nmake on Windows) to build and make install to install to the default prefix (typically /usr/local on Unix-like systems).[8] Custom installation directories can be specified via -DCMAKE_INSTALL_PREFIX=/path/to/install. CMake supports optional components, such as Qt for visualization packages, by enabling flags like -DCGAL_Qt6=ON after installing Qt.[8] For header-only usage, the configuration step sets up the necessary includes without building libraries.[8]
Platform-specific setups vary for ease of installation. On Linux distributions like Ubuntu, CGAL and its dependencies can be installed via package managers using sudo apt install libcgal-dev, which handles GMP, MPFR, and Boost automatically.[65] For macOS, Homebrew provides a straightforward option with brew install cgal, ensuring compatibility with the system's compilers.[65] On Windows, the Vcpkg package manager is advised: after installing Vcpkg, run vcpkg install cgal to fetch CGAL along with dependencies like GMP and Boost, supporting Visual Studio versions 2017, 2019, and 2022.[66] Manual builds on Windows involve extracting the source, installing precompiled GMP/MPFR from CGAL releases, and configuring with CMake for Visual Studio.[66]
The distribution includes demos and examples to verify the installation, located in dedicated directories within the source archive. These can be built using the provided CMakeLists.txt files by running cmake . followed by make in the respective directory, such as examples/Triangulation_2.[8] Enabling all examples during the main build requires -DWITH_examples=ON in CMake configuration.[8] Demos often require additional optional dependencies like Qt or VTK, which must be installed beforehand.[8]
Common troubleshooting issues arise from missing dependencies, particularly GMP and MPFR. If CMake reports "Could NOT find GMP," users should install these libraries via package managers or set paths manually using variables like -DGMP_INCLUDE_DIR=/path/to/gmp/include and -DGMP_LIBRARIES=/path/to/libgmp.so during configuration.[67] For Boost-related errors, specify -DBoost_DIR=/path/to/boost/lib/cmake/Boost-1.XX.X.[67] To prevent CGAL from overriding user-defined compiler flags (e.g., in mixed setups), set -DCGAL_DONT_OVERRIDE_CMAKE_FLAGS=ON.[8] On Windows, ensure DLLs like gmp.dll are in the system PATH to avoid runtime errors.[66]