This looks great. I'm not the biggest fan of shipping the dependency inside our own repo, but I guess it is consistent with our use of Agg and CXX, so I'm not going to make a song and dance about that.

Which platforms have you tested this on? I'd like to get some verification that this is working on windows and OSX at the least.

I've never got around to trying out the NADGRIDS extension myself, I think we should at least port this over to github and get some travis testing of it either here (it isn't being installed atm.) or in its own repo.

This would be a good subject for a discussion on our next developer hangout (2 weeks tomorrow).

@pelson: I've tested it comprehensively on linux (3 different distributions, 32 and 64-bit, with and without natgrid), but not at all on macos or windows as I don't use them.

I haven't looked at natgrid much except to confirm that it was generated using Cython which I have no experience of. For this PR I've opted for minimal change with respect to how it used to be, but I suspect that the more I look into it the more I would like to remove natgrid completely.

It may be a good subject for the next developer hangout but I can't make it (Thursdays, UK office hours are always bad for me). I can answer questions before and after though.

It looks like we have some PEP8 failures here. Once those are fixed, I think we'll just look over this for docstring and style issues, but I suspect the actual work here is probably fine.

The pep8 failures are due to the bootstrap code in _qhull.py that is autogenerated by distutils. It looks like this is a known problem as all the other bootstrap files for C/C++ extensions are listed as EXCLUDE_FILES in test_coding_standards.py. I will therefore do the same with the _qhull.py.

However, there are problems with the C code. @GBillotey has kindly tested the code on windows and identified a problem that I need to look at before this PR can proceed.

I have rebased this PR, dealt with the pep8 failure and fixed the problem on windows. For the latter, rather than creating a temporary file to write to which causes ownership problems on windows, I am instead telling qhull to write to /dev/null on POSIX-compliant OSes and nul on windows. And rather than doing some nasty #ifdef...#else...#endif in the C code to deal with the different OSes, I am instead using the handy python os.devnull as I think this is more future-proof.

I have fully tested the PR on linux and windows. There should be no problems with it working on macos.

I think this is a most excellent (if admittedly huge) PR. I've gone over the code for smells and areas of obscurity, but I'm satisfied that what has been implemented has been implemented well and thoroughly.

I'm going to leave this up for 4 days (until Monday the 16th of December), but if there are no further objections, I will happily merge this.

It is almost inevitable that this will have some impact on the build for some users, but it is unrealistic IMHO to test every variant of OS/numpy etc. and it is for that reason we have release candidates 😉. Thank you @ianthomas23 for testing this in Windows and Linux.

👍 - great job!

Good job @ianthomas23! I've posted on the mpl-devel mailing list to try to get some real life testers before the release candidate phase.

Thank you very much for this Patch! On my current (irregular) datasets, I encountered at least 3 different errors, using matplotlib 1.3.x calling matplotlib.mlab.griddata, while the developer branch and Qhull, solves (almost) all problems! I tried different datasets, and I found it really stable - I hope you can release matplotlib 1.4.x soon, so I could switch back to an official version.

@ngoldbaum Reading this, it looks like we still have the old triangulation code, it just got moved.

@tacaswell it ended up being a pretty straightforward patch: https://bitbucket.org/yt_analysis/yt/pull-request/1017/update-contour-plots-for-matplotlib-140/diff

I've been having trouble exporting the results of Delaunay triangulation in either Matplotlib or now through QHull in a form that I can use.
I eventually want to do some statistical analysis on the shape of the triangles (something done with an old archaeology program, BASP) to see whether the distribution of a whole lot of points are clustered, randomly distributed or patterned.

Matplotlib seems to give me sets of 4 points (the "simplices") that I've had trouble saving in anything like a useful format, but which I first assumed but have since found don't correspond to the old STL (Standardized Tessalation Language) structure: all 3 points in a triangular facet, plus the first point repeated, but rather to some two-facet polygon.
Just what QHull is giving me... I don't really know...

Anyway: could you give me some assistance with either exporting the simplices into a numpy array or a csv file or something, or what I can or cannot do with what comes out of QHull???

I think you're better off looking at SciPy's Delaunay code which also uses QHull, but is designed to give you numpy arrays.

@WombatBill A merged PR is not the place to put a usage question. It should be posted to the matplotlib users mailing list.

@dopplershift Please don't advise users to use scipy when it is not required.

If you google "matplotlib triangulation" the first result is https://matplotlib.org/api/tri_api.html. A cursory glance at the Triangulation class will show you what to do. Here is a minimal example:

>>> import matplotlib.tri as mtri
>>> x = [0, 0, 1, 1]
>>> y = [0, 1, 0, 1]
>>> triang = mtri.Triangulation(x, y)
>>> print(triang.triangles)
>>> print(type(triang.triangles))
[[3 1 0]
 [0 2 3]]
<class 'numpy.ndarray'> (2, 3)

which shows that 'triang.triangles' is a numpy array of shape (number of triangles, 3).

I've been using Scipy, but couldn't export it into any useful format.
This is why I went to QHull, trying to bypass the export issues, and figure out what the two programs are actually calculating.
And that is not at all clear.

Ideally, somehow, from a list of coordinates (x and y, or x, y and z) I should be able to get a list of the coordinates for individual triangles (or facets), and triangles have 3 coordinates, not the 4 I get from Scipy.

@WombatBill Read the link I gave you...

I am reading it; again...
I have read it before...

triang.triangles is an array of the indices of the points that comprise the triangles. If you want the x and y coordinates of those triangles, here is a simple example:

import matplotlib.tri as mtri
import numpy as np
x = np.asarray([0, 0, 1, 1])
y = np.asarray([0, 1, 0, 1])
triang = mtri.Triangulation(x, y)
triangles = triang.triangles
print('triangle indices', triangles)
print('triangle x-values', x[triangles])
print('triangle y-values', y[triangles])

The output is

triangle indices [[3 1 0]
 [0 2 3]]
triangle x-values [[1 0 0]
 [0 1 1]]
triangle y-values [[1 1 0]
 [0 0 1]]