Bug in Triangulation causes infinite loop if 4 or more duplicate points are used in tricontour()

Hi,
I haven't been able to pin point it exactly but following script:

import matplotlib.pyplot as plt
import matplotlib.tri as tri
import numpy as np
from numpy.random import uniform, seed

seed(0)
npts = 200
x = uniform(-2,2,npts)
y = uniform(-2,2,npts)
z = x*np.exp(-x**2-y**2)

y[1:3] = x[0] # 4 or more duplicate points make tricontour hang!!!
x[1:3] = y[0]
triang = tri.Triangulation(x, y)
plt.tricontour(x, y, z, 15, linewidths=0.5, colors='k')

plt.show()

causes infinite loop in _tri.so. It happens in matplotlib-1.1.0 as well
as git HEAD.
I understand that my input is not exactly valid, but I'd rather see MPL
die than occupy my box for eternity :wink:
Best regards,
Kacper

Hi Kacper,

Just to be clear, is it tri.Triangulation(x, y) that hangs, or is it plt.tricontour(…)?

···

Damon McDougall

d.mcdougall@…831…

http://damon.is-a-geek.com

B2.39

Mathematics Institute

University of Warwick

Coventry

West Midlands

CV4 7AL

United Kingdom

On Monday, 16 April 2012 at 14:28, Kacper Kowalik wrote:

Hi,

I haven’t been able to pin point it exactly but following script:

import matplotlib.pyplot as plt

import matplotlib.tri as tri

import numpy as np

from numpy.random import uniform, seed

seed(0)

npts = 200

x = uniform(-2,2,npts)

y = uniform(-2,2,npts)

z = x*np.exp(-x2-y2)

y[1:3] = x[0] # 4 or more duplicate points make tricontour hang!!!

x[1:3] = y[0]

triang = tri.Triangulation(x, y)

plt.tricontour(x, y, z, 15, linewidths=0.5, colors=‘k’)

plt.show()

causes infinite loop in _tri.so. It happens in matplotlib-1.1.0 as well

as git HEAD.

I understand that my input is not exactly valid, but I’d rather see MPL

die than occupy my box for eternity :wink:

Best regards,

Kacper


For Developers, A Lot Can Happen In A Second.

Boundary is the first to Know…and Tell You.

Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!

http://p.sf.net/sfu/Boundary-d2dvs2


Matplotlib-users mailing list

Matplotlib-users@lists.sourceforge.net

https://lists.sourceforge.net/lists/listinfo/matplotlib-users

Hi Kacper,

Just to be clear, is it tri.Triangulation(x, y) that hangs, or is it plt.tricontour(…)?

It’s plt.tricontour that hangs, tri.Triangulation properly issues warning about duplicates.
Cheers,
Kacper

···

On 16 Apr 2012 22:31, “Damon McDougall” <D.McDougall@…831…> wrote:


Damon McDougall
d.mcdougall@…831…
http://damon.is-a-geek.com
B2.39
Mathematics Institute
University of Warwick
Coventry
West Midlands
CV4 7AL
United Kingdom

On Monday, 16 April 2012 at 14:28, Kacper Kowalik wrote:

Hi,
I haven’t been able to pin point it exactly but following script:

import matplotlib.pyplot as plt
import matplotlib.tri as tri
import numpy as np
from numpy.random import uniform, seed

seed(0)
npts = 200
x = uniform(-2,2,npts)
y = uniform(-2,2,npts)
z = x*np.exp(-x2-y2)

y[1:3] = x[0] # 4 or more duplicate points make tricontour hang!!!
x[1:3] = y[0]
triang = tri.Triangulation(x, y)
plt.tricontour(x, y, z, 15, linewidths=0.5, colors=‘k’)

plt.show()

causes infinite loop in _tri.so. It happens in matplotlib-1.1.0 as well
as git HEAD.
I understand that my input is not exactly valid, but I’d rather see MPL
die than occupy my box for eternity :wink:
Best regards,
Kacper

For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know…and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2


Matplotlib-users mailing list
Matplotlib-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/matplotlib-users

Hi Kacper,

Just to be clear, is it tri.Triangulation(x, y) that hangs, or is it plt.tricontour(…)?

It’s plt.tricontour that hangs, tri.Triangulation properly issues warning about duplicates.
Cheers,
Kacper

Hi,
I haven’t been able to pin point it exactly but following script:

import matplotlib.pyplot as plt
import matplotlib.tri as tri
import numpy as np
from numpy.random import uniform, seed

seed(0)
npts = 200
x = uniform(-2,2,npts)
y = uniform(-2,2,npts)
z = x*np.exp(-x2-y2)

y[1:3] = x[0] # 4 or more duplicate points make tricontour hang!!!
x[1:3] = y[0]

You should call z = x*np.exp(-x2-y2) before changing the points you’re triangulating.

Having said that, I see the same behaviour even if I change the vertices before I compute z.

triang = tri.Triangulation(x, y)
plt.tricontour(x, y, z, 15, linewidths=0.5, colors=‘k’)

plt.show()

causes infinite loop in _tri.so. It happens in matplotlib-1.1.0 as well
as git HEAD.
I understand that my input is not exactly valid, but I’d rather see MPL
die than occupy my box for eternity :wink:
Best regards,
Kacper

I think the reason it’s hanging is because you’re trying to plot the contours of a function that is defined on an invalid triangulation (edges cross at points that are not in the vertex set). I think the best way to deal with this is to write a helper function to check the triangulation is valid. If it isn’t, either tri.Triangulation(x, y) should fail, or the plotter should fail.

Anybody else have any suggestions?

···

On Monday, 16 April 2012 at 16:34, Kacper Kowalik wrote:

On 16 Apr 2012 22:31, “Damon McDougall” <D.McDougall@…831…> wrote:

On Monday, 16 April 2012 at 14:28, Kacper Kowalik wrote:

Damon McDougall

d.mcdougall@…831…

http://damon.is-a-geek.com

B2.39

Mathematics Institute

University of Warwick

Coventry

West Midlands

CV4 7AL

United Kingdom

We can definitely do better here. I have created a issue request on github:
https://github.com/matplotlib/matplotlib/issues/838

and will investigate further.

Ian

···

On 16 April 2012 23:36, Damon McDougall <D.McDougall@…4068…> wrote:

On Monday, 16 April 2012 at 16:34, Kacper Kowalik wrote:

On 16 Apr 2012 22:31, “Damon McDougall” <D.McDougall@…831…> wrote:

Hi Kacper,

Just to be clear, is it tri.Triangulation(x, y) that hangs, or is it plt.tricontour(…)?

It’s plt.tricontour that hangs, tri.Triangulation properly issues warning about duplicates.
Cheers,
Kacper

On Monday, 16 April 2012 at 14:28, Kacper Kowalik wrote:

Hi,

I haven’t been able to pin point it exactly but following script:

import matplotlib.pyplot as plt

import matplotlib.tri as tri

import numpy as np

from numpy.random import uniform, seed

seed(0)

npts = 200

x = uniform(-2,2,npts)

y = uniform(-2,2,npts)

z = x*np.exp(-x2-y2)

y[1:3] = x[0] # 4 or more duplicate points make tricontour hang!!!

x[1:3] = y[0]

You should call z = x*np.exp(-x2-y2) before changing the points you’re triangulating.

Having said that, I see the same behaviour even if I change the vertices before I compute z.

triang = tri.Triangulation(x, y)
plt.tricontour(x, y, z, 15, linewidths=0.5, colors=‘k’)

plt.show()

causes infinite loop in _tri.so. It happens in matplotlib-1.1.0 as well
as git HEAD.
I understand that my input is not exactly valid, but I’d rather see MPL
die than occupy my box for eternity :wink:
Best regards,
Kacper

I think the reason it’s hanging is because you’re trying to plot the contours of a function that is defined on an invalid triangulation (edges cross at points that are not in the vertex set). I think the best way to deal with this is to write a helper function to check the triangulation is valid. If it isn’t, either tri.Triangulation(x, y) should fail, or the plotter should fail.

Anybody else have any suggestions?