CVT_MOVIE5
Animated CVT Algorithm

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

This particular computation occurs in the same region of interesting shape that was used for CVT_MOVIE3. However, in this case, there are three important differences:

• the points were initialized by a hexagonal grid.
• a few points at corners were fixed in position.
• the CVT sampling procedure used a "fat" region; but when centroids were lured out of the true region, they were projected back to the boundary.

The goal of the calculation was to modify the CVT iteration so that generators would be produced on the boundary of the region, and in a fairly natural way. The calculation was done by CVT_MOVIE5_DATA, and the results stored in 101 text files.

The CVT_MOVIE5 program illustrates the result of the calculation by reading in the data files, drawing the Voronoi diagram and the region boundary, and creating 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.

Animation:

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

Licensing:

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

Languages:

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

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

Source Code:

• ch_is_digit.m is TRUE if a character represents a digit.
• cvt_movie5.m the main program for the creation of the movie.
• digit_inc.m increments a character that represents a digit.
• file_name_inc.m "increments" a file name that has numeric characters in it.
• p08_boundary_segment_length.m returns the number of points necessary to draw a boundary segment of the P08 region.
• p08_boundary_segment.m returns points on a boundary segment of the P08 region.
• p08_boundary_segment_num.m returns the number of boundary segments for the P08 region.
• s_len_trim.m returns the length of a string to the last nonblank.
• timestamp.m prints the current YMDHMS date as a timestamp.

Data and Tests:

• cvt_movie5_output.txt the output file.

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