deldir (version 2.0-4)

cvt: Centroidal Voronoi (Dirichlet) tessellation.

Description

Calculates the centroidal Voronoi (Dirichlet) tessellation using Lloyd's algorithm.

Usage

cvt(object, stopcrit = c("change", "maxit"), tol = NULL,
       maxit = 100, verbose = FALSE)

Value

A list with components:

centroids

A data frame with columns "x" and "y" specifying the coordinates of the limiting locations of the tile centroids.

tiles

An object of class "tile.list" specifying the Dirichlet (Voronoi) tiles in the tessellation of the points whose coordinates are given in centroids. Note the tile associated with the \(i\)th point has centroid equal to that point.

Arguments

object

An object of class either "deldir" (as returned by deldir()) or "tile.list" (as returned by tile.list()).

stopcrit

Text string specifying the stopping criterion for the algorithm. If this is "change" then the algorithm halts when the maximum change in in the distances between corresponding centroids, between iterations, is less than tol (see below). It stopcrit is "maxit" then the algorithm halts after a specified number of iterations (maxit; see below) have been completed. This argument may be abbreviated, e.g. to "c" or "m".

tol

The tolerance used when the stopping criterion is "change". Defaults to .Machine$double.eps.

maxit

The maximum number of iterations to perform when the stopping criterion is "maxit".

verbose

Logical scalar. If verbose is TRUE then rudimentary “progress reports” are printed out, every 10 iterations if the stopping criterion is "change" or every iteration if the stopping criterion is "maxit".

Author

Rolf Turner

Details

The algorithm iteratively tessellates a set of points and then replaces the points with the centroids of the tiles associated with those points. “Eventually” (at convergence) points and the centroids of their associated tiles coincide.

References

https://en.wikipedia.org/wiki/Lloyd's_algorithm

Lloyd, Stuart P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory 28 (2), pp. 129--137, doi:10.1109/TIT.1982.1056489.

See Also

deldir() tile.list()

Examples

if (FALSE)  # Takes too long.
    set.seed(42)
    x <- runif(20)
    y <- runif(20)
    dxy <- deldir(x,y,rw=c(0,1,0,1))
    cxy1 <- cvt(dxy,verb=TRUE)
    plot(cxy1$tiles)
    with(cxy1$centroids,points(x,y,pch=20,col="red"))
    cxy2 <- cvt(dxy,stopcrit="m",verb=TRUE)
    plot(cxy2$tiles)
    with(cxy2$centroids,points(x,y,pch=20,col="red"))
# Visually indistinguishable from the cxy1 plot.
# But ...
    all.equal(cxy1$centroids,cxy2$centroids) # Not quite.
    cxy3 <- cvt(dxy,stopcrit="m",verb=TRUE,maxit=250)
    all.equal(cxy1$centroids,cxy3$centroids) # Close, but no cigar.
    cxy4 <- cvt(dxy,verb=TRUE,tol=1e-14)
    cxy5 <- cvt(dxy,stopcrit="m",verb=TRUE,maxit=600)
    all.equal(cxy4$centroids,cxy5$centroids) # TRUE
# Takes a lot of iterations or a really small tolerance
# to get "good" convergence.  But this is almost surely
# of no practical importance.
    txy <- tile.list(dxy)
    cxy6 <- cvt(txy)
    all.equal(cxy6$centroids,cxy1$centroids) # TRUE