7
$\begingroup$

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

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

gives

2D Delaunay triangulation

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

Delaunay tetrahedralization of "jiggled" grid

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?

$\endgroup$
6
  • $\begingroup$ This looks like the situation where a Delaunay triangulation is not well-defined if concyclic points are present. $\endgroup$ Feb 3, 2021 at 12:11
  • $\begingroup$ Hi, @J.M. more explanations? :) $\endgroup$
    – matheorem
    Feb 3, 2021 at 12:14
  • $\begingroup$ 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. $\endgroup$ Feb 3, 2021 at 12:26
  • $\begingroup$ Hmm, what version are you using? DelaunayMesh[Tuples[ConstantArray[Range[3], 3]]] seems to work fine in 11.3 ... $\endgroup$ Feb 3, 2021 at 12:30
  • 1
    $\begingroup$ Seem to work in version 12.0, too. Please contact the support about this. This is quite certainly a bug. $\endgroup$ Feb 3, 2021 at 22:24

1 Answer 1

7
$\begingroup$

As a workaround you can use the finite element mesh generator:

Needs["NDSolve`FEM`"]
coordinateList = Tuples[{Range[3], Range[3], Range[3]}];
MeshRegion[ToElementMesh[coordinateList], PlotTheme -> "Lines"]

enter image description here

$\endgroup$
6
  • $\begingroup$ 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!! $\endgroup$
    – matheorem
    Feb 3, 2021 at 12:50
  • 2
    $\begingroup$ @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. $\endgroup$
    – user21
    Feb 3, 2021 at 12:53
  • $\begingroup$ I do have other questions about FEM package. I will post later :) $\endgroup$
    – matheorem
    Feb 3, 2021 at 12:58
  • $\begingroup$ 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. $\endgroup$
    – matheorem
    Feb 4, 2021 at 6:05
  • $\begingroup$ @matheorem, no that's not possible. The point of a Delaunay mesh is to connect a set of nodes, however, it does not fiddle with the position of them. $\endgroup$
    – user21
    Feb 4, 2021 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.