CVT_REFINE
Refine a Centroidal Voronoi Tessellation

CVT_REFINE is a FORTRAN90 library which attempts to "refine" a centroidal Voronoi tessellation (CVT).

CVT_REFINE considers the following problem. We suppose that we have computed a centroidal Voronoi tessellation associated with N1 cell generators. We now wish to "refine" this tessellation, by increasing the number of generators by N2. The stipulations are that the old generators will be fixed in place, and that the new generators will be placed initially at random in the region, and then allowed to adjust themselves using the usual CVT iteration.

However, without some care, this process will not produce very good results, since the old fixed generators will "block" the motion of the new generators seeking areas of "lower pressure". To enable the system to reach a lower energy equilibrium, we use a weight vector to initially reduce the influence of the old generators, and then to gradually "turn them on" until they are equal in influence to the new generators (though still constrained not to move).

The code includes the weight vector that was developed in the CVT_SIZE program and the idea of fixing points that was developed in the CVT_FIXED program.

A new idea was to include a maximum influence distance cvt_cutoff. The idea was that spatial points that were further than this cutoff distance to a generator were not assigned any generator at all. This was another mechanism that would allow us to control the sizes of the Voronoi cells, and allow new generators to move more freely around old, fixed generators.

Animations:

Just to check out the use of the cutoff value, we set 10 points going with a fixed cutoff value. Click HERE to see the CVT_CUTOFF movie.

For our second movie, we follow 10 generators for 100 iterations, then fix them in place. Our goal is to refine the current placement of points by adding some new points and driving them to a CVT equilibrium. We add 10 new generators. By a programming mistake, these points all started out at (0,0), but that just makes the point more dramatically. We make room for the new points to move about by using weights. These start out giving the new points an advantage, but at certain time steps we cut this back until at the end we are back to an unweighted scheme. Click HERE to see the CVT_10PLUS10 movie.

Licensing:

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

Languages:

CVT_REFINE is available in a FORTRAN90 version.

Related Data and Programs:

PBMLIB, a FORTRAN90 library which supplies some routines to create crisp and relatively small binary PPM images of the CVT regions.

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

Source Code:

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

Examples and Tests:

• cvt_refine_test.f90, a sample problem.
• cvt_refine_test.sh, commands to compile, link and run the sample problem.
• cvt_refine_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_WEIGHT takes one step of the weighted CVT iteration.
• CVT_SIZE_TO_WEIGHT computes appropriate CVT weights from desired volumes.
• 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_WEIGHT finds the generator with least weighted distance to X.
• GENERATOR_INIT initializes the Voronoi cell generators.
• GET_UNIT returns a free FORTRAN unit number.
• 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.
• PPM_CHECK_DATA checks pixel data.
• PPMB_WRITE writes a binary portable pixel map file.
• R8VEC_DIST_L2 returns the L2 distance between a pair of real vectors.
• R8VEC_PRINT prints a real vector.
• 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.
• S_TO_I4VEC converts an string of characters into an I4VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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