Robust Geometric Computations and Visualization (for ordinary mortals)

About the CGAL-Python project.

CGAL-python [1] is a project aiming to provide bindings to the CGAL library in Python. The CGAL Open Source Project builds the Computational Geometry Algorithms C++ Library. The CGAL library provides easy access to geometric algorithms and data structures. CGAL-Python is developed at INRIA Sophia Antipolis, by Naceur Meskini.

The CGAL-Python project makes accessing the CGAL library even easier, by making the CGAL functionality available in the Python programming language. Python is often more suitable for rapid prototyping and experimentation and is often easier to learn than C++.

About this document.

The goal of this document is to serve as documentation to anyone wishing to extend the CGAL-Python project. The development of the bindings for the Polygon_2 CGAL class is outlined here, to serve as an example. Intended audience for this how-to are developers who wish to extend the CGAL-Python bindings.

This document is Copyright 2008 Spiros Evangelatos.

This document may be reproduced and distributed in whole or in part, in any medium physical or electronic, as long as this copyright notice is retained on all copies.

If you have corrections or something to add, feel free to e-mail me (grad0864 at di dot uoa dot gr).

Overview of the bindings methodology

The Boost.Python framework is used to create bindings to the CGAL classes and functions. Both Boost and CGAL make heavy use of Templates. Experience in the use of C++ templates and generic programming is not strictly required but can prove usefull in times of trouble. Further documentation on Boost.Python is available on the web [4] [5] [6] [7]. For the sake of modularity, the bindings are organized in modules. The different modules are aggregated in a single CGAL module as they are imported in python. This happens in the file cgal_package/GCAL/

Here, we have to mention that there is a Boost.Python code generator, called Pyste that one could use. Pyste generates wrappers for C++ classes automatically. The generated code though has to be manually modified, in order to clean it up and make it comply with the strategy used throughout CGAL-Python. In this how-to Pyste is not used.

Manually creating a new module

Setting up a new module.

In this guide we are going to import the Polygon_2 class. Since Polygon_2 does not conceptually fit in any of the existing CGAL-Python packages, we are going to create a new package. We will call this new package "Polygon".

First, we create a new directory named "bindings/Polygon" to accomodate the package specific files. Secondly, we modify "cgal_package/GCAL/" to include our package in the CGAL package. So now, reads:

from Polyhedron import *
from Polygon import *	#the Polygon module is included in the CGAL module
from Geometric_Optimisation import *

Now create a new makefile as "bindings/Polygon/Makefile" and copy paste the code below (make sure tabs are preserved):

#	Creates which can be imported via Python

include ../

Polygon_module = Polygon

OBJ_of_Polygon_module =  \
	Polygon_module.o \

	@echo 'Creating a Python modules'
	@g++ $(CGAL_PYTHON_LDFLAGS) $(OBJ_of_Polygon_module)  -o $(Polygon_module).so
	@echo '$(Polygon_module) module created in ./$(Polygon_module)/$(Polygon_module).so'

	@echo 'Compiling $<'

	@rm -f *.so
	@rm -f $(OBJ_of_Polygon_module) *.*~  *~ 

Remember to add any new object files that you create in the OBJ_o_Polygon_module variable. Here we start with 2 object files. The Polygon_module object, defines the new module. The Py_Polygon_2 object contains the bindings for the Polygon_2 class. Next, modify the Makefile in the base CGAL-Python directory to refer to the new module.

Creating the new module.

It is now time to write code to declare the Polygon module. This code resides in the file "bindings/Polygon/Polygon_module.cpp". The full file is available in the tree. The significant code for declaring a module are shown below.


This code declares a Polygon module, sets the error handler that CGAL classes need to call to report errors back to python and calls the export_Polygon_2() function that wil declare the Polygon_2 class. If our module contained more classes, functions that declare the rest of the classes should be called here. The export_Polygon_2() function is defined in "bindings/Polygon/Py_Polygon_2.cpp". We will examine this file in the next section.

Writing bindings for the Polygon_2 class.

The Polygon_2 file bindings reside in "bindings/Polygon/Py_Polygon_2.cpp". The point of entry for this file is the export_Polygon_2() function which is actually a wrapper of the Py_Polygon_2(); function. Py_Polygon_2 takes as a template parameter the Kernel for the Polygon class. The CGAL Polygon_2 class is exposed to Python by the following line:

class_< Polygon_2 >("Polygon_2", "Class doc", init< optional< const kernel& >  >("doc"));

This line exposes the Polygon_2 class to python under the name "Polygon_2". A constructor of the class is also exposed here, taking an optional reference of a kernel object as a parameter. Documentation strings for both the class and the extractor are provided.

If you don't wish to expose a constructor, the following line exposes the class without a constructor. Objects with no constructors cannot be instantiated in python.

class_< Polygon_2 >("Polygon_2", "Class doc", no_init);

Exposing inheritance.

Inheritance may be exposed optionally if one wishes to make python aware of it. The syntax to expose inheritance is as follows. Any base functions have to be exposed as well if one wants to be able to use the derived object as a Base object.

class_<Derived, bases<Base1,Base2> >("Derived")

Exposing member functions, additional constructors and properties.

The def() function is used to expose member functions.

class_< Polygon_2 >(...)
	.def("clear", & Polygon_2::clear, "doc for clear")

The parameter &Polygon_2::clear is a pointer to the member function clear(). Multiple overloaded versions of a member function can be exposed. To do that, you must cast the pointer to the exact type of the overloaded function.

Additional constructors can be exposed using init.
class_< Polygon_2 >("Polygon_2", "Class doc", init< optional< const kernel& >  >("doc"))
        .def(init< const Polygon_2& >("doc2"));

Attaching new functions to an object.

Sometimes we wish to expose a method but slightly modify its semantics or parameter types. Or even sometimes, we want to provide a member that does not even exist in the C++ object. You can add new methods by writing a simple C++ function, that takes a reference to the object as its first parameter. This is similar to the Python member functions that take _self_ as their first argument. You can then use def to bind a pointer to the new function with the object.


Properties can be also exposed by means of the .add_property(...) method.

Exposing functions

Regular functions can be declared in the context of a module using def [7].

    def("name", function_ptr, "documentation string");

More details on using Boost.Python are available on the web [4] [5] [6] [7].

Design considerations.

Python and C++ have huge differences. Sometimes it's impossible or undesirable to expose the mechanics of the C++ CGAL interface to Python. So it is sometimes inevitable that the interface has to be slightly modified, in order to "Pythonize" it. In the next chapters we will see some common problems and the proposed methodology to deal with them.

Dealing with references to primitive types as parameters.

Functions that take as parameters references to Boost.Python objects work as expected. But in CGAL there are some functions that take a reference to an int, float or string. Unfortunately, Python does not support references to such objects. In this case, one has to write a wrapper function that either works around the offending parameter, or takes a reference to a python list object that contains the offending parameter.

The CGAL-Python documentation [2] [3] provides two examples on that. First, we can work around the value if it is an index by providing a reference to the actual object, if this is appropriate. Example:

is_edge( Vertex_handle va,Vertex_handle vb,Face_handle& fr,int & i)
/* becomes */
py_is_edge(Vertex_handle va ,Vertex_handle vb, Edge& e)
If we can't work around the issue, we have to pass the reference by wrapping it in a python list as in the example below.
locate( Point query,Locate_type & lt, int & li)
/* becomes */
py_locate( Point query, boost::python::list l)
Assuming py_locate is exposed to Python as "locate", the python code to call the function would be:
locate(query, [li])

Output iterators.

To work around functions that take as parameters output iterators, we write wrapper functions that return a python list. Example [2]

boost::python::listpy_get_conflicts(constDelaunay_triangulation_2& dt,Point_2 pt) 
	typedeftypenameDelaunay_triangulation_2::Face_handle  Face_handle; 
	std::list<Face_handle>  liste;
	dt.get_conflicts(pt, std::back_inserter(liste));
	for(iter= liste.begin(); iter!= liste.end(); iter++)
	return result;

Dealing with iterators and circulators.

The header file <iterator.h> under the "include" subdirectory of the distribution provides some mechanisms to deal with iterators and circulators. The simplest of those is the simple_python_iterator class. This generic class can be used to turn a range of iterators, to a Python iterator.

For example, the Polygon class Polygon contains a list of it's edges, accessible through iterators. These can be elegantly exposed to Python through a python iterator.

template < class iterator, class Polygon>
simple_python_iterator<iterator> py_all_edges(Polygon& poly)
	std::pair<iterator, iterator> p( poly.edges_begin(), poly.edges_end());
	return  simple_python_iterator<iterator>(p);

All the polygon edges can be elegantly attached to the python object as a property...

.add_property("edges", &py_all_edges<Edge_const_iterator, Polygon_2>,
              "The edges of the polygon.")

So, the C++ interface p.edges_begin(), p.edges_end() is exposed simply as p.edges. The class simple_python_circulator provides similar functionality for circulators.

List-like interface.

The CGAL::Polygon_2 class overloads the [] operator to provide a vector-like interface in C++. This interface is efficient, provided that a random access container is used in the underlying implementation. In Python, similar functionality is available for an object by emulating a list-like interface. For a Python object to emulate a list, these methods have to be inplemented:

  • len
  • getitem to be readable.
  • setitem to be writable.
  • delitem to delete elements.

The file "bindings/Polygon/pylist_helper.h" may be usefull to implement list like interface. Polygon, allows access to the Polygon vertices. The function sanitize_py_index(...) helps to implement pythonic negative indexing and implement bounds checks.

.def("__len__", & Polygon_2::size, Polygon_2_docs::__len__)
.def("__getitem__", &pylist_helper<Polygon_2, Point_2>::get, 
	return_value_policy<copy_const_reference>(), Polygon_2_docs::__getitem__) 
.def("__setitem__", &py_set<Polygon_2, Point_2>, 
.def("__delitem__", &py_erase<Polygon_2>, Polygon_2_docs::__delitem__) 

Iterators as return types in queries.

Some object functions such as Polygon_2::top_vertex() return Vertex_iterators in order to allow the user to use the topmost vertex as a starting point or ending point to move through the vertices of the polygon. A lot of algorithms start from one of those extreme points and move through the polygon, or use them to split a polygon.

One could provide bindings for the iterator object but there are some problems with this approach. Firstly, we haven't exposed any other Vertex_iterators so far. So the user does not have access to the .vertex_end() function to know where to stop incrementing the iterator. Secondly, those iterators do not blend in well in Python code. Python iterators move only forward, whereas in this case, forward, backward and ideally random access iterators are needed. Such iterators can't be used in constructs such as the Python "for".

Instead of exposing iterators, one could provide just the index of the requested vertex in the vertice list. This can be accomplished by writing the function py_top_vertex.

template <class Polygon>
typename std::iterator_traits<typename Polygon::Vertex_iterator>::difference_type
py_top_vertex(Polygon & poly)
	return std::distance(poly.vertices_begin(), poly.top_vertex());

Canonical string representation.

It is good practice to implement the __repr__ method for the Python objects. The canonical string representation should be usable for instantiating an equivalent object. For instance, the canonical string representation for a point with coordinates (1,1) is "Point_2(1, 1)", which is a valid expression that instantiates an appropriate object.

Adding constructors.

The canonical representation of objects such as the Point_2 is easy to imlement as the constructor provided by the CGAL object, is appropriate for instantiating a new object from its canonical string representation. This is not the case for the Polygon_2 object. The object Polygon_2([Point_2(0,0), Point_2(1,0), Point_2(0,1)]) needs a constructor that takes a python iterable as parameter, or at least, a Python list. The CGAL::Polygon_2 does not provide such a constructor. We will have to implement a constructor for this and somehow make it available.

There are 2 methods to attach a new constructor to an object. The most straightforward way is to create a new class , derived from the one that you want to expose, and implement the missing constructor in the new class. The inheritance between the 2 objects should be made visible to Python in order to be able to use the derived object where the base object could be used. I consider this method, a workaround as it involves changing the object hierachy.

The second method, is to add a constructor using the make_constructor Boost.Python function [9]. According to the Boost.Python documentation "make_function() and make_constructor() are the functions used internally by def() and class_<>::def() to produce Python callable objects which wrap C++ functions and member functions.". Suppose we have a function with the signature:

boost::shared_ptr<Some_object> func (int foo);
Then this function can be injected as a constructor like this:
class_< Some_object > ("Some_object", no_init)
	.def ("__init__", make_constructor (&func)

Further documentation and references.

  1. CGAL Python Bindings project site.
  2. How to use and write bindings for CGAL-Python
  3. Developer doc in the CGAL-Python repository.
  4. Official Boost.Python documentation
  5. Building Hybrid Systems with Boost.Python
  6. Boost.Python wiki
  7. About modules in Boost.Python wiki
  8. Boost.Python How-To in Boost.Python wiki
  9. Documentation for make_function and make_constructor in Boost.Python
Spiros Evangelatos
March 2008, Athens