# delaunayn

##### Delaunay triangulation in N dimensions

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 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*It is recommended to use`options`

is specified, the default options are overridden.`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 neither of the Qhull options `Fn`

or `Fa`

are
specified, 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 contains `Fn`

or `Fa`

,
return a list with class `delaunayn`

comprising
the named elements:

`tri`

The Delaunay triangulation described above

`areas`

If

`Fa`

is specified, an \(M\)-dimensional vector containing the generalise 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

`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).

##### 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

```
# NOT RUN {
# 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)
# }
# NOT RUN {
tc1 <- delaunayn(pc, output.options="Fa")
## sum of generalised areas is total volume of cube
sum(tc1$areas)
# }
```

*Documentation reproduced from package geometry, version 0.4.1, License: GPL (>= 3)*