cvt_triangulation


cvt_triangulation a FORTRAN90 code which applies Centroidal Voronoi Tessellation (CVT) methods to produce triangularizations of various test regions.

Note that, when using this code, we begin with a region, which is to be filled up with a number of (unspecified) points and triangularized.

Other codes, such as TABLE_DELAUNAY are available for the case where the points are already given, and only the triangles need to be determined.

Licensing:

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

Languages:

cvt_triangulation is available in a FORTRAN90 version.

Related codes:

cvt_triangulation_test

DISTMESH, a MATLAB code which takes the definition of a 2D region, and fills it up with a set of nodes, and triangulates those nodes to make a triangulation of the region. The region may be nonconvex and may include holes; the user may request a specific density for the nodes, and may require certain points to be in the set of nodes.

HEX_GRID_TRIANGULATE, a FORTRAN90 code which uses this library of test regions and computes points on a hexagonal grid inside each region.

PLOT_POINTS, a FORTRAN90 code which can be used to make simple plots of the computed points. For nonconvex regions, the Delaunay plots can be confusing. The plotting code is simple-minded, and merrily draws sides of triangles that go through holes or areas exterior to the region. In a few cases, it has been possible to draw the outline of the boundary of the region, but PLOT_POINTS cannot do very much in this regard.

TABLE, a file format which is used for the output files containing the CVT points.

TEST_TRIANGULATION, a FORTRAN90 code which can set up a number of triangulation test problems.

TRIANGULATION, a FORTRAN90 code which carries out various operations on order 3 ("linear") or order 6 ("quadratic") triangulations.

TRIANGULATION_BOUNDARY_NODES, a FORTRAN90 code which reads data defining a triangulation, determines which nodes lie on the boundary, and writes their coordinates to a file.

TRIANGULATION_DISPLAY_OPENGL, a C++ code which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_L2Q, a FORTRAN90 code which reads data defining a 3-node triangulation and generates midside nodes and writes out the corresponding 6-node triangulation.

TRIANGULATION_MASK, a FORTRAN90 code which takes an existing triangulation and deletes triangles and their corresponding nodes as requested by the user.

TRIANGULATION_ORDER3, a data directory which contains a description and examples of order 3 triangulations.

TRIANGULATION_ORDER6, a data directory which contains a description and examples of order 6 triangulations.

TRIANGULATION_ORIENT, a FORTRAN90 code which reads data defining a triangulation, makes sure that every triangle has positive orientation, and if not, writes a corrected triangle file.

TRIANGULATION_PLOT, a FORTRAN90 code which reads data defining a triangulation and creates a PostScript image of the nodes and triangles.

TRIANGULATION_Q2L, a FORTRAN90 code which reads data defining a 6-node triangulation, and subdivides each triangle into 4 3-node triangles, writing the resulting triangulation to a file.

TRIANGULATION_QUALITY, a FORTRAN90 code which reads data defining a triangulation and computes a number of quality measures.

TRIANGULATION_RCM, a FORTRAN90 code which reads data defining a triangulation, determines an ordering of the nodes that will reduce the bandwidth of the adjacency matrix, and writes the new triangulation information to a file.

TRIANGULATION_REFINE, a FORTRAN90 code which reads data defining a triangulation, replaces each triangle by four congruent smaller ones, and writes the new triangulation information to a file.

TRIANGULATION_TRIANGLE_NEIGHBORS, a FORTRAN90 code which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Reference:

  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, Number 3, September 1991, pages 345-405.
  2. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
    Computational Geometry,
    Springer, 2000,
    ISBN: 3-540-65620-0.
  3. Qiang Du, Vance Faber, Max Gunzburger,
    Centroidal Voronoi Tessellations: Applications and Algorithms,
    SIAM Review,
    Volume 41, 1999, pages 637-676.
  4. Lili Ju, Qiang Du, Max Gunzburger,
    Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations,
    Parallel Computing,
    Volume 28, 2002, pages 1477-1500.
  5. Joseph ORourke,
    Computational Geometry,
    Second Edition,
    Cambridge, 1998,
    ISBN: 0521649765,
    LC: QA448.D38.
  6. Per-Olof Persson, Gilbert Strang,
    A Simple Mesh Generator in MATLAB,
    SIAM Review,
    Volume 46, Number 2, June 2004, pages 329-345.

Source Code:


Last revised on 15 June 2020.