delaunay: Delaunay tessellation

In delaunay: 2d, 2.5d, and 3d Delaunay Tessellations

Delaunay tessellation

Description

Delaunay tessellation of a set of 2D or 3D points.

Usage

delaunay(points, elevation = FALSE, constraints = NULL, quick3d = FALSE)

Arguments

points	numeric matrix which stores the points, one point per row
elevation	if points are three-dimensional and elevation=TRUE, then the function performs an elevated two-dimensional Delaunay triangulation, using the z coordinates of the points for the elevations; see the example
constraints	for 2D only, some edges to perform a constrained Delaunay triangulation, given as an integer matrix with two columns (each row provides the indices of the two points forming the edge); NULL for no constraint
quick3d	Boolean, for 3D only; if FALSE, there is more information in the output about the Delaunay tessellation; see the Value section for details

Value

The Delaunay tessellation.

• If the dimension is 2 and constraints=NULL, the returned value is a list with four fields: faces, edges, area, and mesh. The faces field is an integer matrix with three columns; each row represents a triangle whose each vertex is given by the index (row number) of this point in the points matrix. The edges field also is an integer matrix with three columns. The first two integers of a row are the indices of the two points which form the edge. The third column, named border, only contains some zeros and some ones; a border (exterior) edge is labelled by a 1. The area field contains only a number: the area of the triangulated region (that is, the area of the convex hull of the points). Finally, the mesh field is a list with three fields: vertices, edges, and faces.

  • The vertices field is the same numeric matrix as the points matrix.

  • The edges field is a dataframe with six columns. The first two columns provide the edges of the triangulation; they are given by row, the two integers of a row are the indices of the two points which form the edge. The third column provides the lengths of the edges. The fourth column, named border, is a column of Boolean values; an edge is labelled by TRUE in this column if it is a border edge, that is to say it has only one adjacent face (a face it belongs to). Finally, the fifth and sixth columns are integer columns providing the indices of the faces adjacent to the edge. If the edge is a border edge, NA is reported in the sixth column.

  • The faces field is a numeric matrix with three columns. In each row i, the first two columns provide the coordinates of the circumcenter of the face indexed by i. The third column provides the area of this face.

• If the dimension is 2 and constraints is not NULL, the returned value is a list with four fields: faces, constraints, area, and mesh. The faces field contains an integer matrix with three columns; each row represents a triangle whose each vertex is given by the index (row number) of this point in the points matrix. The constraints field is an integer matrix with two columns, it represents the constraint edges. The area field contains only a number: the area of the triangulated region. Finally, the mesh field is a list with three fields: vertices, edges, and faces.

  • The vertices field is the same numeric matrix as the points matrix.

  • The edges field is a dataframe with six columns. The first two columns provide the edges of the triangulation; they are given by row, the two integers of a row are the indices of the two points which form the edge. The third column provides the lengths of the edges. The fourth column, named border, is a column of Boolean values; an edge is labelled by TRUE in this column if it is a border edge, that is to say it has only one adjacent face (a face it belongs to). Finally, the fifth and sixth columns are integer columns providing the indices of the faces adjacent to the edge. If the edge is a border edge, NA is reported in the sixth column.

  • The faces field is a numeric matrix with three columns. In each row i, the first two columns provide the coordinates of the circumcenter of the face indexed by i. The third column provides the area of this face.

• If the dimension is 3, the returned value is a list with four fields: cells, facets, edges, and volume. The cells field represents the tetrahedra which form the tessellation. The facets field represents the faces of these tetrahedra, some triangles. The edges field represents the edges of these triangles. The volume field provides only one number, the volume of the tessellation, in other words the volume of the convex hull of the given points. If quick3d=TRUE, then cells, facets and edges are integer matrices with four, three, and two columns respectively; each integer is a vertex index. If quick3d=FALSE, the cells field is a list of lists. Each sublist is composed of three fields: cell provides the indices of the four vertices of the corresponding tetrahedron, faces provides the indices of the four faces of the tetrahedron, that is to say the row number of the facets field which represents this face, and finally there is a volume field which provides the volume of the tetrahedron. The facets field is an integer matrix with four columns. The three first integers of a row are the indices of the points which form the corresponding facet. The fourth column, named onhull is composed of zeros and ones only, and a 1 means that the corresponding facet lies on the convex hull of the points. The edges field contains an integer matrix with three columns. Each row represents an edge, given by the two indices of the points which form this edge, and the third integer, in the column named onhull is a 0/1 indicator of whether the edge lies on the convex hull. Finally the volume field provides only one number, the volume of the tessellation (i.e. the volume of the convex hull of the points).

• If elevation=TRUE, the returned value is a list with five fields: mesh, edges, faceVolumes, volume and area. The mesh field is an object of class mesh3d, ready for plotting with the rgl package. The edges field provides the indices of the edges, given as an integer matrix with two columns. The faceVolumes field is a numeric vector, it provides the volumes under the faces that can be found in the mesh field. The volume field provides the sum of these volumes, that is to say the total volume under the triangulated surface. Finally, the area field provides the sum of the areas of all triangles, thereby approximating the area of the triangulated surface.

Examples

library(delaunay)
# elevated Delaunay triangulation ####
f <- function(x, y){
  2 * exp(-(x^2 + y^2)) # integrate to 2pi
}
x <- y <- seq(-4, 4, length.out = 50)
grd <- transform(expand.grid(x = x, y = y), z = f(x, y))
del <- delaunay(as.matrix(grd), elevation = TRUE)
# `del` is a list; its first component is a mesh representing the surface:
mesh <- del[["mesh"]]
library(rgl)
open3d(windowRect = c(50, 50, 562, 562))
shade3d(mesh, color = "limegreen")
wire3d(mesh)
# in `del` you can also found the volume under the surface, which should
#   approximate the integral of the function:
del[["volume"]]

delaunay documentation built on May 31, 2023, 6:26 p.m.