CVT_SIZE
CVT with Prescribed Cell Sizes

CVT_SIZE is a FORTRAN90 library which attempts to compute a (weighted) centroidal Voronoi tessellation (CVT) in which each cell has a desired prescribed size.

Normally, given arbitrary initial data and a constant density, the CVT would comprise cells of roughly equal area. This program modifies the CVT iteration, allowing the user to specify a relative cell size for each cell. Thus, if the region has area 100, and we make a tessellation of two cells, and we specify weights of 1 and 3, we would hope for the cells to be computed with areas of 25 and 75 units respectively.

Internally, the desired cell sizes are normalized, and then the appropriate root is taken to account for the dimensionality of the space. (In 2 space, you take the square root of the normalized cell size, for instance.) This gives you the weight to be assigned to a generator.

Then, when it is time to compute the distance for a sample point to the center of each Voronoi cell and take the "closest" one, we divide each cell's distance by the adjusted weight. This has the effect of making cells with a larger weight seem closer than they really are, and hence they attract more sample points, and end up with a larger area.

If only a small number of generators are used, or if the weights vary greatly in size, the effects of local geometry and curvature come into play, and the chosen weights produce areas that are only roughly what is desired. Increasing the number of cells being used seems to produce more regular behavior, with the cells tending to have the areas requested by the user.

Some of the activity on this project was inspired by a query from Professor Alexandru Telea, of the Department of Mathematics and Computer Science, Technische Universiteit Eindhoven.

Early versions of the code required the PS_WRITE library in order to create PostScript images of the CVT regions. These images were made by sampling the region, and drawing little circle of the color of the nearest generator. The resulting images were charming, but fuzzy, slow to render, and enormous in size.

Licensing:

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

Related Data and Programs:

PBMLIB is a FORTRAN90 library which can create crisp and relatively small PPMB images of the CVT regions.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, 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,
   ../../publications/bgpb_2002.pdf
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, and Max Gunzburger,
   Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
   Parallel Computing,
   Volume 28, 2002, pages 1477-1500.

Source Code:

• cvt_size.f90, the source code.
• cvt_size.csh, commands to compile the source code.

Examples and Tests:

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

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.

Click HERE to see the CVT movie.

We ran the code on a variety of different sets of data.

• We ran a problem called cvt_1111133333 with 10 generators, with weights 1, 1, 1, 1, 1, 3, 3, 3, 3, 3.
• We ran a problem called cvt_123456789x with 10 generators, with weights 1, 2, 3, ..., 9, 10.
• We ran a problem called cvt_1to37 with 10 generators, with weights 1, 5, 9, ..., 37.
• We ran a problem called cvt_1to80 with 80 generators, with weights 1 through 80.
• We ran a problem called cvt_1to80 with 80 generators, with weights 1, 5, 9, ..., 317.
• We ran a problem called cvt_1to1024 with 11 generators, with weights 1, 2, 4, ..., 1024.

We made a sequence of calculations giving half the cells weight 1 and half weight 4. Increasing the number of generators seemed to show regular behavior.

• cvt_halfandhalf10 uses 10 generators.
• cvt_halfandhalf20 uses 20 generators.
• cvt_halfandhalf40 uses 40 generators.
• cvt_halfandhalf80 uses 80 generators.

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_SIZE_ITERATION takes one step of the CVT size 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_SIZE finds the Voronoi cell generator closest to a point X.
• GENERATOR_INIT initializes the Voronoi cell generators.
• GET_UNIT returns a free FORTRAN unit number.
• 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_UNIFORM returns a scaled pseudorandom I4.
• R82VEC_DIST_L2 returns the L2 distance between a pair of real 2-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.

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