1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/delaunayn.R
\name{delaunayn}
\alias{delaunayn}
\title{Delaunay triangulation in N dimensions}
\usage{
delaunayn(p, options = NULL, output.options = NULL, full = FALSE)
}
\arguments{
\item{p}{An \eqn{M}-by-\eqn{N} matrix whose rows represent \eqn{M}
points in \eqn{N}-dimensional space.}
\item{options}{String containing extra control options for the
underlying Qhull command; see the Qhull documentation
(\url{../doc/qhull/html/qdelaun.html}) for the available
options.
The \code{Qbb} option is always passed to Qhull. The remaining
default options are \code{Qcc Qc Qt Qz} for \eqn{N<4} and
\code{Qcc Qc Qt Qx} for \eqn{N>=4}. If neither of the \code{QJ}
or \code{Qt} options are supplied, the \code{Qt} option is
passed to Qhull. The \code{Qt} option ensures all Delaunay
regions are simplical (e.g., triangles in 2D). See
\url{../doc/qhull/html/qdelaun.html} for more details. Contrary
to the Qhull documentation, no degenerate (zero area) regions
are returned with the \code{Qt} option since the R function
removes them from the triangulation.
\emph{If \code{options} is specified, the default options are
overridden.} It is recommended to use \code{output.options} for
options controlling the outputs.}
\item{output.options}{String containing Qhull options to control
output. Currently \code{Fn} (neighbours) and \code{Fa} (areas)
are supported. Causes an object of return value for details. If
\code{output.options} is \code{TRUE}, select all supported
options.}
\item{full}{Deprecated and will be removed in a future release.
Adds options \code{Fa} and \code{Fn}.}
}
\value{
If \code{output.options} is \code{NULL} (the default),
return the Delaunay triangulation as a matrix with \eqn{M} rows
and \eqn{N+1} columns in which each row contains a set of
indices to the input points \code{p}. Thus each row describes a
simplex of dimension \eqn{N}, e.g. a triangle in 2D or a
tetrahedron in 3D.
If the \code{output.options} argument is \code{TRUE} or is a
string containing \code{Fn} or \code{Fa}, return a list with
class \code{delaunayn} comprising the named elements:
\describe{
\item{\code{tri}}{The Delaunay triangulation described above}
\item{\code{areas}}{If \code{TRUE} or if \code{Fa} is specified, an
\eqn{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 \url{../doc/qhull/html/qh-optf.html#Fa}.}
\item{\code{neighbours}}{If \code{TRUE} or if \code{Fn} is specified,
a list of neighbours of each simplex. Note that a negative number
corresponds to "facet" (="edge" in 2D or "face" in 3D) that has no
neighbour, as will be the case for some simplices on the boundary
of the triangulation.
See \url{../doc/qhull/html/qh-optf.html#Fn}}
}
}
\description{
The Delaunay triangulation is a tessellation of the convex hull of
the points such that no \eqn{N}-sphere defined by the \eqn{N}-
triangles contains any other points from the set.
}
\note{
This function interfaces the Qhull library and is a port
from Octave (\url{https://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 \url{../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 \link{distmesh2d} (currently only 2D).
}
\examples{
# example delaunayn
d <- c(-1,1)
pc <- as.matrix(rbind(expand.grid(d,d,d),0))
tc <- delaunayn(pc)
# example tetramesh
\dontrun{
rgl::view3d(60)
rgl::light3d(120,60)
tetramesh(tc,pc, alpha=0.9)
}
tc1 <- delaunayn(pc, output.options="Fa")
## sum of generalised areas is total volume of cube
sum(tc1$areas)
}
\references{
\cite{Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T.,
\dQuote{The Quickhull algorithm for convex hulls,} \emph{ACM Trans. on
Mathematical Software,} Dec 1996.}
\url{http://www.qhull.org}
}
\seealso{
\code{\link[interp]{tri.mesh}}, \code{\link{convhulln}},
\code{\link{surf.tri}}, \code{\link{distmesh2d}}
}
\author{
Raoul Grasman and Robert B. Gramacy; based on the
corresponding Octave sources of Kai Habel.
}
\keyword{dplot}
\keyword{graphs}
\keyword{math}
|
