Re: [matplotlib-devel] Interpolation in a triangular mesh (tri.Triangulation)

[Ian T. <ian...@gm...>]

Hi Geoffroy,

I have had some time to look at your TriLinearInterpolator in some detail
(the other two files only briefly).  I would indeed like to add something
like this to matplotlib - the mesh refinement looks very nice and the
interpolators would be useful to many people.

As you suspected, the code does need significant changes before we can
include it.  Some are merely cosmetic, as all code must adhere to PEP8 and
the matplotlib coding guidelines, but there are also some functional and
performance improvements.  For example, your wavefront method for finding
the triangle containing a certain point must be able to deal with masked
triangulations and indeed triangulations that are discontinuous, for
example two islands in a masked-out ocean, which is unusual but must be
supported.  In terms of performance, there is much explicit looping within
numpy arrays that could be improved using other numpy array commands, and
would also reduce the length of the source code.  There is an argument for
some of the performance-critical code to be in C/C++.

I think the code used to determine which triangle contains a certain point
should be factored out into its own TriFinder class, so that (1) it does
not need to be replicated in the two interpolator classes, and (2)
different algorithms can be easily swapped if necessary.  I have a C++
TriFinder class that I could modify to work within matplotlib, and it is
O(log N) so should be faster than your version for typical use cases.

I expect that this is probably more work than you anticipated when you
asked if the code needed any improvement!  I propose the following: if you
are happy to give matplotlib your source code as it stands and for us to
include it under our BSD-style license, then I will take on the
responsibility of getting it into a form that will be accepted by the other
developers.  I will acknowledge your contribution in both the source code
and on the web site, something like "based on code contributed by Geoffroy
Billotey".

Alternatively, if you would like to use this as an excuse to learn how to
contribute to matplotlib more actively but don't want to take on
everything, then we could divide up the work so that first I write my C++
log(N) TriFinder class and the linear interpolator that uses it, and then
you could modify the cubic interpolator following the format of the linear
interpolator and using my guidance as and when you need it.

Let me know your preference,
Ian

P.S.  Never apologise for not being a computer scientist!  Many of our
developers, myself included, are proper scientists or engineers!!!


On 29 October 2012 09:37, Ian Thomas <ian...@gm...> wrote:

> Hi Geoffroy
>
> This will certainly be very useful.  I need to spend some time looking at
> it and seeing how it would best fit within the matplotlib framework,
> particularly as only a few days ago I committed to writing a triangular
> grid interpolator for quad grids and it would be sensible to group these
> interpolators together in some way.
>
> I'll get back to you when I've had time to look at it.
>
> Thanks for your efforts!
> Ian
>
>
>
> On 28 October 2012 20:17, GBillotey <geo...@gm...> wrote:
>
>>    Hi!
>>
>>
>> I had recently to develop interpolators for a function defined at the
>> nodes
>> of a user-specified triangular mesh.
>> (Beside interpolation, it can help producing higher-quality tricontour
>> plots, using interpolation on a refined mesh and matplotlib tricontour
>> function.)
>>
>> Being a regular user of matplotlib, I would be happy if it can be useful
>> to
>> others...
>> The code is hosted here:
>> https://github.com/GBillotey/trimesh-interpolator.git
>>
>>
>> Please let me know if it this dev. can be useful and if the code needs
>> some
>> cleaning (I am not a computer scientist, only a mechanical engineer)
>>
>>
>> Cheers,
>> Geoffroy.
>>
>