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)

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.

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.

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.

Author

Rolf Turner rolfurner@posteo.net

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)
#> iteration: 10 change: 0.01090659 
#> iteration: 20 change: 0.005077311 
#> iteration: 30 change: 0.003679425 
#> iteration: 40 change: 0.00279814 
#> iteration: 50 change: 0.0009966652 
#> iteration: 60 change: 0.0004381775 
#> iteration: 70 change: 0.0002279981 
#> iteration: 80 change: 0.0001378879 
#> iteration: 90 change: 9.47937e-05 
#> iteration: 100 change: 6.693825e-05 
#> iteration: 110 change: 4.804137e-05 
#> iteration: 120 change: 3.483073e-05 
#> iteration: 130 change: 2.541936e-05 
#> iteration: 140 change: 1.863291e-05 
#> iteration: 150 change: 1.369995e-05 
#> iteration: 160 change: 1.009469e-05 
#> iteration: 170 change: 7.44972e-06 
#> iteration: 180 change: 5.503994e-06 
#> iteration: 190 change: 4.069836e-06 
#> iteration: 200 change: 3.011221e-06 
#> iteration: 210 change: 2.228981e-06 
#> iteration: 220 change: 1.650506e-06 
#> iteration: 230 change: 1.222469e-06 
#> iteration: 240 change: 9.056073e-07 
#> iteration: 250 change: 6.709699e-07 
#> iteration: 260 change: 4.971776e-07 
#> iteration: 270 change: 3.684291e-07 
#> iteration: 280 change: 2.73037e-07 
#> iteration: 290 change: 2.023522e-07 
#> iteration: 300 change: 1.499714e-07 
#> iteration: 310 change: 1.111525e-07 
#> iteration: 320 change: 8.238307e-08 
#> iteration: 330 change: 6.10608e-08 
#> iteration: 340 change: 4.525758e-08 
#> iteration: 350 change: 3.354466e-08 
#> iteration: 360 change: 2.486325e-08 
#> iteration: 370 change: 1.842867e-08 
#> 
    plot(cxy1$tiles)
    with(cxy1$centroids,points(x,y,pch=20,col="red"))

    cxy2 <- cvt(dxy,stopcrit="m",verb=TRUE)
#> iteration: 10 change: 0.01090659 
#> iteration: 20 change: 0.005077311 
#> iteration: 30 change: 0.003679425 
#> iteration: 40 change: 0.00279814 
#> iteration: 50 change: 0.0009966652 
#> iteration: 60 change: 0.0004381775 
#> iteration: 70 change: 0.0002279981 
#> iteration: 80 change: 0.0001378879 
#> iteration: 90 change: 9.47937e-05 
#> iteration: 100 change: 6.693825e-05 
    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.
#> [1] "Component “x”: Mean relative difference: 0.0008559738"
#> [2] "Component “y”: Mean relative difference: 0.0006650263"
    cxy3 <- cvt(dxy,stopcrit="m",verb=TRUE,maxit=250)
#> iteration: 10 change: 0.01090659 
#> iteration: 20 change: 0.005077311 
#> iteration: 30 change: 0.003679425 
#> iteration: 40 change: 0.00279814 
#> iteration: 50 change: 0.0009966652 
#> iteration: 60 change: 0.0004381775 
#> iteration: 70 change: 0.0002279981 
#> iteration: 80 change: 0.0001378879 
#> iteration: 90 change: 9.47937e-05 
#> iteration: 100 change: 6.693825e-05 
#> iteration: 110 change: 4.804137e-05 
#> iteration: 120 change: 3.483073e-05 
#> iteration: 130 change: 2.541936e-05 
#> iteration: 140 change: 1.863291e-05 
#> iteration: 150 change: 1.369995e-05 
#> iteration: 160 change: 1.009469e-05 
#> iteration: 170 change: 7.44972e-06 
#> iteration: 180 change: 5.503994e-06 
#> iteration: 190 change: 4.069836e-06 
#> iteration: 200 change: 3.011221e-06 
#> iteration: 210 change: 2.228981e-06 
#> iteration: 220 change: 1.650506e-06 
#> iteration: 230 change: 1.222469e-06 
#> iteration: 240 change: 9.056073e-07 
#> iteration: 250 change: 6.709699e-07 
    all.equal(cxy1$centroids,cxy3$centroids) # Close, but no cigar.
#> [1] "Component “x”: Mean relative difference: 8.412556e-06"
#> [2] "Component “y”: Mean relative difference: 7.297346e-06"
    cxy4 <- cvt(dxy,verb=TRUE,tol=1e-14)
#> iteration: 10 change: 0.01090659 
#> iteration: 20 change: 0.005077311 
#> iteration: 30 change: 0.003679425 
#> iteration: 40 change: 0.00279814 
#> iteration: 50 change: 0.0009966652 
#> iteration: 60 change: 0.0004381775 
#> iteration: 70 change: 0.0002279981 
#> iteration: 80 change: 0.0001378879 
#> iteration: 90 change: 9.47937e-05 
#> iteration: 100 change: 6.693825e-05 
#> iteration: 110 change: 4.804137e-05 
#> iteration: 120 change: 3.483073e-05 
#> iteration: 130 change: 2.541936e-05 
#> iteration: 140 change: 1.863291e-05 
#> iteration: 150 change: 1.369995e-05 
#> iteration: 160 change: 1.009469e-05 
#> iteration: 170 change: 7.44972e-06 
#> iteration: 180 change: 5.503994e-06 
#> iteration: 190 change: 4.069836e-06 
#> iteration: 200 change: 3.011221e-06 
#> iteration: 210 change: 2.228981e-06 
#> iteration: 220 change: 1.650506e-06 
#> iteration: 230 change: 1.222469e-06 
#> iteration: 240 change: 9.056073e-07 
#> iteration: 250 change: 6.709699e-07 
#> iteration: 260 change: 4.971776e-07 
#> iteration: 270 change: 3.684291e-07 
#> iteration: 280 change: 2.73037e-07 
#> iteration: 290 change: 2.023522e-07 
#> iteration: 300 change: 1.499714e-07 
#> iteration: 310 change: 1.111525e-07 
#> iteration: 320 change: 8.238307e-08 
#> iteration: 330 change: 6.10608e-08 
#> iteration: 340 change: 4.525758e-08 
#> iteration: 350 change: 3.354466e-08 
#> iteration: 360 change: 2.486325e-08 
#> iteration: 370 change: 1.842867e-08 
#> iteration: 380 change: 1.36594e-08 
#> iteration: 390 change: 1.012442e-08 
#> iteration: 400 change: 7.50429e-09 
#> iteration: 410 change: 5.562236e-09 
#> iteration: 420 change: 4.122775e-09 
#> iteration: 430 change: 3.055837e-09 
#> iteration: 440 change: 2.265015e-09 
#> iteration: 450 change: 1.67885e-09 
#> iteration: 460 change: 1.24438e-09 
#> iteration: 470 change: 9.223469e-10 
#> iteration: 480 change: 6.836529e-10 
#> iteration: 490 change: 5.0673e-10 
#> iteration: 500 change: 3.755944e-10 
#> iteration: 510 change: 2.783931e-10 
#> iteration: 520 change: 2.063473e-10 
#> iteration: 530 change: 1.529479e-10 
#> iteration: 540 change: 1.133663e-10 
#> iteration: 550 change: 8.402807e-11 
#> iteration: 560 change: 6.228292e-11 
#> iteration: 570 change: 4.616474e-11 
#> iteration: 580 change: 3.421732e-11 
#> iteration: 590 change: 2.536227e-11 
#> iteration: 600 change: 1.879973e-11 
#> iteration: 610 change: 1.393496e-11 
#> iteration: 620 change: 1.032771e-11 
#> iteration: 630 change: 7.655049e-12 
#> iteration: 640 change: 5.675194e-12 
#> iteration: 650 change: 4.205176e-12 
#> iteration: 660 change: 3.117463e-12 
#> iteration: 670 change: 2.310835e-12 
#> iteration: 680 change: 1.71244e-12 
#> iteration: 690 change: 1.268629e-12 
#> iteration: 700 change: 9.415814e-13 
#> iteration: 710 change: 6.971148e-13 
#> iteration: 720 change: 5.167585e-13 
#> iteration: 730 change: 3.830477e-13 
#> iteration: 740 change: 2.840969e-13 
#> iteration: 750 change: 2.113605e-13 
#> iteration: 760 change: 1.561621e-13 
#> iteration: 770 change: 1.159535e-13 
#> iteration: 780 change: 8.462005e-14 
#> iteration: 790 change: 6.340892e-14 
#> iteration: 800 change: 4.720175e-14 
#> iteration: 810 change: 3.510061e-14 
#> iteration: 820 change: 2.553899e-14 
#> iteration: 830 change: 1.820774e-14 
#> iteration: 840 change: 1.422646e-14 
#> iteration: 850 change: 1.021782e-14 
#> 
    cxy5 <- cvt(dxy,stopcrit="m",verb=TRUE,maxit=600)
#> iteration: 10 change: 0.01090659 
#> iteration: 20 change: 0.005077311 
#> iteration: 30 change: 0.003679425 
#> iteration: 40 change: 0.00279814 
#> iteration: 50 change: 0.0009966652 
#> iteration: 60 change: 0.0004381775 
#> iteration: 70 change: 0.0002279981 
#> iteration: 80 change: 0.0001378879 
#> iteration: 90 change: 9.47937e-05 
#> iteration: 100 change: 6.693825e-05 
#> iteration: 110 change: 4.804137e-05 
#> iteration: 120 change: 3.483073e-05 
#> iteration: 130 change: 2.541936e-05 
#> iteration: 140 change: 1.863291e-05 
#> iteration: 150 change: 1.369995e-05 
#> iteration: 160 change: 1.009469e-05 
#> iteration: 170 change: 7.44972e-06 
#> iteration: 180 change: 5.503994e-06 
#> iteration: 190 change: 4.069836e-06 
#> iteration: 200 change: 3.011221e-06 
#> iteration: 210 change: 2.228981e-06 
#> iteration: 220 change: 1.650506e-06 
#> iteration: 230 change: 1.222469e-06 
#> iteration: 240 change: 9.056073e-07 
#> iteration: 250 change: 6.709699e-07 
#> iteration: 260 change: 4.971776e-07 
#> iteration: 270 change: 3.684291e-07 
#> iteration: 280 change: 2.73037e-07 
#> iteration: 290 change: 2.023522e-07 
#> iteration: 300 change: 1.499714e-07 
#> iteration: 310 change: 1.111525e-07 
#> iteration: 320 change: 8.238307e-08 
#> iteration: 330 change: 6.10608e-08 
#> iteration: 340 change: 4.525758e-08 
#> iteration: 350 change: 3.354466e-08 
#> iteration: 360 change: 2.486325e-08 
#> iteration: 370 change: 1.842867e-08 
#> iteration: 380 change: 1.36594e-08 
#> iteration: 390 change: 1.012442e-08 
#> iteration: 400 change: 7.50429e-09 
#> iteration: 410 change: 5.562236e-09 
#> iteration: 420 change: 4.122775e-09 
#> iteration: 430 change: 3.055837e-09 
#> iteration: 440 change: 2.265015e-09 
#> iteration: 450 change: 1.67885e-09 
#> iteration: 460 change: 1.24438e-09 
#> iteration: 470 change: 9.223469e-10 
#> iteration: 480 change: 6.836529e-10 
#> iteration: 490 change: 5.0673e-10 
#> iteration: 500 change: 3.755944e-10 
#> iteration: 510 change: 2.783931e-10 
#> iteration: 520 change: 2.063473e-10 
#> iteration: 530 change: 1.529479e-10 
#> iteration: 540 change: 1.133663e-10 
#> iteration: 550 change: 8.402807e-11 
#> iteration: 560 change: 6.228292e-11 
#> iteration: 570 change: 4.616474e-11 
#> iteration: 580 change: 3.421732e-11 
#> iteration: 590 change: 2.536227e-11 
#> iteration: 600 change: 1.879973e-11 
    all.equal(cxy4$centroids,cxy5$centroids) # TRUE
#> [1] 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
#> [1] TRUE
 # \dontrun{}