Re: [Matplotlib-users] Contour Plotting of Varied Data on a Shape

[Robert K. <rob...@gm...>]

On 2010-03-11 15:49 PM, Chris Barker wrote:
> Robert Kern wrote:
>>> the triangulation. Yes, it would use the existing delaunay code by
>>> default, and hopefully optionally use the not-as-good-a-license code the
>>> Robert Kern put in SciPy.
>>
>> I did what now?
>
> I thought you'd put a wrapper of a delaunay code that is GPL'd or
> something (not BSD compatible anyway) into a scikit or something?
> optional -- so it doesn't screw up licensing for those that don't want it.
>
> Anyway, the point is, for any code that might be put into MPL, we want a
> properly licensed compatible default, but ideally with the option of
> easily plug in in other, better, delaunay code that may not be license
> compatible.
>
> Now that I've written this, I really should go and look and see if I
> remember correctly:
>
> I've found this:
>
> http://scikits.appspot.com/delaunay
>
> Though I see no reference to license in there, so I presume it's under
> the same license as scipy.
>
> So I guess I was thinking of the natgrid toolkit, which I guess is not
> Robert's work, and is a substitute for nn interpolation, not triangulation.
>
> Sorry for writing too quickly.

Instead of addressing the misconceptions point by point, let me just lay out the 
situation:

natgrid is a GPLed library for doing Delaunay triangulation and natural neighbor 
interpolation. The author is presumed to be deceased, so this code will always 
be GPLed. It seems to fail less often when doing the Delaunay triangulation on 
datasets in the wild; however, it is not using robust geometric primitives, so 
there probably still are cases where it fails.

I wrote a BSD library for doing natural neighbor interpolation using the 
Delaunay triangulation code using the sweepline algorithm. This algorithm does 
not (and cannot) use robust geometric primitives, so there are datasets for 
which it fails to produce a valid triangulation. This is the code in 
scikits.delaunay. I have not pushed it to a 1.0 release because of this issue. 
However, this *was* put into matplotlib. matplotlib can optionally use natgrid 
if it is installed.

> While I've got your attention, though -- I suspect you have looked for
> license compatible delaunay code and the stuff in the scikits package is
> as good as it gets?

Pretty much. I do have some code for constructing the Delaunay triangulation 
using robust primitives and an insertion algorithm, but it is an order of 
magnitude slower than scikits.delaunay. Ideally, we would be able to find or 
write a divide-and-conquer algorithm using Jon Shewchuk's robust geometric 
primitives.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco