CCVT_BOX
Animated Constrained CVT Algorithm

CCVT_BOX is a MATLAB program which allows the user to specify certain parameters, and then creates and animates a Centroidal Voronoi Tessellation of points in a 2D box. After each iteration, points near the boundary are projected onto the boundary.

The data that the user may set includes:

• N, the number of points to generate,
• NPP, the number of (equally spaced) sample points to be used along the boundary of the box;
• INIT, initialize the points:
  • file, by reading data from file;
  • 'GRID', picking points from a grid;
  • 'HALTON', from a Halton sequence;
  • 'RAND', using MATLAB's RAND function;
  • 'UNIFORM', using a simple uniform RNG;
• IT_MAX, the maximum number of iterations;
• IT_FIXED, the number of iterations for which each set of sample points should be used (between 1 and IT_MAX);
• SAMPLE, how to conduct the sampling:
  • 'GRID', picking points from a grid;
  • 'HALTON', from a Halton sequence;
  • 'RAND', using MATLAB's RAND function;
  • 'UNIFORM', using a simple uniform RNG;
• SAMPLE_NUM, the number of sampling points:
• MOVIE_NAME, the number the animation file to be created.

Licensing:

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

Languages:

CCVT_BOX is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

AVI, a data directory which contains an animation of the behavior of the generator points during the iteration, as computed by CCVT_BOX.

CCVT_REFLECT, a MATLAB program which tries to achieve the same results as CCVT_BOX but using a "reflection" idea to force points onto the boundary of the region.

CVT, a MATLAB library which can create CVT's.

CVT, a dataset directory which contains files describing a number of CVT's.

CVT_1D_LLOYD, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density.

CVT_1D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the interval [0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_DATASET, a MATLAB program which creates a CVT dataset.

Author:

The FORTRAN version of CCVT_BOX was written by Lili Ju.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
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, Number 4, December 1999, pages 637-676.
4. Qiang Du, Max Gunzburger, Lili Ju,
   Meshfree, Probabilistic Determination of Point Sets and Support Regions for Meshfree Computing,
   Computer Methods in Applied Mechanics in Engineering,
   Volume 191, 2002, pages 1349-1366.
5. 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:

• ccvt_box.m gets information from the user, creates the CVT and saves the animation.
• ch_cap.m capitalizes a single character.
• cvt_energy.m estimates the CVT energy of a given pointset.
• cvt_sample.m returns sample points.
• cvt_write.m writes a CVT dataset to a file.
• data_read.m reads data from a file.
• file_exist.m is true if a file exists.
• file_delete.m deletes a file.
• find_closest.m finds the Voronoi cell generator closest to a point X.
• get_seed.m returns a seed for the random number generator.
• halham_leap_check.m checks LEAP for a Halton or Hammersley sequence.
• halham_n_check.m checks N for a Halton or Hammersley sequence.
• halham_dim_num_check.m checks NDIM for a Halton or Hammersley sequence.
• halham_seed_check.m checks SEED for a Halton or Hammersley sequence.
• halham_step_check.m checks STEP for a Halton or Hammersley sequence.
• halton_base_check.m checks BASE for a Halton sequence.
• i4_to_halton_sequence.m next N elements of an NDIM-dimensional Halton sequence
• points_eps.m creates a PostScript image of a set of points.
• prime.m returns the N-th prime number.
• r8_huge.m returns a very large R8 value.
• r8mat_transpose_print.m prints the transpose of an R8MAT, with an optional title.
• r8mat_transpose_print_some.m prints the transpose of some of an R8MAT, with an optional title.
• r8mat_uniform_01.m returns a unit pseudorandom R8MAT.
• random_initialize.m initializes the MATLAB random number seed.
• s_eqi.m is TRUE if two strings are equal, ignoring case.
• s_len_trim.m returns the length of a string to the last nonblank.
• timestamp.m prints the current YMDHMS date as a timestamp.
• timestring.m prints the current YMDHMS date into a string.
• tuple_next_fast.m computes the next element of a tuple space, "fast".

Examples and Tests:

• ccvt_box_output.txt, the output file.
• initial.txt, a TABLE file containing the initial CVT generators.
• initial.png, a PNG image of the initial CVT generators.
• final.txt, a TABLE file containing the final CVT generators.
• final.png, a PNG image of the final CVT generators.

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