matplotlib/matplotlib — pull request #2504 by ianthomas23 (2013-10-08 22:04:23+00:00)
Title: Using qhull for Delaunay triangulation

This PR adds (some of) the Qhull library to matplotlib to perform Delaunay triangulation. Currently Delaunay triangulations are performed by the matplotlib.delaunay module, but this is not particularly robust. Qhull is much more robust, is open-source, and is used in many other projects including scipy.spatial, octave and matlab.

The qhull source code and license file are in `extern/qhull/`, and the Python/C wrapper in `src/qhull_wrap.c`. The setup scripts attempt to build the qhull extension in three ways (as other extensions): (1) using system-installed version via pkg-config, (2) using system-installed version without pkg-config, (3) using the local version in `extern/qhull`. I've tested all three methods using python 2 and 3 on linux, but not macos or windows as I don't use them. Any help here would be appreciated - you can confirm that everything is OK by running `test_triangulation` and `test_mlab`.

Qhull is used as a single atomic operation, i.e. when a triangulation is needed qhull is started up, the triangulation is calculated and returned, then qhull is closed down. There is no storage of qhull objects in memory in case they are needed later.

I've deprecated the matplotlib.delaunay module for future removal. Note to self: when it is time to remove it, the following need to be deleted: `lib/matplotlib/delaunay`, `lib/matplotlib/tests/test_delaunay` and `lib/matplotlib/tests/baseline_images/test_delaunay`, and the following modified: `setup.py` and `setupext.py`.

The delaunay code is used by `matplotlib.tri.Triangulation`, and hence by all of the `pyplot.tri*` functions. It is also used by `mlab.griddata`. I don't think that `matplotlib.delaunay` was specifically intended to be used directly by users, but it has been. This will now be harder to do which is by intent. I will be encouraging everyone to access the delaunay functionality via `matplotlib.tri.Triangulation` as this provides a standard interface, does consistency and error checking, and can be passed to any of the `pyplot.tri*` functions for plotting.

The PR is in two commits for easier review; the first is the addition of the qhull files, and the second contains my changes. I have added a number of new tests, in particular cases that used to fail using `matplotlib.delaunay` but now pass OK.

There are two decisions I have made that others may wish to question/alter:

(1) qhull expects a valid FILE* for writing errors to. scipy and octave use stderr. I haven't done this as I think writing to stderr is bad practice for a C extension in python, plus the error messages are too technical for our audience. So instead I create a temporary file using the ANSI function tmpfile() and write errors to it that are ignored. Instead I raise a python RuntimeError with a simpler explanation of the error. I have used tmpfile() rather than say writing to /dev/null as it is cross-platform. However, in case a user really does want the full details of the qhull error, e.g. to help with a bug report, if verbose mode is enabled then I do use stderr instead of tmpfile. This isn't elegant but I can't think of a better solution.

(2) `mlab.griddata` is a matlab-similar utility function to interpolate from an unstructured (i.e. triangular) grid to some other grid. It provides the option for linear or natural neighbor ('nn') interpolation, the latter being specific to delaunay triangulations. You could use either linear or nn interpolation with `matplotlib.delaunay`, but because this wasn't very robust if you had installed the `natgrid` mpl_toolkit you could use nn interpolation with that. Now the combination of qhull and `matplotlib.tri.Triangulation` does not support nn interpolation and I don't wish to do so as that would involve keeping the qhull data structures in memory in case they were subsequently needed for an nn interpolation, and that is a significant change that I can't justify for what is a matlab utility function. So now `griddata` has two options: for linear interpolation qhull is used, which is always available; for nn interpolation natgrid must be installed and if it isn't an error is raised. Unfortunately the historic default is nn interpolation so that a standard installation without natgrid will by default raise an error. Again this is not elegant but as I don't know why the default is nn I don't feel I can change it.

There is an argument that now the delaunay triangulations are robust, there is no need at all for natgrid and it could just be removed and the only interpolation option being linear, but I think this would be too big a change in one go. Finally I should add that I will be discouraging use of `griddata` and instead encouraging use of the `matplotlib.tri.TriInterpolator` classes which are more flexible and more powerful, so `griddata` will become less important than it is now.