CVT_METRIC is a MATLAB program which computes 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 )We assume that A varies spatially, but we would prefer to simplify this variation in a manner that saves us computational effort, while allowing us to recover the variational behavior if we are willing to use a finer spatial sampling.
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.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
CVT_METRIC is available in a MATLAB version.
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_NONUNIFORM, a MATLAB library which allows the user to watch the evolution of a CVT computed over a 1D interval with a nonuniform density.
CVT_2D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit square [0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.
CVT_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.
CVT_DEMO, a MATLAB library which allows the user to generate a CVT over several geometric regions using uniform or nonuniform density.
CVTM_1D, a MATLAB program which estimates a mirror-periodic centroidal Voronoi Tessellation (CVTM) in the periodic interval [0,1], using a version of Lloyd's iteration.
CVTP_1D, a MATLAB program which estimates a periodic centroidal Voronoi Tessellation (CVTP) in the periodic interval [0,1], using a version of Lloyd's iteration.
FLORIDA_CVT_GEO, MATLAB programs which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.
LCVT, a MATLAB library which computes a "Latinized" Centroidal Voronoi Tessellation.
TEST_TRIANGULATION, a MATLAB library which defines the geometry of a number of sample regions.
The following files contain functions to evaluate various simple metrics:
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.
You can go up one level to the MATLAB source codes.