Home

About CGAL TAU Python Bindings

This repository contains software for binding CGAL TAU components (written in C++) with Python. It also contains examples, tests, and benchmarks.

We have compared three different products to create Python bindings, namely:

1. Boost.Python
2. Pybind11
3. Swig

We have concluded that Boost.Python has an advantage over its rivals. Swig uses a proprietary dedicated language to describe the bindings. It supports bindings to many scripting languages. However, this profusion is not an advantage for us, as we are only interested in Python. Pybind11 and Boost Python use C++ generic programming to describe the bindings. They have the same interface. While Pybind11 exploits more generic-programming features, it is less efficient space- and time- wise. Pybind11 is headers only, and does not depend on anything, while Boost Python depends on, well, Boost. However, CGAL already depends on Boost; thus, this dependency cannot be lifted anyway.

Installing

Naturally, you need to install Python and CGAL before attempting to use the bindings.

Python & Pip

We use Python 3.8 or a higher version.

Ubuntu

If Python 3.8 is the default version for your Ubuntu distribution, proceed to install Python via the standard apt installation procedure. Otherwise, jump to install Python from a PPA.

Install Python via apt-get

Install Pip once via a dedicated procedure and then upgrade via Pip. Install Python modules via Pip.

#!bash

# Install Python 3
> sudo apt update
> sudo apt install -y python3 python3-dev
# Verify
> python3 --version
# Set up your system to build binary Python packages
# Install Pip
> curl -LO https://bootstrap.pypa.io/get-pip.py
> python3 get-pip.py --user
# Upgrade (not really necessary---already up-to-date)
> pip3 install -U pip --user
# Verify
> pip3 --version
> which pip3
# Install popular Python packages
> pip3 install --user numpy
> pip3 install --user pipenv
> pip3 install --user pytest
> pip3 install --user pybind11

Install Python 3.8 via PPA

#!bash

> add-apt-repository ppa:deadsnakes/ppa
> sudo apt update
> sudo apt install -y python3.8 python3.8-dev
> curl -LO https://bootstrap.pypa.io/get-pip.py
> python3.8 get-pip.py
> pip3.8 install -U pip
> pip3.8 install --user numpy
> pip3.8 install --user pipenv
> pip3.8 install --user pytest
> pip3.8 install --user pybind11

Boost

As mentioned above Boost is a dependency of CGAL. When you install CGAL, it is recommended installing all Boost components. If not installed already though, install the Python component python38.

Ubuntu

Python bindings requires Boost version 1.73 or higher. If Boost 1.73 or higher is the default version of you Ubuntu distribution, proceed to install Boost via the standard apt-get installation procedure. Otherwise, jump to install Boost from sources.

Install Boost via apt

#!bash

> sudo apt install libboost-all-dev

Install Boost From Sources

The following installs version 1.72 to /usr/local. While only the Boost libraries bellow are required, it is recommended that you install all.

#!bash

# Install Boost
> mkdir -p ~/tmp/src/boost
> cd ~/tmp/src
> curl -SL boost_1_73_0.tar.gz https://sourceforge.net/projects/boost/files/boost/1.73.0/boost_1_73_0.tar.gz | tar -xzC boost
> cd ~/tmp/src/boost/boost_1_73_0
> ./bootstrap.sh --with-python=python3.7 --with-python-version=3.7
> ./b2 --with=all -j4
# Install to /usr/local
> sudo ./b2 install
# Clean
> rm -rf ~/tmp/src/boost

Pybind11

Pybind11 is used only by the benchmark to compare the performance of the various binding methods. It is not needed if you are only interested in the CGAL bindings themselves. Pybind11 is a header-only product.

The PYBIND11_DIR environment variable is used by the CMakeLists.txt file to build the Pybind11 bindings.

#!bash

# Obtain the pybind11 sources
> git clone https://github.com/pybind/pybind11.git
# Set the PYBIND11_DIR  environment variable to point at the header directory
> export PYBIND11_DIR <pybind11-root-directory>/include

cmake

cmake is used to build CGAL and applications that depends on CGAL. The minimun required version is 3.7.

Ubuntu

If cmake 3.7 or higher is the default version of you Ubuntu distribution, proceed to install cmake via the standard apt-get installation procedure. Otherwise, jump to install cmake from sources.

Install cmake via apt

#!bash

# RUN 
> sudo apt install -y cmake

Install cmake from sources

#!bash

> mkdir -p ~/tmp/src/cmake
> cd ~/tmp/src
# Download
> curl -SL https://github.com/Kitware/CMake/releases/download/v3.13.2/cmake-3.13.2.tar.gz | tar -xzC cmake
> cd ~/tmp/src/cmake/cmake/cmake-3.13.2
# Build
> ./configure
> make install
# Clean
> rm -rf ~/tmp/src/cmake

CGAL Bindings

The CGAL library is huge. It consists of many function and class templates. It follows the generic programming paradigm, which implies that many decisions the programmer has to take are resolved during compile time. Bindings occur at run time, and the C++ objects that are bound, must be known ahead. Specifically, they must be instances (instantiated types) of C++ function and class templates. This makes the set of potential objects to bind enormous. Our objective is to enable bindings, of a great portion of this set, concurrently in a convenient way. With our system it is possible to generate, for example, a single library that contains bindings for an instance of the 2D arrangement class template and an instance of the 2D triangulation class template. If several instances of the same template must be bound, several corresponding libraries must be generated. By default, the name of the generated library is CGALPY.so. However, the user can override the name with a string that maps to the set of bound instances. This is useful when more then one instance of the same template must be bound. Each execution of cmake followed by make generates a single library.

The CGAL library consists of several packages. We use the same partition and refer to each package as a module. Each module has a long (and meaningful) name and a short name; see the list of modules supported so far below. Each module is associated with a cmake Boolean flag that determines whether to generate bindings for that particular module. Each module may be associated with zero or more additional flags that indicate selections for bindings within the module. For example, the long name of the 2D Arrangement module is ARRANGEMENT_2; its short name is ARR2; the Boolean flag that indicates whether to generate bindings for this module is CGALPY_ARRANGEMENT_2_BINDINGS. This module is associated with the Boolean flag CGALPY_ARR2_POINT_LOCATION_BINDINGSthat indicates whether to generate bindings for point location of 2D Arrangements package. This module has also a string flagCGALPY_ARR2_GEOMETRY_TRAITS_NAMEthat indicates the geometry traits used to instantiate theArrangement_2<>` class template.

The Python attribute name of a bound entity of every module are gathered in a distinct Python scope to prevent name conflicts. The name of the scope is the short name of the module in lower-case except for the first letter (which is in upper-case); for example, the scope names of the bound types and free functions of the 2D Arrangement and the 3D Triangulation packages are Arr2 and Tri3, respectively. Each of these two scopes, for example, have the attribute Vertex_handle (i.e., Arr2.Vertex and Tri3.Vertex).

As mentioned above, the cmake flag CGALPY_FIXED_LIBRARY_NAME determines whether the name of the generated library is CGALPY.so or not. If not, it has the suffix CGALPY_ followed by as many as substrings as modules, the bindings of which are enabled, separated by an underscore (_). Each such substring starts with the short name of the module in lower case followed by strings that maps to the selections for bindings within the module. Each such string is a single word that starts with a capital letter. For example, the name CGALPY_kernelEpecInt_Arr2SegPlainPl of a generated library, names a library that contains bindings for (i) the Exact-Predicate-Exact-Construction (EPEC) kernel module and intersections, and (ii) the 2D Arrangement module, where the Arrangement_2<> class template is instantiated with a traits class that handles segments and a plain DCEL, and point location queries.

Module	Name	Short Name
2D and 3D Kernel	KERNEL	KER
dD Geometry Kernel	KERNEL_D	KERD
2D Arrangements on Surfaces	ARRANGEMENT_2	ARR2
2D Alpha shapes	ALPHA_SHAPE_2	AS2
3D Alpha shapes	ALPHA_SHAPE_3	AS3
2D Regularized Boolean operations	BOOLEAN_SET_OPERATIONS_2	BSO2
Bounding Volumes	BOUNDING_VOLUMES	BV
2D Convex hulls	CONVEX_HULL_2	CH2
3D Convex hulls	CONVEX_HULL_3	CH3
2D Polygons	POLYGON_2	POL2
Polygon partitioning	POLYGON_PARTITIONING	PP
2D Minkowski sums	MINKOWSKI_SUM_2	MS2
Spatial searching	SPATIAL_SEARCHING	SS
2D Triangulations	TRIANGULATION_2	TRI2
3D Triangulations	TRIANGULATION_3	TRI3

The generated library is dynamically linked—it must be so. However, the library itself can be compiled of either static or dynamic (dependent) libraries. If you intend to generate and use just a single library that contains the bindings, you have the freedom to choose between generating a library compiled of static libraries or dynamic libraries. However, if you intend to generate and use several libraries in a single Python module, it is recommended that you use libraries compiled of dynamic libraries. (Otherwise, different generated libraries might be compiled of conflicting static libraries.) The cmake flag CGALPY_USE_SHARED_LIBS indicates whether the generated library is compiled of static or dynamic libraries; it is true by default.

The content of the library and its name are governed by flags provided to cmake. The number of flags is already large, and it is expected to grow in the future. All flags have the prefix CGALPY_. In the following tables this prefix is omitted.

General arguments

Name	Type	Default	Description
USE_SHARED_LIBS	Boolean	true	Determines whether to compile shared libraries
BUILD_SHARED_LIBS	Boolean	true	Determines whether to generate shared libraries
FIXED_LIBRARY_NAME	Boolean	true	Determines whether the library name is fixed 'cgalpy.so' or set based on other selections

Binding selection

Name	Type	Default	Description
KERNEL_BINDINGS	Boolean	true	Determines whether to generate bindings for 2D and 3D Kernel types
KERNEL_D_BINDINGS	Boolean	false	Determines whether to generate bindings for dD Kernel types
ARRANGEMENT_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D arrangement instances
ALPHA_SHAPE_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D Alpha shape instances
ALPHA_SHAPE_3_BINDINGS	Boolean	false	Determines whether to generate bindings for 3D Alpha shape instances
BOOLEAN_SET_OPERATIONS_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D Boolean set operation instances
BOUNDING_VOLUMES_BINDINGS	Boolean	false	Determines whether to generate bindings for bounding volume instances
CONVEX_HULL_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D convex hull instances
CONVEX_HULL_3_BINDINGS	Boolean	false	Determines whether to generate bindings for 3D convex hull instances
POLYGON_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D polygon instances
POLYGON_PARTITIONING_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D polygon partitioning instances
MINKOWSKI_SUM_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D Minkowski sum instances
SPATIAL_SEARCHING_BINDINGS	Boolean	false	Determines whether to generate bindings for spatial searching instances
TRIANGULATION_2_BINDINGS	Boolean	false	Determines whether to generate bindings for 2D triangulation instances
TRIANGULATION_3_BINDINGS	Boolean	false	Determines whether to generate bindings for 3D triangulation instances

Kernel module flags

Name	Type	Default	Description
KERNEL_NAME	String	epic	The kernel used, e.g., epic, epec, or epecws
KERNEL_INTERSECTION_BINDINGS	Boolean	true	Determines whether to generate bindings for intersections

Kernel name options

KERNEL_NAME	Predefined Type
epic	Exact_predicates_inexact_constructions_kernel
epec	Exact_predicates_exact_constructions_kernel
epecws	Exact_predicates_exact_constructions_kernel_with_sqrt
filteredSimpleCartesianDouble	NT = double
^^	Filtered_kernel <Simple_cartesian<NT>>
filteredSimpleCartesianLazyGmpq	NT = Lazy_exact_nt<Gmpq>
^^	Filtered_kernel <Simple_cartesian<NT>>

dD Geometry Kernel module flags

2D Arrangement module flags

Name	Type	Default	Description
ARR2_GEOMETRY_TRAITS_NAME	String	segment	The geometry traits of a 2D arrangement. Options are: linear, segment, nonCachingSegment, conic, algebraic, or circleSegment
ARR2_DCEL_NAME	String	allExtended	The DCEL of a 2D arrangement. Options are: plain, faceExtended, halfedgeExtended, vertexExtended, allExtended
ARR2_POINT_LOCATION_BINDINGS	Boolean	true	Determines whether to generate bindings for point location and vertical ray shoot queries

3D Triangulation Arguments

Name	Type	Default	Description
TRI3_NAME	String	regular	The 3D triangulation type; options are: plain, regular, delaunay, or periodic3Delaunay
TRI3_VERTEX_BASE_NAME	String	plain	Options are: plain, plainWithInfo, regular, regualrWithInfo alphaShape, alphaShapeWithInfo, alphaShapeRegular, alphaShapeRegularWithInfo, fixedAlphaShape, fixedAlphaShapeWithInfo, fixedAlphaShapeRegular, or fixedAlphaShapeRegularWithInfo
TRI3_CELL_BASE_NAME	String	plain	Options are: plain, plainWithInfo, regular, regualrWithInfo alphaShape, alphaShapeWithInfo, alphaShapeRegular, alphaShapeRegularWithInfo, fixedAlphaShape, fixedAlphaShapeWithInfo, fixedAlphaShapeRegular, or fixedAlphaShapeRegularWithInfo
TRI3_TRAITS_NAME	String	kernel	The geometry traits of a 2D triangulation, either kernel or periodic3Delaunay
TRI3_CONCURRENCY_NAME	String	sequential	The concurrency method, either sequential or parallel
TRI3_LOCATION_POLICY_NAME	String	compact	The location policy, either fast or compact

3D Alpha Shape Arguments

Name	Type	Default	Description
AS3_NAME	String	plain	The 3D Alpha shape type, either plain or fixed
AS3_EXACT_COMPARISON	Boolean	false	Determines whether to apply exact comparisons

Spatial Searching Arguments

Name	Type	Default	Description
SPATIAL_SEARCHING_DIMENSION	Integer	2	The dimension of spatial searching related classes

Benchmarks

Tests