10
$\begingroup$

I have a set of known points/nodes irregularly spaced in N-Dimensional space (N>=2), and I would like a way to generate the Delaunay triangulation of these points, and return the corresponding elements.

Are there any existing meshing libraries that will do an N-D Delaunay triangulation?

(I am doing this because I want to use the meshed elements as a basis for linear interpolation at any point in space. My dimension is currently handled by a C++ class templated over dimension if that makes any difference to suggestions...)

Improve this question
$\endgroup$
5
  • $\begingroup$ Hi mirams, and welcome to scicomp! You may be interested in this question: scicomp.stackexchange.com/questions/770/… $\endgroup$ – Paul♦ Jun 17 '13 at 15:40
  • $\begingroup$ Thanks for the link, I was hoping to avoid writing my own mesher. Tetgen (for 3D) runs to a lot of lines of code. It seems like a problem that must have been solved many times. $\endgroup$ – mirams Jun 17 '13 at 15:58
  • $\begingroup$ popular question... also scicomp.stackexchange.com/questions/7664/… $\endgroup$ – clipper Jun 17 '13 at 17:45
  • $\begingroup$ Delaunay triangulation are typically derived from the the convex hull in higher dimensional space. See the qhull remark below. $\endgroup$ – meawoppl Jun 17 '13 at 18:21
  • $\begingroup$ 3D is not that hard, but for 4D it is extremely difficult when refining, I asked a question on MathOverflow, but no answer yet: mathoverflow.net/questions/130878/… $\endgroup$ – Shuhao Cao Jun 17 '13 at 18:33
4
$\begingroup$

I think you can do this using convex hull software (e.g. QHull) via the lifting algorithm. At least, the documentation of matlab's "delaunayn" command seems to indicate as much.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Tested 4D, and that seems to work fine in QHull (I use it via scipy.spatial in python). $\endgroup$ – Ethan Coon Jun 17 '13 at 16:27
  • 1
    $\begingroup$ You won't beat qhull. I have used in via Scipy as well in up to 6 dimensions. $\endgroup$ – meawoppl Jun 17 '13 at 18:20
  • $\begingroup$ Hmmm - this from qhull.org/news/qhull-news.html isn't ideal: "All users In 3-d and higher, option 'Qt' does not produce conforming triangulations for adjacent, non-simplicial facets. For example, if you have a regular, 3-d array of input sites, their Delaunay triangulation consists of cubes. Option 'Qt' will triangulate each cube into tetrahedra. Within each cube, the triangulation is consistent, but it is not necessarily consistent between adjacent cubes [C. Bertoglio; C. de Visser]. How to fix this problem is unknown." Worth a try though, I'll see how I get on. $\endgroup$ – mirams Jun 17 '13 at 19:50
5
$\begingroup$

This feature seems to be available in CGAL

Improve this answer
$\endgroup$
1
  • $\begingroup$ This also looks good. I'll try both Qhull and this. Thanks for the suggestions. $\endgroup$ – mirams Jun 17 '13 at 19:56
0
$\begingroup$

I have also found distmesh in Matlab that appears to be able to do this:

Distmesh Homepage

It does tesselations for finite element meshes (via QHull) but with a nice interface for defining areas / surfaces based on distance functions. Better for cases where you want to define a surface mathematically and do not mind where the internal nodes are.

Improve this answer
$\endgroup$

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.