Home

• User guide
  • Installing
  • CGAL Bindings
  • Benching

User Guide

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

Let's say that you would like to generate bindings for the 2D/3D Kernel and 2D Arrangements packages, and in particular for the following:

• Kernel, and
• CGAL::Arrangement<GeometryTraits, Dcel>

where,

• Kernel is CGAL::Exact_predicate_exact_construction_kernel,
• GeometryTraits is CGAL::Arr_segment_traits_2<Kernel>, and
• Dcel is the default 'DCEL.

If you install CGAL from sources, set the environment variable CGAL_DIR to point at the root directory of CGAL. Let the environment variable <CGALPY_DIR> point at the root of the local clone. Create a build directory and go there. Assuming you have all dependencies install, type:

cmake -C <CGALPY_DIR>/cmake/tests/release/aos2_epec_fixed_release.cmake <CGALPY_DIR>
make -j4
pip3 install --user src/libs/cgalpy/dist/CGALPY-1.0-py3-none-any.whl

Then, you should be able to execute the program <CGALPY_DIR>/src/python_scripts/cgalpy_examples/aos2.py.

At some point you will need bindings for additional instances (I assume); see Section CGAL Bindings for the relevant instructions.

If you are a developer and would like to build the cpp documentation, type:

make CGALPY_CPP_DOC

If you would like to build the Python documentation, type:

make CGALPY_DOC

The Python html manual pages are generated under src/libs/cgalpy/CGALPY/build/html/. The pdf single file is generated under src/libs/cgalpy/CGALPY/build/latex/.

Observe that the CGALPY prefix in the target of the above make is the binding library based name; this name can be different then CGALPY, and depends on your selections; see Section CGAL Bindings.

If you would like to build the documentation for both, type:

make doc

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
> pip3 install --user build
> pip3 install --user sphinx
> pip3 install --user sphinx_rtd_theme

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
> pip3.8 install --user build
> pip3.8 install --user sphinx
> pip3.8 install --user sphinx_rtd_theme

Boost

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.73 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

Doxygen

Ubuntu

By default the cpp documentation is generated by doxygen, which in turn optionally depends on dot provided by graphviz. The documentation is generated as html pages and as a single pdf file from latex sources.

#!bash

> sudo apt install graphviz doxygen

latex

Ubuntu

To install Tex Live LaTeX distribution use the following command.

#!bash

> sudo apt install texlive-full  

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

Name	Type	Default	Description
KERNEL_D_NAME	String	epicd	The kernel type used
KERNEL_D_DIMENSION_TAG	String	dynamic	Determines whether the dimension is dynamic
KERNEL_D_DIMENSION	Integer	2	The dimension of the ambient Euclidean space

d-dimensional Kernel name options

KERNEL_D_NAME	Predefined Type
epicd	Epick_d<DimensionTag>
epecd	Epeck_d<DimensionTag>
cartesiandDouble	Cartesian_d<double>
cartesiandLazyGmpq	Cartesian_d<Lazy_exact_nt<Gmpq>>

d-dimensional Kernel dimension tag options

KERNEL_D_DIMENSION_TAG	Predefined Type
static	Dimension_tag<d>
dynamic	Dynamic_dimension_tag

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
AOS2_EXTEND_VERTEX	Boolean	false	Determines whether to extend the vertex type
AOS2_EXTEND_HALFEDGE	Boolean	false	Determines whether to extend the halfedge type
AOS2_EXTEND_FACE	Boolean	false	Determines whether to extend the face type
ARR2_POINT_LOCATION_BINDINGS	Boolean	true	Determines whether to generate bindings for point location and vertical ray shoot queries

2D arrangement geometry traits options

AOS2_GEOMETRY_TRAITS_NAME	Type
nonCachingSegment	Arr_non_caching_segment_basic_traits_2<Kernel>
segment	Arr_segment_traits_2<Kernel>
linear	Arr_linear_traits_2<Kernel>
conic	Arr_conic_traits_2<RatKernel , AlgKernel , NtTraits>
circleSegment	Arr_circle_segment_traits_2<Kernel>
algebraic	Arr_algebraic_segment_traits_2<Coefficient>

2D Triangulations module flags

Name	Type	Default	Description
TRI2_NAME	String	plain	The 2D triangulation type
TRI2_VERTEX_WITH_INFO	Boolean	false	Determines whether the vertex type is extended
TRI2_FACE_WITH_INFO	Boolean	false	Determines whether the face type is extended
TRI2_INTERSECTION_TAG_NAME	String	ncirc	The intersection tag
TRI2_HIERARCHY	Boolean	false	Determines whether to generate the binding for
a hierarchy triangulation

2D triangulation name options

TRI2_NAME	Type
plain	Triangulation_2<Traits , Tds>
regular	Regular_triangulation_2<Traits , Tds>
delaunay	Delaunay_triangulation_2<Traits , Tds>
constrained	Constrained_triangulation_2<Traits , Tds , Itag>
constrainedDelaunay	Constrained_Delaunay_triangulation_2<Traits , Tds , Itag>
periodicPlain	Periodic_2_triangulation_2<Traits , Tds>
periodicDelaunay	Periodic_2_Delaunay_triangulation_2<Traits , Tds>

2D Alpha Shapes module flags

Name	Type	Default	Description
AS2_EXACT_COMPARISON	Boolean	false	Determines whether to apply exact comparisons

3D Triangulation module flags

Name	Type	Default	Description
TRI3_NAME	String	regular	The 3D triangulation type; options are: plain, regular, delaunay, 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
TRI3_HIERARCHY	Boolean	false	Determines whether to generate the binding for a hierarchy triangulation

3D triangulation name options

TRI3_NAME	Type
plain	Triangulation_3<Traits , Tds , Slds>
regular	Regular_triangulation_3<Traits , Tds , Slds>
delaunay	Delaunay_triangulation_3<Traits , Tds , LocationPolicy , Slds>
periodicPlain	Periodic_3_triangulation_3<Traits , Tds>
periodicRegular	Periodic_3_regular_triangulation_3<Traits , Tds>
periodicDelaunay	Periodic_3_Delaunay_triangulation_3<Traits , Tds>

3D triangulation concurrency options

TRI3_CONCURRENCY_NAME	Type
sequential	Sequential_tag
parallel	Parallel_tag

3D triangulation location policy options

TRI3_LOCATION_POLICY_NAME	Type
fast	Fast_location
compact	Compact_location

3D Alpha Shape module flags

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

3D Alpha Shapes types

AS3_NAME	Type
plain	Alpha_shape_3<>
fixed	Fixed_alpha_shape_3<>

Spatial Searching Arguments

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

Benchmarking

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.

Tests