CVT_SQUARE_UNIFORM
Centroidal Voronoi Tesselation in Square with Uniform Density


CVT_SQUARE_UNIFORM is a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) in a square with uniform density.

As you watch the CVT develop, for instance, you will be able to guess something about the angle of intersection between the boundaries of the region, and the edges of Voronoi regions.

CVT_SQUARE_UNIFORM works in a square with a uniform density. The function starts from a random initial configuration. Another step of the CVT iteration is carried out each time the user hits RETURN. The MATLAB routines trimesh() and voronoi() are used to simultaneously display the Voronoi diagram and Delaunay triangulation associated with the generators. Moreover, the nearest-neighbor search and centroid computation are carried out efficiently using MATLAB's Delaunay search and rapid array accumulation. The calling sequence is:

[ p, t ] = cvt_square_uniform ( n, sample_num, delaunay_display )

Licensing:

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

Languages:

CVT_SQUARE_UNIFORM is available in a MATLAB 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_1D_LLOYD, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density.

CVT_1D_NONUNIFORM, a MATLAB library which allows the user to watch the evolution of a CVT computed over a 1D interval with a nonuniform density.

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_2D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit square [0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_CIRCLE_NONUNIFORM, a MATLAB program which calculates a nonuniform Centroidal Voronoi Tessellation (CVT) over a circle.

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 creates a CVT dataset.

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

cvt_square_uniform_test

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.

DISCRETE_PDF_SAMPLE_2D, a MATLAB program which demonstrates how to construct a Probability Density Function (PDF) from a table of sample data, and then to use that PDF to create new samples.

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.

TEST_TRIANGULATION, a MATLAB library which defines the geometry of a number of sample regions.

VORONOI_PLOT, a MATLAB program which plots the Voronoi neighborhoods of points using L1, L2, LInfinity or arbitrary LP norms;

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. John Burkardt, Max Gunzburger, Janet Peterson, Rebecca Brannon,
    User Manual and Supporting Information for Library of Codes for Centroidal Voronoi Placement and Associated Zeroth, First, and Second Moment Determination,
    Sandia National Laboratories Technical Report SAND2002-0099,
    February 2002.
  3. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review,
    Volume 41, Number 4, December 1999, pages 637-676.

Source Code:


Last revised on 23 December 2018.