cvt {deldir}

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)

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".

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.

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 ith point has centroid equal to that point.

Note

This function was added to the deldir package at the suggestion of Dr. Michaël Aupetit, Senior Scientist at the Qatar Computing Research Institute, Hamad Bin Khalifa University.

Author(s)

Rolf Turner [e-mail]

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

## Not run:  # 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

## End(Not run)