Delaunay code: future directions?

Development matplotlib-devel
1

Dear MPL-devs,

Currently, matplotlib does Delaunay triangulation using a special purpose module written in C++ (if I'm not mistaken, it was originally forked off from some SciKit and wrapped into a Python module).
Some people (here and on github issues) had suggested it might need some rewrites/modification.
In particular I was wondering if we should continue maintaining it here or maybe switch to using some external library.

Since triangulation is not a plotting-specific problem, and some free libraries are available for solving it, we might actually benefit in terms of efficiency and robustness.

Specifically, I had suggested QHull, which is used by scipy (note that now there is also a stand-alone python interface: https://pypi.python.org/pypi/pyhull - I did not check that out yet).
@dmcdougall had suggested Jonathan Shewchuk's triangle library (we should check the license though - I think it is "for non-commercial use", unlike mpl). There are also other alternatives.

On the other hand, there's the issue of minimizing external dependencies. I think @ianthomas23 had once mentioned that he is happy with having Delaunay code reside in mpl (and, of course, "maintainable" is whatever is most convenient for the maintainers).

I apologize for suggesting more tasks without contributing time to work on them. Just thought that since I finally sat down to report issue #1809 (which seems to be a particularly slippery bug in the code mentioned above), it might be a good time to discuss this topic again.

thanks,

     Amit Aronovitch

2

Hi Amit,

I am with you 100% of the way. We should use an existing open source Delaunay triangulator, and my preference is for QHull as well.

“Improved Delaunay triangulator” is on my matplotlib todo list, albeit it quite a long way from the top. I don’t tend to use the existing code as I usually specify my own triangulations, so I have never seen anything quite as embarrassing as issue #1809. Perhaps I need to bump it up my priority list.

If I come up with a possible solution as a PR, would you be prepared to help test it? You seem to have quite a few examples that don’t work under the existing code and would be very useful for demonstrating if the improved code is indeed an improvement.

Ian

···

On 5 March 2013 23:08, Amit Aronovitch <aronovitch@…149…> wrote:

Dear MPL-devs,

Currently, matplotlib does Delaunay triangulation using a special

purpose module written in C++ (if I’m not mistaken, it was originally

forked off from some SciKit and wrapped into a Python module).

Some people (here and on github issues) had suggested it might need some

rewrites/modification.

In particular I was wondering if we should continue maintaining it here

or maybe switch to using some external library.

Since triangulation is not a plotting-specific problem, and some free

libraries are available for solving it, we might actually benefit in

terms of efficiency and robustness.

Specifically, I had suggested QHull, which is used by scipy (note that

now there is also a stand-alone python interface:

https://pypi.python.org/pypi/pyhull - I did not check that out yet).

@dmcdougall had suggested Jonathan Shewchuk’s triangle library (we

should check the license though - I think it is "for non-commercial

use", unlike mpl). There are also other alternatives.

On the other hand, there’s the issue of minimizing external

dependencies. I think @ianthomas23 had once mentioned that he is happy

with having Delaunay code reside in mpl (and, of course, “maintainable”

is whatever is most convenient for the maintainers).

I apologize for suggesting more tasks without contributing time to work

on them. Just thought that since I finally sat down to report issue

#1809 (which seems to be a particularly slippery bug in the code

mentioned above), it might be a good time to discuss this topic again.

thanks,

 Amit Aronovitch
3

Thanks Ian.

These examples occured when I processed large propriatary datasets. So far, scipy’s triangulation worked whenever matplotlib failed.

When we have a new implementation, it should be quite simple to check if it works where it had previously failed.

Certainly easier than slicing the data to small chunks and trying to distill a failing example of reasonable size as I did in this case.

So, “working”/“not working” test (possibly including some time measurements) I can do on a fairly short notice.

Producing some more examples that fail with the current code might require several hours of work, so would probably get delayed for a few weeks.

Amit
···

On Wed, Mar 6, 2013 at 10:53 AM, Ian Thomas <ianthomas23@…149…> wrote:

Hi Amit,

I am with you 100% of the way. We should use an existing open source Delaunay triangulator, and my preference is for QHull as well.

“Improved Delaunay triangulator” is on my matplotlib todo list, albeit it quite a long way from the top. I don’t tend to use the existing code as I usually specify my own triangulations, so I have never seen anything quite as embarrassing as issue #1809. Perhaps I need to bump it up my priority list.

If I come up with a possible solution as a PR, would you be prepared to help test it? You seem to have quite a few examples that don’t work under the existing code and would be very useful for demonstrating if the improved code is indeed an improvement.

Ian

On 5 March 2013 23:08, Amit Aronovitch <aronovitch@…149…> wrote:

Dear MPL-devs,

Currently, matplotlib does Delaunay triangulation using a special

purpose module written in C++ (if I’m not mistaken, it was originally

forked off from some SciKit and wrapped into a Python module).

Some people (here and on github issues) had suggested it might need some

rewrites/modification.

In particular I was wondering if we should continue maintaining it here

or maybe switch to using some external library.

Since triangulation is not a plotting-specific problem, and some free

libraries are available for solving it, we might actually benefit in

terms of efficiency and robustness.

Specifically, I had suggested QHull, which is used by scipy (note that

now there is also a stand-alone python interface:

https://pypi.python.org/pypi/pyhull - I did not check that out yet).

@dmcdougall had suggested Jonathan Shewchuk’s triangle library (we

should check the license though - I think it is "for non-commercial

use", unlike mpl). There are also other alternatives.

On the other hand, there’s the issue of minimizing external

dependencies. I think @ianthomas23 had once mentioned that he is happy

with having Delaunay code reside in mpl (and, of course, “maintainable”

is whatever is most convenient for the maintainers).

I apologize for suggesting more tasks without contributing time to work

on them. Just thought that since I finally sat down to report issue

#1809 (which seems to be a particularly slippery bug in the code

mentioned above), it might be a good time to discuss this topic again.

thanks,

 Amit Aronovitch
4

Amit,

···

On 6 March 2013 20:20, Amit Aronovitch <aronovitch@…149…> wrote:

So, “working”/“not working” test (possibly including some time measurements) I can do on a fairly short notice.

Producing some more examples that fail with the current code might require several hours of work, so would probably get delayed for a few weeks.

The quick working/not working tests without time measurements would be ample, thanks. I will be writing a set of small tests within the mpl testing framework for specific cases that currently fail, but it will be useful to check on some of the big datasets that you use.

Ian