Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

delaunayn

Delaunay triangulation in N dimensions


Description

The Delaunay triangulation is a tessellation of the convex hull of the points such that no N-sphere defined by the N- triangles contains any other points from the set.

Usage

delaunayn(p, options = NULL, output.options = NULL, full = FALSE)

Arguments

p

An M-by-N matrix whose rows represent M points in N-dimensional space.

options

String containing extra control options for the underlying Qhull command; see the Qhull documentation (../doc/qhull/html/qdelaun.html) for the available options.

The Qbb option is always passed to Qhull. The remaining default options are Qcc Qc Qt Qz for N<4 and Qcc Qc Qt Qx for N>=4. If neither of the QJ or Qt options are supplied, the Qt option is passed to Qhull. The Qt option ensures all Delaunay regions are simplical (e.g., triangles in 2D). See ../doc/qhull/html/qdelaun.html for more details. Contrary to the Qhull documentation, no degenerate (zero area) regions are returned with the Qt option since the R function removes them from the triangulation.

If options is specified, the default options are overridden. It is recommended to use output.options for options controlling the outputs.

output.options

String containing Qhull options to control output. Currently Fn (neighbours) and Fa (areas) are supported. Causes an object of return value for details. If output.options is TRUE, select all supported options.

full

Deprecated and will be removed in a future release. Adds options Fa and Fn.

Value

If output.options is NULL (the default), return the Delaunay triangulation as a matrix with M rows and N+1 columns in which each row contains a set of indices to the input points p. Thus each row describes a simplex of dimension N, e.g. a triangle in 2D or a tetrahedron in 3D.

If the output.options argument is TRUE or is a string containing Fn or Fa, return a list with class delaunayn comprising the named elements:

tri

The Delaunay triangulation described above

areas

If TRUE or if Fa is specified, an M-dimensional vector containing the generalised area of each simplex (e.g. in 2D the areas of triangles; in 3D the volumes of tetrahedra). See ../doc/qhull/html/qh-optf.html#Fa.

neighbours

If TRUE or if Fn is specified, a list of neighbours of each simplex. See ../doc/qhull/html/qh-optf.html#Fn

Note

This function interfaces the Qhull library and is a port from Octave (http://www.octave.org) to R. Qhull computes convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams. It runs in 2D, 3D, 4D, and higher dimensions. It implements the Quickhull algorithm for computing the convex hull. Qhull handles round-off errors from floating point arithmetic. It computes volumes, surface areas, and approximations to the convex hull. See the Qhull documentation included in this distribution (the doc directory ../doc/qhull/index.html).

Qhull does not support constrained Delaunay triangulations, triangulation of non-convex surfaces, mesh generation of non-convex objects, or medium-sized inputs in 9D and higher. A rudimentary algorithm for mesh generation in non-convex regions using Delaunay triangulation is implemented in distmesh2d (currently only 2D).

Author(s)

Raoul Grasman and Robert B. Gramacy; based on the corresponding Octave sources of Kai Habel.

References

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., “The Quickhull algorithm for convex hulls,” ACM Trans. on Mathematical Software, Dec 1996.

See Also

Examples

# example delaunayn
d <- c(-1,1)
pc <- as.matrix(rbind(expand.grid(d,d,d),0))
tc <- delaunayn(pc)

# example tetramesh
## Not run: 
rgl::rgl.viewpoint(60)
rgl::rgl.light(120,60)
tetramesh(tc,pc, alpha=0.9)

## End(Not run)

tc1 <- delaunayn(pc, output.options="Fa")
## sum of generalised areas is total volume of cube
sum(tc1$areas)

geometry

Mesh Generation and Surface Tessellation

v0.4.5
GPL (>= 3)
Authors
Jean-Romain Roussel [cph, ctb] (wrote tsearch function with QuadTrees), C. B. Barber [cph], Kai Habel [cph, aut], Raoul Grasman [cph, aut], Robert B. Gramacy [cph, aut], Pavlo Mozharovskyi [cph, aut], David C. Sterratt [cph, aut, cre] (<https://orcid.org/0000-0001-9092-9099>)
Initial release
2019-12-02

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.