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

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

On 16 November 2012 05:14, Damon McDougall <dam...@gm...>wrote:

> >> 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.
> >
> > What algorithm does this use? Is the code open source and/or availabel
> > for other projects?
>
> I'm pretty sure there is an O(log n) algorithm in the Numerical
> Recipes book. It requires you to construct the triangulation in a
> specific way (this allows one to set up a tree data structure of
> triangles nicely). There may be others that I am not aware of though.
>

I think this is the standard method used for point-in-triangulation tests
for delaunay triangulations, as the search structure is created as the
triangulation is built.  We need to support non-delaunay triangulations
that are specified by the user, which requires a different approach.

Ian