The Computational Geometry Algorithms Library (CGAL) is an open source software

library A library is a collection of Book, books, and possibly other Document, materials and Media (communication), media, that is accessible for use by its members and members of allied institutions. Libraries provide physical (hard copies) or electron ...

of computational geometry

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s. While primarily written in C++,

Scilab Scilab is a free and open-source, cross-platform numerical computational package and a high-level, numerically oriented programming language. It can be used for signal processing, statistical analysis, image enhancement, fluid dynamics simul ...

bindings and bindings generated with

SWIG The Simplified Wrapper and Interface Generator (SWIG) is an open-source software tool used to connect computer programs or libraries written in C or C++ with scripting languages such as Lua, Perl, PHP, Python, R, Ruby, Tcl, and other lang ...

(supporting Python and

Java Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...

for now) are also available. The software is available under dual licensing scheme. When used for other open source software, it is available under open source licenses (

LGPL The GNU Lesser General Public License (LGPL) is a free-software license published by the Free Software Foundation (FSF). The license allows developers and companies to use and integrate a software component released under the LGPL into their own ...

or GPL depending on the component). In other cases commercial license may be purchased, under different options for academic/research and industrial customers.

History

The CGAL project was founded in 1996, as a consortium of eight research institutions in Europe and Israel:

Utrecht University Utrecht University (UU; , formerly ''Rijksuniversiteit Utrecht'') is a public university, public research university in Utrecht, Netherlands. Established , it is one of the oldest universities in the Netherlands. In 2023, it had an enrollment of ...

ETH Zurich ETH Zurich (; ) is a public university in Zurich, Switzerland. Founded in 1854 with the stated mission to educate engineers and scientists, the university focuses primarily on science, technology, engineering, and mathematics. ETH Zurich ran ...

Free University of Berlin The Free University of Berlin (, often abbreviated as FU Berlin or simply FU) is a public university, public research university in Berlin, Germany. It was founded in West Berlin in 1948 with American support during the early Cold War period a ...

INRIA The National Institute for Research in Digital Science and Technology (Inria) () is a French national research institution focusing on computer science and applied mathematics. It was created under the name French Institute for Research in Comp ...

Sophia Antipolis, Martin-Luther-University Halle-Wittenberg,

Max Planck Institute for Informatics The Max Planck Institute for Informatics (German: ''Max-Planck-Institut für Informatik'', abbreviated ''MPI-INF'' or ''MPII'') is a research institute in computer science with a focus on algorithms and their applications in a broad sense. It host ...

Saarbrücken Saarbrücken (; Rhenish Franconian: ''Sabrigge'' ; ; ; ; ) is the capital and largest List of cities and towns in Germany, city of the state of Saarland, Germany. Saarbrücken has 181,959 inhabitants and is Saarland's administrative, commerci ...

Johannes Kepler University Linz The Johannes Kepler University Linz (German: ''Johannes Kepler Universität Linz'', short: ''JKU'') is a public university in Austria. It is located in Linz, the capital of Upper Austria. It offers bachelor's, master's, diploma and doctoral degre ...

, and

Tel-Aviv University Tel Aviv University (TAU) is a Public university, public research university in Tel Aviv, Israel. With over 30,000 students, it is the largest university in the country. Located in northwest Tel Aviv, the university is the center of teaching and ...

. The original funding for the project came from the ESPRIT project of the

European Union The European Union (EU) is a supranational union, supranational political union, political and economic union of Member state of the European Union, member states that are Geography of the European Union, located primarily in Europe. The u ...

. 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. it is managed by a thirteen-member editorial board, with an additional 30 developers and reviewers. The project started in 1996 as the pooling of the previous efforts of several project participants:PlaGeo and SpaGeo from

, LEDA of the Max-Planck-Institute for Informatics and C++GAL of

Sophia Antipolis. The LEDA library encompasses a broader range of algorithms. A comparison of the two libraries is provided by Kettner and Näher. Three CGAL User workshops held in 2002, 2004, and 2008 highlighted research results related to CGAL, and many additional papers related to CGAL have appeared in other conferences, workshops, and journals. In 2023 the project won the SoCG ''Test of Time Award''

Scope

The library covers the following topics: * Geometry kernels - basic geometric operations on

geometric primitive In vector computer graphics, CAD systems, and geographic information systems, a geometric primitive (or prim) is the simplest (i.e. 'atomic' or irreducible) geometric shape that the system can handle (draw, store). Sometimes the subroutines ...

s *

Arithmetic Arithmetic is an elementary branch of mathematics that deals with numerical operations like addition, subtraction, multiplication, and division. In a wider sense, it also includes exponentiation, extraction of roots, and taking logarithms. ...

and

algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

Convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

algorithms *

Polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...

s and

polyhedra In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...

* Polygon and polyhedron operations *

Arrangement In music, an arrangement is a musical adaptation of an existing composition. Differences from the original composition may include reharmonization, melodic paraphrasing, orchestration, or formal development. Arranging differs from orchestr ...

s * Point set triangulations *

Delaunay triangulation In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...

s *

Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (calle ...

s *

Mesh generation Mesh generation is the practice of creating a polygon mesh, mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric ...

Geometry processing Geometry processing is an area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, 3D reconstruction, reconstruction, analysis, manipulation, simulation and ...

* Search structures ( ''k''-d tree) * Shape analysis, fitting, and distances *

Interpolation In the mathematics, mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points. In engineering and science, one ...

Kinetic data structures Kinetic (Ancient Greek: κίνησις “kinesis”, movement or to move) may refer to: * Kinetic theory, describing a gas as particles in random motion * Kinetic energy, the energy of an object that it possesses due to its motion Art and ente ...

Platforms

The library is supported on a number of platforms:CGAL Supported Platforms
/ref> *

Microsoft Windows Windows is a Product lining, product line of Proprietary software, proprietary graphical user interface, graphical operating systems developed and marketed by Microsoft. It is grouped into families and subfamilies that cater to particular sec ...

( GNU G++,

Microsoft Visual C++ Microsoft Visual C++ (MSVC) is a compiler for the C, C++, C++/CLI and C++/CX programming languages by Microsoft. MSVC is proprietary software; it was originally a standalone product but later became a part of Visual Studio and made available i ...

Intel C++ Compiler Intel oneAPI DPC++/C++ Compiler and Intel C++ Compiler Classic (deprecated icc and icl is in Intel OneAPI HPC toolkit) are Intel’s C, C++, SYCL, and Data Parallel C++ (DPC++) compilers for Intel processor-based systems, available for Wind ...

) * GNU g++ (

Solaris Solaris is the Latin word for sun. It may refer to: Arts and entertainment Literature, television and film * ''Solaris'' (novel), a 1961 science fiction novel by Stanisław Lem ** ''Solaris'' (1968 film), directed by Boris Nirenburg ** ''Sol ...

Linux Linux ( ) is a family of open source Unix-like operating systems based on the Linux kernel, an kernel (operating system), operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically package manager, pac ...

Mac OS Mac operating systems were developed by Apple Inc. in a succession of two major series. In 1984, Apple debuted the operating system that is now known as the classic Mac OS with its release of the original Macintosh System Software. The system ...

) *

Clang Clang () is a compiler front end for the programming languages C, C++, Objective-C, Objective-C++, and the software frameworks OpenMP, OpenCL, RenderScript, CUDA, SYCL, and HIP. It acts as a drop-in replacement for the GNU Compiler ...

The CGAL library depends on the

Boost libraries Boost is a set of library (computing), libraries for the C++ programming language that provides support for tasks and structures such as linear algebra, pseudorandom number generator, pseudorandom number generation, multithreading, image proces ...

, and several CGAL packages on the Eigen C++ library.

References

{{Reflist

External links

CGAL Homepage
C++ libraries Geometric algorithms Free computer libraries Max Planck Institute for Informatics Python (programming language) scientific libraries

History

Scope

Platforms

See also

References

External links