Delaunay triangulation (or tessellation) of a set of points.

## Usage

```
delaunay(
points,
atinfinity = FALSE,
degenerate = FALSE,
exteriorEdges = FALSE,
elevation = FALSE
)
```

## Arguments

- points
the points given as a matrix, one point per row

- atinfinity
Boolean, whether to include a point at infinity

- degenerate
Boolean, whether to include degenerate tiles

- exteriorEdges
Boolean, for dimension 3 only, whether to return the exterior edges (see below)

- elevation
Boolean, only for three-dimensional points; if

`TRUE`

, the function performs an elevated Delaunay triangulation (also called 2.5D Delaunay triangulation), using the third coordinate of a point as its elevation; see the example

## Value

If the function performs an elevated Delaunay tessellation, then
the returned value is a list with four fields: `mesh`

, `edges`

,
`volume`

, and `surface`

. The `mesh`

field is an object of
class `mesh3d`

, ready for plotting with the **rgl** package. The
`edges`

field is an integer matrix which provides the indices of the
vertices of the edges, and an indicator of whether an edge is a border
edge; this matrix is obtained with `vcgGetEdge`

.
The `volume`

field provides the sum of the
volumes under the Delaunay triangles, that is to say the total volume
under the triangulated surface. Finally, the `surface`

field provides
the sum of the areas of the Delaunay triangles, thus this is an approximate
value of the area of the surface that is triangulated.
The elevated Delaunay tessellation is built with the help of the
**interp** package.
Otherwise, the function returns the Delaunay tessellation with many details,
in a list. This list contains five fields:

*vertices*the vertices (or sites) of the tessellation; these are the points passed to the function

*tiles*the tiles of the tessellation (triangles in dimension 2, tetrahedra in dimension 3)

*tilefacets*the facets of the tiles of the tessellation

*mesh*a 'rgl' mesh (

`mesh3d`

object)*edges*a two-columns integer matrix representing the edges, each row represents an edge; the two integers of a row are the indices of the two points which form the edge.

In dimension 3, the list contains an additional field *exteriorEdges* if you set `exteriorEdges = TRUE`

. This is the list of the exterior
edges, represented as `Edge3`

objects. This field is involved
in the function `plotDelaunay3D`

.
The **vertices** field is a list with the following fields:

*id*the id of the vertex; this is nothing but the index of the corresponding point passed to the function

*neighvertices*the ids of the vertices of the tessellation connected to this vertex by an edge

*neightilefacets*the ids of the tile facets this vertex belongs to

*neightiles*the ids of the tiles this vertex belongs to

The **tiles** field is a list with the following fields:

*id*the id of the tile

*simplex*a list describing the simplex (that is, the tile); this list contains four fields:

*vertices*, a`hash`

giving the simplex vertices and their id,*circumcenter*, the circumcenter of the simplex,*circumradius*, the circumradius of the simplex, and*volume*, the volume of the simplex*facets*the ids of the facets of this tile

*neighbors*the ids of the tiles adjacent to this tile

*family*two tiles have the same family if they share the same circumcenter; in this case the family is an integer, and the family is

`NA`

for tiles which do not share their circumcenter with any other tile*orientation*`1`

or`-1`

, an indicator of the orientation of the tile

The **tilefacets** field is a list with the following fields:

*id*the id of this tile facet

*subsimplex*a list describing the subsimplex (that is, the tile facet); this list is similar to the

*simplex*list of**tiles***facetOf*one or two ids, the id(s) of the tile this facet belongs to

*normal*a vector, the normal of the tile facet

*offset*a number, the offset of the tile facet

## Note

The package provides the functions `plotDelaunay2D`

to
plot a 2D Delaunay tessellation and `plotDelaunay3D`

to
plot a 3D Delaunay tessellation. But there is no function to plot an
elevated Delaunay tessellation; the examples show how to plot such a
Delaunay tessellation.

## Examples

```
library(tessellation)
points <- rbind(
c(0.5,0.5,0.5),
c(0,0,0),
c(0,0,1),
c(0,1,0),
c(0,1,1),
c(1,0,0),
c(1,0,1),
c(1,1,0),
c(1,1,1)
)
del <- delaunay(points)
del$vertices[[1]]
#> $id
#> [1] 1
#>
#> $point
#> [1] 0.5 0.5 0.5
#>
#> $neighvertices
#> [1] 2 3 4 5 6 7 8 9
#>
#> $neightilefacets
#> [1] 1 3 4 5 7 9 10 11 13 15 16 17 20 21 23 25 26 29
#>
#> $neightiles
#> [1] 1 2 3 4 5 6 7 8 9 10 11 12
#>
del$tiles[[1]]
#> $vertices
#> [1] 8 1 6 2
#>
#> $id
#> [1] 1
#>
#> $simplex
#> $simplex$vertices
#> <hash> containing 4 key-value pair(s).
#> 1 : 0.5 0.5 0.5
#> 2 : 0 0 0
#> 6 : 1 0 0
#> 8 : 1 1 0
#>
#> $simplex$circumcenter
#> [1] 0.50 0.50 -0.25
#>
#> $simplex$circumradius
#> [1] 0.75
#>
#> $simplex$volume
#> [1] 0.08333333
#>
#>
#> $facets
#> [1] 1 2 3 4
#>
#> $neighbors
#> [1] 3 2 5
#>
#> $family
#> [1] 0
#>
#> $orientation
#> [1] -1
#>
del$tilefacets[[1]]
#> $id
#> [1] 1
#>
#> $subsimplex
#> $subsimplex$vertices
#> <hash> containing 3 key-value pair(s).
#> 1 : 0.5 0.5 0.5
#> 2 : 0 0 0
#> 6 : 1 0 0
#>
#> $subsimplex$circumcenter
#> [1] 0.500 0.125 0.125
#>
#> $subsimplex$circumradius
#> [1] 0.5303301
#>
#> $subsimplex$volume
#> [1] 0.3535534
#>
#>
#> $facetOf
#> [1] 1 3
#>
#> $normal
#> [1] 0.0000000 0.7071068 -0.7071068
#>
#> $offset
#> [1] 0
#>
# an elevated Delaunay tessellation ####
f <- function(x, y){
dnorm(x) * dnorm(y)
}
x <- y <- seq(-5, 5, length.out = 50)
grd <- expand.grid(x = x, y = y) # grid on the xy-plane
points <- as.matrix(transform( # data (x_i, y_i, z_i)
grd, z = f(x, y)
))
del <- delaunay(points, elevation = TRUE)
del[["volume"]] # close to 1, as expected
#> [1] 0.9999988
# plotting
library(rgl)
mesh <- del[["mesh"]]
open3d(windowRect = c(100, 100, 612, 356), zoom = 0.6)
aspect3d(1, 1, 20)
shade3d(mesh, color = "limegreen")
wire3d(mesh)
```