CVT_FIXED2
CVT with Some Generators Fixed

CVT_FIXED2 is a FORTRAN90 library which generates a centroidal Voronoi tessellation (CVT), with some nodes fixed.

The "interesting" routine in the library is CVT_FIXED_ITERATION, which updates an ongoing CVT calculation, but does not adjust certain nodes that have been designated by the user.

The user also supplies a subroutine that samples the domain of interest. If the domain is the unit square, say, then it is enough to return points uniformly distributed in [0,1]. However, the sampling subroutine interface makes it simple to handle regions which are not the unit square, or which have irregular boundaries, or holes, or for which a nonuniform probability density is to be used.

The sample problem illustrates the use of this routine to generate a mesh of points in a region that has two hexagonal holes. The user has set a number of points along the boundary, and on the holes, and these points are not to be moved. More points are to be generated within the region, and these, together with the fixed points, will constitute the mesh. The user also supplies a routine that returns sample points within the double hexagonal hole region.

Licensing:

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

Languages:

CVT_FIXED2 is available in a FORTRAN90 version.

Related Data and Programs:

PLOT_POINTS, a FORTRAN90 program which was used to plot the points and mesh.

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_fixed2.f90, the source code.
• cvt_fixed2.sh, commands to compile the source code.

Examples and Tests:

• cvt_fixed2_test.f90, a sample problem.
• cvt_fixed2_test.sh, commands to compile, link and run the sample problem.
• cvt_fixed2_test.txt, the output file.

The CVT_FIXED2_test program can be used to handle the "double hexagonal hole" region. A few lines in source code file "cvt_fixed2_test.f90" must be set so that the appropriate files are read and written, and so that 511 nodes are created by the run. Files you may copy include:

• double_hex.txt, a set of 96 fixed nodes for the double hexagonal hole region.
• double_hex.png, a PNG image of the fixed nodes.
• double_hex_cvt.txt, a set of 511 nodes computed by CVT_FIXED2_test after 80 iterations.
• double_hex_cvt.png, a PNG image of the Delaunay mesh induced by the nodes.

The CVT_FIXED2_test program can be used to handle a second version of the "double hexagonal hole" region which uses half as many fixed nodes. A few lines in source code file "cvt_fixed2_test.f90" must be set so that the appropriate files are read and written, and so that 139 nodes are created by the run. Files you may copy include:

• double_hex2.txt, a set of 48 fixed nodes for the double hexagonal hole region.
• double_hex2.png, a PNG image of the fixed nodes.
• double_hex2_cvt.txt, a set of 139 nodes computed by CVT_FIXED2_test after 1000 iterations.
• double_hex2_cvt.png, a PNG image of the Delaunay mesh induced by the nodes.

List of Routines:

• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• CVT_FIXED_ITERATION takes one step of the CVT iteration.
• DTABLE_DATA_READ reads real table data from a file.
• DTABLE_DATA_WRITE writes a real table dataset to a file.
• DTABLE_HEADER_READ reads header data from a file.
• DTABLE_HEADER_WRITE writes the table header data to a file.
• FIND_CLOSEST finds the Voronoi cell generator closest to a point X.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_ROW_COUNT counts the number of row records in a file.
• GET_UNIT returns a free FORTRAN unit number.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING writes the current YMDHMS date into a string.

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