CVT_2D_SAMPLING
Centroidal Voronoi Tessellation (CVT) in Unit Square

CVT_2D_SAMPLING is a Python 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 only carried out approximately, using sampling. This means that the convergence of the iteration is influenced by the accuracy of the estimates provided by sampling.

Usage:

cvt_2d_sampling ( g_num, it_num, s_1d_num )

• g_num is the number of generators;
• it_num is the number of iterative steps to take.
• s_1d_num sets the 1d sampling density. The program will create a sample grid that is s_1d_num points on a side. Thus, a value of s_1d_num=1,000 will result in 1,000,000 sample points.

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:

CVT_1D_LLOYD, a Python 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.

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

FLORIDA_CVT_POP, Python programs which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based on population density.

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

Examples and Tests:

• initial.png a PNG image of the Voronoi diagram and Delaunay triangulation for a set of 16 points on the 0th step.
• final.png a PNG image of the Voronoi diagram and Delaunay triangulation for a set of 16 points on the 19th step.

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