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

[geoffroy b. <geo...@gm...>]

Hello Ian,

Thank you for your second proposition ; I find it very interesting in fact.

(But beware that, as I do not feel able to do this on my own, your code
exemple / guidance would be needed for sure... )
I will have a look at http://matplotlib.org/devel/index.html

I think your idea of having a separate TriFinder class is quite good. My
search algo. is not optimised, only avoiding a O(N) for interpolations
along a path or line.
Some other parts of the code (especially the loop over the (x,y) points in
__call__() ) may also be performance-critical, at least for the 'cubic'
interpolator. But I dont have a clear picture on how to embed C++ code in
python so I would need your example to figure out what is possible.

Regards
Geoffroy.


2012/11/14 Ian Thomas <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.
>>>
>>
>