Regression /Bug in DelaunayMesh from 10.3.1 to 10.4

Bug introduced in 10.4 and persists through 11.1

In answering this question, I realized the OP and I were obtaining different results from the alphaShapes2D code. This question was updated with additional point sets, but when I tried to use my answer there, it failed. The OP used my answer and got really good results which made me realize something has changed between Mathematica versions 10.3.1 and 10.4. I think I may have tracked the problem down to DelaunayMesh. To see what I mean, here are the MeshRegions generated from the data obtained from the linked question using the same alpha parameter (10.4 is on the right of the following images):

alphaShapes2D[points, 3.0]


You can see it's more pronounced if we try to extract the region boundaries:

When I tried to apply the code to the second data set provided (points2), Mathematica 10.3.1 returns the nice result shown in the linked question whereas, 10.4 fails to return any useful result. After spending some time debugging the only thing I could come up with is that DelaunayMesh is doing something different in both versions. For instance the number of mesh cells returned in both versions are different:

\$Version
dd = DelaunayMesh[points];
MeshCellCount[dd, All]


Also, as you can see from above, in 10.4 DelaunayMesh claims there's a degenerate polygon but we don't see this error in 10.3.1. Can anyone reproduce this? Is this a change in algorithm in DelaunayMesh?

• Same behavior for me (OS X, mma 10.3.1 / 10.4). – SquareOne Mar 22 '16 at 8:18

The problem arises from the definition of ellipsePoints in the linked question, which maps over a range of angles Range[0, 2 Pi, 0.02 Pi]. Because the range includes both 0 and 2 Pi, there are duplicate points in the data. Simply changing to Range[0.02 Pi, 2 Pi, 0.02 Pi] makes the problem go away.
• @RunnyKine I'm not sure. The point is not perfectly duplicated due to roundoff errors. The triangulation works okay (it uses TriangleDelaunay from the TriangleLink package) and treats the points as distinct, but MeshRegion seems to treat them as equal. The inconsitency could be regarded as a bug. – Simon Woods Mar 28 '17 at 15:54