matplotlib/matplotlib — pull request #1582 by ianthomas23 (2012-12-10 21:22:08+00:00)
Title: Linear tri interpolator

This is the first PR for issue #1521. It adds a `TrapezoidMapTriFinder` that is used to determine the triangles in which (x,y) points lie and a `LinearTriInterpolator` to interpolate scalar fields defined on triangular grids. Have included tests for both classes, a pylab_example for the interpolator and an whizzy interactive event_handling example for the trifinder, and have updated sphinx docs, whats_new and CHANGELOG.

I'll repeat the observation from #1521 that the delaunay module already has a linear interpolator, but it cannot be used with user-specified triangulations unlike the one in this PR which can be used with user-specified and delaunay-calculated triangulations. The new one is much more flexible in accepting arrays of points to iterate over as they can be any shape, e.g. 1D for a transect through a triangulation, 2D to create a quad mesh to pass to contourf, etc.

It is possible that the TrapezoidMapTriFinder is overkill for what we need. It is O(log N) but may be outperformed by a simpler 'walking across the triangulation' algorithm if most users are passing in hi-res regular 2D grids to interpolate to. My preference is to release this code out into the wild as it is and get feedback from users before adding/modifying the trifinder.