usa_cvt_geo


usa_cvt_geo, an Octave code which explores 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 MIT license

Languages:

usa_cvt_geo is available in a MATLAB version and an Octave version.

Related Data and Programs:

usa_cvt_geo_test

cvt_box, an Octave code which constructs a modified CVT in which some points are forced to lie on the boundary.

ccvt_reflect, an Octave code 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, an Octave code which constructs a CVT in one dimension, under a nonuniform density function.

cvt_1d_sampling, an Octave code 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, an Octave code 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, an Octave code 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, an Octave code which calculates a nonuniform Centroidal Voronoi Tessellation (CVT) over a circle.

cvt_circle_uniform, an Octave code which calculates a Centroidal Voronoi Tessellation (CVT) over a circle with uniform density.

cvt_corn, an Octave code 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_ellipse_uniform, an Octave code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over an ellipse, with a uniform density.

cvt_1_movie, an Octave code which creates an animation of the evolution of a Centroidal Voronoi Tessellation (CVT);

cvt_2_movie, an Octave code which creates a Centroidal Voronoi Tessellation (CVT) movie;

cvt_3_movie, an Octave code which creates a Centroidal Voronoi Tessellation (CVT) movie in a region of unusual shape;

cvt_4_movie, an Octave code which creates a Centroidal Voronoi Tessellation (CVT) movie in a square, with a density function that drives points to the corners;

cvt_square_pdf_discrete, an Octave code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a density derived from a discrete PDF.

cvt_square_uniform, an Octave code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a square, with a uniform density.

cvt_triangle_uniform, an Octave code which iteratively calculates a Centroidal Voronoi Tessellation (CVT) over a triangle, with a uniform density.

florida_cvt_geo, an Octave code which explores the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based solely on geometric considerations.

florida_cvt_pop, an Octave code which explores the creation of a centroidal Voronoi Tessellation (CVT) of the state of Florida, based on population density.

line_cvt_lloyd, an Octave code 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, an Octave code which illustrates the use of the MATLAB Mapping Toolbox.

sphere_cvt, an Octave code which uses a Centroidal Voronoi Tessellation to create a mesh of well-separated points on the surface of the unit sphere in 3D.

usa_box_plot, an Octave code which can create simplified maps of the USA in which each state appears as a box, and the placement of the boxes only roughly corresponds to the relative locations of states on an accurate map.

usa_matrix, an Octave code which defines the adjacency matrix for US states, using a variety of matrix formats.

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 03 July 2023.