geometry (version 0.1)

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 = "QJ")

Arguments

p

p is an n-by-dim matrix. The rows of p represent n points in dim-dimensional space.

options

Optional options, see details below.

Value

• The return matrix has m rows and dim+1 columns. It contains for each row a set of indices to the points, which describes a simplex of dimension dim.

Details

This function interfaces the qhull library, and intents to be a port from Octave 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 2-d, 3-d, 4-d, and higher dimensions. It implements the Quickhull algorithm for computing the convex hull. Qhull handles roundoff 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/index.htm). The input n-by-dim matrix contains n points of dimension dim. The return matrix T has m rows and dim+1 columns. It contains for each row a set of indices to the points, which describes a simplex of dimension dim. The 3D simplex is a tetrahedron. If a second optional argument is given, it must be a string containing extra options for the underlying qhull command. In particular, "Qt" may be useful for joggling the input to cope with non-simplicial cases. (See the Qhull documentation (../doc/index.htm) for the available options.)

References

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., The Quickhull algorithm for convex hulls, ACM Trans. on Mathematical Software, Dec 1996. http://www.qhull.org

See Also

tri.mesh, convhulln, surf.tri, distmesh2d

Examples

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

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

# example surf.tri
# ==> see also convhulln, but it currently prints an unavoidable
#     message to the console
ps = matrix(rnorm(3000),ncol=3)        # generate poinst on a sphere
ps = sqrt(3) * ps / drop(sqrt((ps^2) %*%rep(1,3)))
ts = delaunayn(ps)
ts.surf = t( surf.tri(ps,ts) )
rgl.triangles(ps[ts.surf,1], ps[ts.surf,2] ,ps[ts.surf,3],
              col="blue", alpha=.2)
for(i in 1:(8*360)) rgl.viewpoint(i/8)