USA_CVT_GEO
Geometric Centroidal Voronoi Tessellation of the US


USA_CVT_GEO, MATLAB programs which explore the creation of a centroidal Voronoi Tessellation (CVT) of the continental United States, based solely on geometric considerations.

The main data item needed is a list of the longitudes and latitudes of points that form a polygon that approximates the boundary of the United States. Having such a polygon makes it possible to draw points uniformly at random from the interior of the US. This makes it possible to estimate computationally the value of certain geometric data including area, centroids, and the centroidal Voronoi Tessellation.

The function usa_sample_geo() can return a set of points drawn uniformly at random from the interior of the US.

Using the border polygon definition, usa_point_display() can display a set of points representing locations in the US, specified by their longitude and latitude.

Given a set of points in the US, usa_voronoi_display() can show the resulting Voronoi diagram. Note that, because of shortcomings in MATLAB's voronoi() command, some tricks had to be used to get a satisfactory plot. In particular, because rays to infinity are not returned, an auxilliary frame of points was added around the boundary, which fixes that problem, while causing the display of somewhat spurious cell boundary lines well outside of the region of interest.

Given a set of points in the US, usa_centroid_geo() can estimate the centroids of the "in-USA" Voronoi cells.

The function usa_cvt_geo() can estimate the location of generator points corresponding to a centroidal Voronoi tessellation of the geometric information in the US.

Licensing:

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

Languages:

USA_CVT_GEO is available in a MATLAB version.

Related Data and Programs:

CCVT_BOX, a MATLAB program which constructs a modified CVT in which some points are forced to lie on the boundary.

CCVT_REFLECT, a MATLAB program which tries to construct a modified CVT in which some points are forced to lie on the boundary, using a reflection idea.

CVT, a dataset directory which contains a variety of examples of CVT datasets.

CVT_1D_NONUNIFORM, a MATLAB program which constructs a CVT in one dimension, under a nonuniform density function.

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_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_3D_SAMPLING, a MATLAB program which computes an N-point Centroidal Voronoi Tessellation (CVT) within the unit cube [0,1]x[0,1]x[0,1], under a uniform density, using sampling to estimate the Voronoi regions.

CVT_CIRCLE_NONUNIFORM, a MATLAB program which calculates a nonuniform Centroidal Voronoi Tessellation (CVT) over a circle.

CVT_CIRCLE_UNIFORM, a MATLAB program which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

CVT_CORN, a MATLAB program which studies a 2D model of the growth of a corn kernel, by treating the surface and interior biological cells as points to be organized by a Centroidal Voronoi Tessellation (CVT) with a nonuniform density; during a sequence of growth steps, new biological cells are randomly added to the surface and interior.

CVT_DATASET, a MATLAB program which computes a Centroidal Voronoi Tessellation (CVT) and writes it to a file.

CVT_ELLIPSE_UNIFORM, a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over an ellipse, with a uniform density.

CVT_METRIC, a MATLAB program which computes a Centroidal Voronoi Tessellation (CVT) under a spatially varying metric;

CVT_MOVIE, a MATLAB program which creates an animation of the evolution of a Centroidal Voronoi Tessellation (CVT);

CVT_MOVIE2, a MATLAB program which creates a Centroidal Voronoi Tessellation (CVT) movie;

CVT_MOVIE3, a MATLAB program which creates a Centroidal Voronoi Tessellation (CVT) movie in a region of unusual shape;

CVT_MOVIE4, a MATLAB program which creates a Centroidal Voronoi Tessellation (CVT) movie in a square, with a density function that drives points to the corners;

CVT_MOVIE5, a MATLAB program which repeats cvt_movie3, but with hexagonal grid initialization, fixed points, and boundary projection;

CVT_SQUARE_PDF_DISCRETE, a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a density derived from a discrete PDF.

CVT_SQUARE_UNIFORM, a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a uniform density.

CVT_TRIANGLE_UNIFORM, a MATLAB program which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a triangle, with a uniform density.

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.

FLORIDA_CVT_POP, MATLAB programs which explore the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based on population density.

LCVT, a MATLAB library which computes a latinized Centroidal Voronoi Tessellation.

LINE_CVT_LLOYD, a MATLAB library which applies Lloyd's iteration repeatedly to a set of N points, to compute a Centroidal Voronoi Tessellation (CVT) over the interior of a line segment in 1D.

MATLAB_MAP, MATLAB programs which illustrate the use of the MATLAB Mapping Toolbox.

NEAREST_NEIGHBOR, a MATLAB library which works in a given M-dimensional space, seeking, for each point in a set S, the nearest point in a set R, by Richard Brown.

SPHERE_CVT, a MATLAB library which uses a Centroidal Voronoi Tessellation to create a mesh of well-separated points on the surface of the unit sphere in 3D.

usa_cvt_geo_test

Reference:

  1. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review,
    Volume 41, Number 4, December 1999, pages 637-676.
  2. Lili Ju, Qiang Du, Max Gunzburger,
    Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
    Parallel Computing,
    Volume 28, 2002, pages 1477-1500.
  3. The Mathworks,
    Mapping Toolbox User's Guide, R2016a.

Source Code:


Last revised on 12 February 2019