CVT_DEMO
Interactive Graphic CVT Demonstrations

CVT_DEMO is a collection of MATLAB routines which use interaction and graphics to demonstrate properties of the CVT (Centroidal Voronoi Tessellation) calculation.

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.

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.

CVT_SQUARE_UNIFORM

CVT_SQUARE_UNIFORM is a MATLAB function, with calling sequence

cvt_square_uniform ( n, sample_num )
Here, n is the number of generators (default 100) and sample_num is the number of sample points (default = 1000*n ). Starting from a random initial configuration, another step of the CVT iteration is carried out each time the user hits RETURN. The MATLAB routines trimesh and voronoi are used to simultaneously display the Voronoi diagram and Delaunay triangulation associated with the generators. Moreover, the nearest-neighbor search and centroid computation are carried out efficiently using MATLAB's Delaunay search and rapid array accumulation.

Source Code:

CVT_ELLIPSE_UNIFORM

CVT_ELLIPSE_UNIFORM is a MATLAB function, with calling sequence

cvt_ellipse_uniform ( n, sample_num )
This works the same as the code for the square, except that we are now working in a more interesting region, namely, the ellipse defined by x'*A*x<=36 with A = [ 9, 6; 6, 20 ]; The only tricky thing we have to do is write a routine that returns sample points from the region.

Source Code:

CVT_CIRCLE_NONUNIFORM

CVT_CIRCLE_NONUNIFORM is a MATLAB function, with calling sequence

cvt_circle_nonuniform ( n, sample_num )
The spatial region is the unit circle, but a nonuniform density is applied to that region. The density is implicitly defined by the sampling routine, which returns many more points near the circumference than near the center of the circle. The result is that, during the CVT iteration, the generators arrange themselves more densely towards the outer part of the circle.

Source Code:

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

Last revised on 20 May 2006.