Animated CVT Algorithm

CVT_MOVIE4 is a MATLAB program which animates the generation of a Centroidal Voronoi Tessellation (CVT) dataset.

The action takes place in a square; however, a nonuniform density function is applied, which effectively increases the "weight" of regions in the corners; for this iterative algorithm, the effect of the density function is that many more sample points will come from the corners than from the center. The CVT cells will correspondingly tend to migrate away from the center.

The data that the user may set includes:

The program proceeds to create a series of JPG files, each containing one frame of the animation. It is possible to create an animation by using software such as Apple QuickTime.


One version of a sample animation file is stored in the MPEG-4 format. You can see the MP4 animation.


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


CVT_MOVIE4 is available in a MATLAB version.

Related Data and Programs:

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

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.

FILE_NAME_SEQUENCE, a MATLAB program which demonstrates four ways to generate a sequence of filenames.

PEAK_MOVIE, a MATLAB program which creates the pieces of an animation, one frame at a time. Each frame is independently created and saved as a JPEG file.


  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 and Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review, Volume 41, 1999, pages 637-676.

Source Code:

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

Last revised on 31 August 2005.