Personal tools
You are here: Home Projects In-house Projects CGAL Python Bindings CGAL Python Bindings
« August 2022 »
August
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
Log in


Forgot your password?
 

CGAL Python Bindings

Abstract

aos_open_concept
The open boundary cluster of the 2D Arrangement on surface geometry traits concept.

We introduce bindings that enable the convenient, efficient, and reliable use of software modules of CGAL (Computational Geometry Algorithm Library), which are written in C++, from within code written in Python. There are different tools that facilitate the creation of such bindings. We present a short study that compares three main tools, which leads to the tool of choice. The implementation of algorithms and data structures in computational geometry presents tremendous difficulties, such as obtaining robust software despite the use of (inexact) floating point arithmetic, found in standard hardware, and meticulous handling of all degenerate cases, which typically are in abundance. The code of CGAL extensively uses function and class templates in order to handle these difficulties, which implies that the programmer has to make many choices that are resolved during compile time (of the C++ modules). While bindings take effect at run time (of the Python code), the type of the C++ objects that are bound must be known when the bindings are generated, that is, when they are compiled. The types of the bound objects are instances (instantiated types) of C++ function and class templates. The number of object types that can potentially be bound, in implementation of generic computational-geometry algorithms, is enormous; thus, the generation of the bindings for all these types in advance is practically impossible. For example, the programmer needs to choose among a dozen types of curves (e.g., line segments, circular arcs, geodesic arcs on a sphere, or polycurves of any curve type) to yield a desired arrangement type; often there are several choices to make, resulting in a prohibitively large number of combinations. We present a system that rapidly generates bindings for desired object types according to user prescriptions, which enables the convenient use of any subset of bound object types concurrently. After many years, in which the usage of these packages was restricted to C++ experts, the introduction of the bindings made them easily accessible to newcomers and practitioners in non-computing fields, as we report in the paper.

Concepts-Binding Coupling

Generic programming enables the implementation of generic algorithms, which work on collections of different types, can be easily maintained, extended, and customized, and are type safe and easier to read. As mentioned in the introduction, CGAL rigorously adheres to the generic programming paradigm. As a consequence, most components of CGAL are either class or function templates. Many of the parameters of these templates are described in terms of models of concepts. When a class or a function template is instantiated, each one of its template parameters is substituted with a model of one or more concepts associated with the template parameter. Close to~750 concepts can be identified in CGAL at the time this article is written. Most hierarchy graphs of concepts are small. Few graphs, such as the graph of concepts of the geometry traits of the 2D Arrangements on Surfaces package, are quite large with intricate refinement relations. We use clusters of closely related concepts to describe the refinement relations among them; see, e.g., the open-boundary cluster of the 2D Arrangement on Surface traits concept in the figure above. We have introduced tight coupling between concepts and (i) binding generations and (ii) type annotation.

Links

Contact

Nir Goren http://acg.cs.tau.ac.il/people/nir-goren/nir-goren null
Efi Fogel http://acg.cs.tau.ac.il/people/efifogel null
Dan Halperin http://acg.cs.tau.ac.il/danhalperin null
Document Actions