CVT_METRIC
CVT Calculation With Varying Metric

CVT_METRIC is a collection of MATLAB routines which carry out the computation of a CVT (Centroidal Voronoi Tessellation) calculation under a spatially varying metric.

What we are saying is that the distance between two vectors a and b is no longer simply the Euclidean distance, but rather a quadratic form involving a spatially varying, positive definite symmetric matrix that represents the metric:

        d(a,b) = ( a - b )' * A * ( a - b )
      

The metric function is distinct from the density function, which can also be used in these kinds of problems. The density function is weaker, and corresponds to a metric whose matrix at any point is a multiple of the identity matrix. A density function approach cannot result in the more interesting anisotropic effects that an arbitrary metric produces.

Related Data and Programs:

CVT_1D_NONUNIFORM is a MATLAB library of routines which allows the user to watch the evolution of a CVT computed over a 1D interval with a nonuniform density.

CVT_DEMO is a MATLAB library of routines which allows the user to generate a CVT over several geometric regions using uniform or nonuniform density.

LCVT is a MATLAB library of routines which compute a "Latinized" Centroidal Voronoi Tessellation.

TEST_TRIANGULATION is a MATLAB library of routines which define the geometry of a number of sample 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,
   ../../pdf/aurenhammer.pdf
2. Qiang Du, Vance Faber, Max Gunzburger,
   Centroidal Voronoi Tessellations: Applications and Algorithms,
   SIAM Review, Volume 41, 1999, pages 637-676.

Source Code:

• cvt_square_metric.m, the text of the MATLAB function.
• square_uniform.m, the routine which returns sample points from the square.
• voronoi_new.m, an improved, unreleased version of the Voronoi command that does a better job of handling the semi-infinite Voronoi edges.

Examples and Tests:

The following files contain functions to evaluate various simple metrics:

• metric_01.m, the identity matrix.
• metric_02.m, the matrix [9,0;0,1].
• metric_03.m, the matrix [1,0;0,100].
• metric_04.m, the matrix [1,0;0,1] * (0.2+sin(2*pi*x)**2 * sin(2*pi*y)**2).
• metric_05.m, the matrix [2,3;3,5].

Here are images of CVT point sets. These are crude calculations, with a relatively low number of sample points and iterations. This is partly because I haven't figured out how to optimize these calculations in MATLAB.

• metric_03.png, 200 generators, using 1600 sample points, and 20 iterations, with the constant metric [1,0;0,100].
• metric_04.png, 200 generators, using 1600 sample points, and 20 iterations, with the metric matrix [1,0;0,1] * (0.2+sin(2*pi*x)**2 * sin(2*pi*y)**2).

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