CVTP
Centroidal Voronoi Tessellation on Logical Torus

CVTP is a FORTRAN90 library which creates CVTP's, that is, Centroidal Voronoi Tessellations of a periodic region.

A 2D unit logical torus is the unit square, but with "wraparound". This is the connectivity frequently seen in video games, in which a spaceship flies off the top of the screen and immediately reappears at the bottom of the screen. In the general M-dimensional case, the extreme minimum and maximum values of each coordinate are identified, and modular arithmetic may be used to determine distances.

Licensing:

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

Languages:

CVTP is available in a FORTRAN90 version.

Related Data and Programs:

CVT, a FORTRAN90 library which computes a Centroidal Voronoi Tessellation.

CVT_DATASET, a FORTRAN90 program which defines and computes a CVT.

CVTP, a dataset directory which contains examples of CVTP's, that is, Centroidal Voronoi Tessellations on a periodic domain.

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:

• cvtp.f90, the source code.

Examples and Tests:

• cvtp_test.f90, a sample calling program.
• cvtp_test.txt, the output from a run of the sample program.

CVT_1X1 is a nonperiodic CVT of 400 points on the region [0,1]x[0,1]:

• cvt_1x1.txt, the list of point coordinates.
• cvt_1x1.png, a PNG image of the set.
• cvt_1x1_double.png, a plot of the data (X,Y) and (X+1,Y) together on the domain [0,2]x[0,1] showing a boundary effect at X=1.

CVT_1X2 is a nonperiodic CVT of 400 points on the region [0,1]x[0,2]:

• cvt_1x2.txt, the list of point coordinates.
• cvt_1x2.png, a PNG image of the set.
• cvt_1x2_double.png, a plot of the data (X,Y) and (X+1,Y) together on the domain [0,2]x[0,2] showing a boundary effect at X=1.

CVTP_1X1 is a periodic CVT of 400 points on the region [0,1]x[0,1]:

• cvtp_1x1.txt, the list of point coordinates.
• cvtp_1x1.png, a PNG image of the set.
• cvtp_1x1_double.png, a plot of the data (X,Y) and (X+1,Y) together on the domain [0,2]x[0,1] showing no boundary effect at X=1.

CVTP_1X2 is a periodic CVT of 400 points on the region [0,1]x[0,2]:

• cvtp_1x2.txt, the list of point coordinates.
• cvtp_1x2.png, a PNG image of the set.
• cvtp_1x2_double.png, a plot of the data (X,Y) and (X+1,Y) together on the domain [0,2]x[0,2] showing no boundary effect at X=1.

List of Routines:

• CVTP_FIND_CLOSEST finds the Voronoi cell generator closest to a point X.
• CVTP_ITERATION takes one step of the CVT iteration.
• CVTP_REGION_SAMPLER returns a sample point in the physical region.
• GET_UNIT returns a free FORTRAN unit number.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8MAT_WRITE writes an R8MAT file.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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