CVT_2D_SAMPLING
Centroidal Voronoi Tessellation in Unit Square

CVT_2D_SAMPLING is a MATLAB program which allows the user to carry out steps of Lloyd's iteration for approximating a Centroidal Voronoi Tessellation (CVT) in the unit square.

The determination of the Voronoi regions is carried out using sampling. This means that the convergence of the iteration is influenced by the accuracy of the estimates provided by sampling.

This code stopped working when MATLAB pulled the DSEARCH function (please don't do things like this any more, MathWorks!); I have updated it now to use DSEARCHN so it works again.

Usage:

cvt_2d_sampling ( g_num, it_num, s_num )

• g_num is the number of generators;
• it_num is the number of iterative steps to take.
• s_num is the number of sample points in the unit square used to estimate the Voronoi regions. A value between 1,000 and 100,000 is typical.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

CVT_2D_SAMPLING is available in a MATLAB version and a Python version.

Related Data and Programs:

CCVT_BOX, a MATLAB program which constructs a modified CVT in which some points are forced to lie on the boundary.

CCVT_REFLECT, a MATLAB program which tries to construct a modified CVT in which some points are forced to lie on the boundary, using a reflection idea.

CVT, a MATLAB library which computes CVT's.

CVT, a dataset directory which contains a variety of examples of CVT datasets.

CVT_1D_LLOYD, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using exact techniques to determine the Voronoi regions.

CVT_1D_NONUNIFORM, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation in 1 dimension, under a nonuniform density, and plots the evolution of the locations of the generators during the iteration;

CVT_1D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_3D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit cube [0,1]x[0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

CVT_DATASET, a MATLAB program which can create a CVT dataset.

CVT_DEMO, a MATLAB program which demonstrates a CVT calculation.

CVT_SQUARE_NONUNIFORM, a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a nonuniform density.

CVTM_1D, a MATLAB program which estimates a mirror-periodic centroidal Voronoi Tessellation (CVTM) in the periodic interval [0,1], using a version of Lloyd's iteration.

CVTP_1D, a MATLAB program which estimates a periodic centroidal Voronoi Tessellation (CVTP) in the periodic interval [0,1], using a version of Lloyd's iteration.

FLORIDA_CVT_GEO, MATLAB programs which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.

LCVT , a MATLAB library which computes a "Latinized" Centroidal Voronoi Tessellation.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
2. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.

Source Code:

• cvt_2d_sampling.m

Examples and Tests:

• cvt_2d_sampling.png a PNG image of the Voronoi diagram and Delaunay triangulation for a set of 35 points on the 10th step of an iteration.

You can go up one level to the MATLAB source codes.