Centroidal Voronoi (Dirichlet) tessellation.
Calculates the centroidal Voronoi (Dirichlet) tessellation using Lloyd's algorithm.
cvt(object, stopcrit = c("change", "maxit"), tol = NULL, maxit = 100, verbose = FALSE)
object |
An object of class either |
stopcrit |
Text string specifying the stopping criterion for the algorithm. If
this is |
tol |
The tolerance used when the stopping criterion is |
maxit |
The maximum number of iterations to perform when the stopping criterion
is |
verbose |
Logical scalar. If |
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.
A list with components:
centroids |
A data frame with columns |
tiles |
An object of class |
This function was added to the deldir
package at the
suggestion of Dr. Micha\"el Aupetit, Senior Scientist at the
Qatar Computing Research Institute, Hamad Bin Khalifa University.
Rolf Turner r.turner@auckland.ac.nz
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.
## 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)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.