scipy/scipy — pull request #212 by pv (2012-05-12 00:13:38+00:00)
Title: BUG: trying to fix #1605, griddata spitting out nans

Now comes somewhat tricky stuff: ticket http://projects.scipy.org/scipy/ticket/1605 reports a bug in interpolate.griddata, which turns out to be due to numerical precision issues in "is-this-point-inside-this-simplex" checks. These turn up when the triangulation contains nearly-zero-volume simplices, which is actually not so rare in rectangular grids.

Unfortunately, this is sort of a release blocker, and should be solved for 0.11.0.

This patch set does the following:

- Detect which simplices are "bad", i.e., for which we cannot reliably detect whether points are inside or not

- This leaves in nearly-zero-volume "holes" inside the triangulation (which is always convex in reality), in which it is numerically unclear whether a point belongs to a simplex or not

- To resolve this, we add sqrt(eps) sized margins for each simplex, so that the holes are blocked. Or, are they?

The problem here is that the broadening of the simplices by sqrt(eps) is obviously a fudge factor, and it's probably not guaranteed that even this is large enough in all cases. It also introduces errors of the same relative order of magnitude, sqrt(eps), for interpolation --- although this is likely not so bad.

I think this problem cannot be avoided just by telling Qhull to use its `QJ` joggling mode, as badly conditioned simplices probably still occur e.g. in manually perturbed rectangular grids.

I'll try to think up a better solution, but in case nothing comes up, this PR should be a reasonable workaround for practical purposes.