scipy: Scipy Delaunay triangulation is not oriented

PC details

• scipy==0.12.0
• Linux dana 3.8.0-30-generic #44-Ubuntu SMP Thu Aug 22 20:52:24 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux
• Intel® Xeon® CPU E5-1650 0 @ 3.20GHz
• Linked against Intel MKL (though issue replicated on a machine linked against Atlas)

Issue

With this mesh I am seeing inconsistent results from scipy.spatial.Delaunay. Assuming that the mesh has been loaded using numpy.loadtxt into a variable called points, I duplicate the issue as follows:

from scipy.spatial import Delaunay
scipy_t = Delaunay(points).simplices

I have some code that checks the consistency of a triangulation (in terms of ordering) and the above code generates an inconsistent triangulation.

Ground Truth

In order to sanity check I compared the triangulation against the one created by pyhull. This is created using the same point set as follows:

from pyhull.delaunay import DelaunayTri
pyhull_t = np.asarray(DelaunayTri(points).vertices)

I’ve also generated the triangulation in Matlab using both delaunay and delaunayn and it yields results identical to pyhull_t. My triangulation consistency verifier also confirms that the pyhull_t triangulation is correct.

Options

In order to try and ensure that scipy.spatial.Delaunay is applying the same algorithm as pyhull, I dove in to their source code. There I noticed that they always set the following flags:

i Qt Qc Qbb

but running with those flags as follows:

from scipy.spatial import Delaunay
scipy_t = Delaunay(points, qhull_options='Qbb Qc').simplices

still does not yield correct results.

Example output

An example of the triangulation I am seeing using the flags Qbb Qc:

print scipy_t

[[16549 35521 21080]
 [58451 78938 91348]
 [38031 32638 33401]
 ..., 
 [47968 47967 48281]
 [47968 47656 47969]
 [47968 47655 47656]]

print pyhull_t

[[35521 16549 21080]
 [78938 58451 91348]
 [32638 38031 33401]
 ..., 
 [47968 47967 48281]
 [47656 47968 47969]
 [47655 47968 47656]]

where we can see that the same indices are being generated, but the first two are sometimes swapped.