# Centroidal Voronoi (Dirichlet) tessellation. Calculates the centroidal Voronoi (Dirichlet) tessellation using Lloyd's algorithm. UTF-8 ```r 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"`. ## 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. ## 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. ## Returns 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. ## References [https://en.wikipedia.org/wiki/Lloyd's_algorithm](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. ## Author(s) Rolf Turner rolfurner@posteo.net ## See Also `deldir()` `tile.list()` ## Examples ```r ## 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) ```

cvt function