CVT_FIXED
CVT with Some Generators Fixed

CVT_FIXED is a FORTRAN90 library which can be used to update a centroidal Voronoi tessellation (CVT).

CVT_FIXED attempts to compute a new CVT starting from an existing one, updating some of the cell generators, but leaving designated cell generators fixed. The updated cell generators are replaced by the centroid of their cells.

The user specifies which generators are to be fixed, and which may be updated. Watching an animation of the evolution of the system, the cells corresponding to fixed generators comprise obstacles, and the free cells behave like soap bubbles that flow around the obstacles, trying to balance pressures (cell volume).

A second feature has been added, a maximum influence distance. This is the variable "cutoff_dist". When sampling the region, if the nearest generator is further than this distance, we don't assign the point at all.

The code includes the weight vector that was developed in the CVT_SIZE program. Here, it is anticipated that the weight vector would be used in situations where an initial set of generators has been computed, and is to be augmented. The initial set of generators is held fixed, and the new points are to be allowed to arrange themselves. However, if we place the new points at random, they will get trapped in local minima. By using the weight vector, we can start out with the initial generators having very little influence, and then gradually ramp their weights up to equality with the new points.

We were interested in watching the behavior of the Voronoi cells over "time". We set up a problem with 10 generators, with weights 1, 2, 3, ..., 10. We started with random initial locations for the generators, and carried out 100 iterations of the CVT code. We saved a PPMB file containing an image of each step, used the CJPEG program to convert these to JPEG files with consecutive file names, fed that into QuickTime Pro to create an animation, and saved the result as an MPEG-4 file.

Licensing:

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

Languages:

CVT_FIXED is available in a FORTRAN90 version.

Related Data and Programs:

PPMB, a data format which is used for the images of the CVT regions.

PBMLIB, a FORTRAN90 library which is used to create the graphics files.

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 and 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, and Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.
4. Lili Ju, Qiang Du, and Max Gunzburger,
   Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
   Parallel Computing,
   Volume 28, 2002, pages 1477-1500.

Source Code:

• cvt_fixed.f90, the source code.
• cvt_fixed.sh, commands to compile the source code.

Examples and Tests:

• cvt_fixed_test.f90, a sample problem. To run the various cases below, you have to make changes to the text of this file.
• cvt_fixed_test.sh, commands to compile, link and run the sample problem.
• cvt_fixed_test.txt, the output file.

List of Routines:

• ANGLE_TO_RGB returns a color on the perimeter of the color hexagon.
• CH_IS_DIGIT returns .TRUE. if a character is a decimal digit.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• CVT_ITERATION takes one step of the CVT iteration.
• DIGIT_INC increments a decimal digit.
• DIGIT_TO_CH returns the character representation of a decimal digit.
• FILE_NAME_INC generates the next filename in a series.
• FIND_CLOSEST finds the nearest R point to each S point.
• FIND_CLOSEST_SIZE finds the Voronoi cell generator closest to a point X.
• GENERATOR_INIT initializes the Voronoi cell generators.
• HEXCOL returns a color on the perimeter of the color hexagon.
• I4_LOG_2 returns the integer part of the logarithm base 2 of |I|.
• I4_TO_ANGLE maps integers to points on a circle.
• I4_TO_RGB maps integers to RGB colors.
• R8VEC_DIST_L2 returns the L2 distance between a pair of vectors.
• RANDOM_INITIALIZE initializes the FORTRAN 90 random number seed.
• REGION_PLOT_PPMB makes a binary PPM plot of the CVT regions.
• REGION_SAMPLER returns a sample point in the physical region.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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