delvor: Delaunay triangulation and Voronoi diagram

In alphahull: Generalization of the Convex Hull of a Sample of Points in the Plane

Delaunay triangulation and Voronoi diagram

Description

This function returns a list containing the Delaunay triangulation and Voronoi diagram of a given planar sample.

Usage

delvor(x, y = NULL)

Arguments

x, y	The x and y arguments provide the coordinates of a set of planar points. Alternatively, a single argument x can be provided, see Details.

Details

The coordinates are obtained using xy.coords. At least three non-collinear points are required.

The Delaunay triangulation is computed with delaunayn from the geometry package, which uses Qhull. The corresponding Voronoi diagram is reconstructed from the triangle incidences and circumcentres. For an interior Delaunay edge, its dual Voronoi edge joins the circumcentres of the two adjacent triangles.

For a Delaunay edge on the convex hull, the dual Voronoi edge is semi-infinite. The function dummycoor supplies fictitious coordinates along the outward-pointing ray for plotting; these are not additional Voronoi vertices. Its direction is determined using the sample centroid.

The matrix mesh contains one row for each Delaunay edge: ind1, ind2 are its sample-point indices; x1, y1, x2, y2 are its endpoint coordinates; mx1, my1, mx2, my2 are the coordinates of the corresponding Voronoi edge endpoints; and bp1, bp2 identify fictitious endpoints of unbounded Voronoi rays.

Value

A list of class "delvor" with the following components:

mesh	A twelve-column matrix with one row for each distinct Delaunay edge and its dual Voronoi edge.
x	A two-column matrix with the coordinates of the sample points.
tri.obj	An object of class "triSht" containing the Delaunay triangulation and associated geometric information. Its components include trlist, a matrix containing the triangle vertices, neighbouring triangles and edge indices; cclist, containing circumcircle information; chull, containing the indices of the convex hull vertices; and arcs, containing the Delaunay edges. This structure is retained for backward compatibility.

References

Barber, C. B., Dobkin, D. P. and Huhdanpaa, H. (1996). The Quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 22(4), pp. 469–483.

See Also

plot.delvor.

Examples

## Not run: 
# Random sample in the unit square
x <- matrix(runif(20), ncol = 2)
# Delaunay triangulation and Voronoi diagram calculation
delvor.obj <- delvor(x)

## End(Not run)

alphahull documentation built on Oct. 30, 2026, 1:07 a.m.