# problem with DelaunayMesh 3D coordinates

I found DelaunayMesh works fine for 2D. For example,

coordinateList = Tuples[{Range[3], Range[3]}];
DelaunayMesh[coordinateList, PlotTheme -> "Lines"]


gives

Oddly enough, it does not work for simple regular point array like below

coordinateList = Tuples[{Range[3], Range[3], Range[3]}];
DelaunayMesh[coordinateList, PlotTheme -> "Lines"]


which just prints out the original data like

DelaunayMesh[{{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 1}, {1, 2,
2}, {1, 2, 3}, {1, 3, 1}, {1, 3, 2}, {1, 3, 3}, {2, 1, 1}, {2, 1,
2}, {2, 1, 3}, {2, 2, 1}, {2, 2, 2}, {2, 2, 3}, {2, 3, 1}, {2, 3,
2}, {2, 3, 3}, {3, 1, 1}, {3, 1, 2}, {3, 1, 3}, {3, 2, 1}, {3, 2,
2}, {3, 2, 3}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}},
PlotTheme -> "Lines"]


I have to jiggle each point a little to make DelaunayMesh work. Define

ClearAll[jiggleCoordinateList];
jiggleCoordinateList[coordinateList_, eta_] := Module[{},
RandomReal[eta*{-1, 1}, Dimensions@coordinateList] + coordinateList
]


then

coordinateList = Tuples[{Range[3], Range[3], Range[3]}];
DelaunayMesh[jiggleCoordinateList[coordinateList, 0.00001],
PlotTheme -> "Lines"]


gives

But why is that? I can not think of a reason why a regular point array in 3D can not be DelaunayMeshed.

Though a jiggled mesh is fine for display, for calculations, a jiggled mesh is not the same as the original mesh and will introduce error (even though it is small, it is not perfect).

Is there any workaround other than jiggling coordinates?

• This looks like the situation where a Delaunay triangulation is not well-defined if concyclic points are present. Feb 3, 2021 at 12:11
• Hi, @J.M. more explanations? :) Feb 3, 2021 at 12:14
• It's when if you have a bunch of points that belong to one circle, then a Delaunay triangulation will (usually) have trouble. I am not sure, because I haven't done extensive experiments yet. Feb 3, 2021 at 12:26
• Hmm, what version are you using? DelaunayMesh[Tuples[ConstantArray[Range[3], 3]]] seems to work fine in 11.3 ... Feb 3, 2021 at 12:30

Needs["NDSolveFEM"]

• That is quite ironic for me. Because I was reading doc and tutorial of ToElementMesh all day and never thought it could directly support bare coordinate list. Thank you so much!! Feb 3, 2021 at 12:50
• @matheorem, and that's a shortcoming; in the next version you can specify ToElementMesh["Coordinates" -> coords] and it will give you the Delaunay triangulation. If you have suggestions for improving the FEM documentation, let me know. Feb 3, 2021 at 12:53
• Hi, user21. I am wondering if I could directly control the mesh quality during ToElementMesh[coords]. I mean throw away triangles whose quality is below a threshold, So I won't have to do a postprocessing deleting work. I tried various options of ToElementMesh all failed. Feb 4, 2021 at 6:05