Delaunay bug: bad triangulations (intersecting triangles)

[AmitAronovitch]

For certain configurations of (x,y) points, matplotlib.delaunay.delaunay() produces illegal triangulations - in particular they contain overlapping triangles.
As a consequence, the "Triangulation" class cannot be used for such data, as it fails during construction (overlapping triangles break the assumptions used for the convex-hull computation).
A sample dataset is available at https://dl.dropbox.com/u/6960989/bad_tri/points.csv
The attached image is zoomed-in on some overlapping triangles in the resulting triangulation.

(will try to attach some code later)

[AmitAronovitch]

Hmm... seems that there's no simple way to attach.
So, for now - all's in the following DB folder: https://dl.dropbox.com/u/6960989/bad_tri/index.html

Code for producing the bad triangulation and plotting it:

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.delaunay as dl

def draw_triangles(x,y, nodes, **v):
    circ_nodes = np.concatenate([nodes, nodes[:,:1]],1)
    for inds in circ_nodes:
        plt.plot(np.take(x,inds),np.take(y,inds),'k-')

pts = np.array([map(float,line.split(",")) 
                for line in open("points.csv")])
x,y = np.transpose(pts)
plt.plot(x,y,'rd')

cents, edges, nodes, neighbors = dl.delaunay(x, y)
draw_triangles(x,y, nodes)
plt.show()

Also attached are a csv containing the dataset, and two zoom-ins of the plot.
Note that I have seen this problem many times - this is just the smallest example I managed to sit down and track. Let me know if more examples are required.

[ianthomas23]

As discussed on the matplotlib-devel mailing list, the proposed solution is to replace the existing matplotlib Delaunay triangulation code with Qhull. I will investigate.

[ianthomas23]

Fixed by PR #2504.