CVT_TRIANGULATION
Centroidal Voronoi Tessellation
for Triangularization

CVT_TRIANGULATION is a FORTRAN90 program which applies Centroidal Voronoi Tessellation (CVT) methods to produce triangularizations of various test regions.

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

Other programs, 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 Programs:

CVT_TET_MESH, a FORTRAN90 program which applies CVT methods to produce a tetrahedral mesh of various test regions in 3D.

DISTMESH, a MATLAB program 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 program which uses this library of test regions and computes points on a hexagonal grid inside each region.

PLOT_POINTS, a FORTRAN90 program which can be used to make simple plots of the computed points. For nonconvex regions, the Delaunay plots can be confusing. The plotting program 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.

TABLE_DELAUNAY, a FORTRAN90 program which reads in a TABLE file of points and writes out a corresponding triangulation.

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

TRIANGLE, a C program which computes a triangulation of a geometric region.

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

TRIANGULATION_BOUNDARY_NODES, a FORTRAN90 program 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++ program which reads files defining a triangulation and displays an image using Open GL.

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

TRIANGULATION_MASK, a FORTRAN90 program 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 program 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 program which reads data defining a triangulation and creates a PostScript image of the nodes and triangles.

TRIANGULATION_Q2L, a FORTRAN90 program 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 program which reads data defining a triangulation and computes a number of quality measures.

TRIANGULATION_RCM, a FORTRAN90 program 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 program 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 program 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:

• cvt_triangulation.f90, the source code.
• cvt_triangulation.txt, the output file.

There are some files for use with the PLOT_POINTS program:

• plot_points_input.txt, contains the input commands to PLOT_POINTS to make the plots.
• plot_points.txt, contains the printed output from PLOT_POINTS.

Examples and Tests:

Region 1 is the circle:

• cvt_p01.txt, a text file containing the CVT points.
• cvt_p01.png, a PNG image of the points and the region's boundary.
• cvt_p01_dot.png, a PNG image of the CVT points.
• cvt_p01_del.png, a PNG image of the Delaunay mesh.

Region 2 is the circle with a circular hole:

• cvt_p02.txt, a text file containing the CVT points.
• cvt_p02.png, a PNG image of the points and the region's boundary.
• cvt_p02_dot.png, a PNG image of the CVT points.
• cvt_p02_del.png, a PNG image of the Delaunay mesh.

Region 3 is the square with a circular hole:

• cvt_p03.txt, a text file containing the CVT points.
• cvt_p03.png, a PNG image of the points and the region's boundary.
• cvt_p03_del.png, a PNG image of the Delaunay mesh.
• cvt_p03_hbf.txt, the coordinates of points generated using hexagonal initialization, an expanded boundary and fixed points.
• cvt_p03_hbf.png, a PNG image of the points generated using hexagonal initialization, an expanded boundary and fixed points.

Region 4 is the hexagon with a hexagonal hole:

• cvt_p04.txt, a text file containing the CVT points.
• cvt_p04.png, a PNG image of the points and the region's boundary.
• cvt_p04_del.png, a PNG image of the Delaunay mesh.

Region 5 is the horn:

• cvt_p05.txt, a text file containing the CVT points.
• cvt_p05.png, a PNG image of the points and the region's boundary.
• cvt_p05_del.png, a PNG image of the Delaunay mesh.

Region 6 is the superellipse with the superelliptical hole:

• cvt_p06.txt, a text file containing the CVT points.
• cvt_p06.png, a PNG image of the points and the region's boundary.
• cvt_p06_del.png, a PNG image of the Delaunay mesh.

Region 7 is the "bicycle seat":

• cvt_p07.txt, a text file containing the CVT points.
• cvt_p07.png, a PNG image of the points and the region's boundary.
• cvt_p07_del.png, a PNG image of the Delaunay mesh.

Region 8 is the pie slice:

• cvt_p08.txt, a text file containing the CVT points.
• cvt_p08_boundary.png, a PNG image of the points and the region's boundary.
• cvt_p08_boundary_fixed.png, a PNG image of the points and the region's boundary, with fixed points.
• cvt_p08_del.png, a PNG image of the Delaunay mesh.
• cvt_p08_fixed_del.png, a PNG image of the Delaunay mesh, with fixed points.
• cvt_p08_hex.png, a PNG image of the initial points from a hex grid.
• cvt_p08_hbf.png, a PNG image of the mesh using hexagonal initialization, boundary constraints, and fixed points.

Region 9 is the square with two hexagonal holes:

• cvt_p09.txt, a text file containing the CVT points.
• cvt_p09.png, a PNG image of the points and the region's boundary.
• cvt_p09_del.png, a PNG image of the Delaunay mesh.

Region 10 is the unit square:

• cvt_p10.txt, a text file containing the CVT points.
• cvt_p10.png, a PNG image of the points and the region's boundary.
• cvt_p10_del.png, a PNG image of the Delaunay mesh.

Region 11 is the L-shaped region:

• cvt_p11.txt, a text file containing the CVT points.
• cvt_p11.png, a PNG image of the points and the region's boundary.
• cvt_p11_boundary.png, a PNG image of the region's boundary.
• cvt_p11_boundary_fixed.png, a PNG image of the region's boundary with fixed points.
• cvt_p11_del.png, a PNG image of the Delaunay mesh.
• cvt_p11_fixed_del.png, a PNG image of the Delaunay mesh, using fixed points.
• cvt_p11_hex.png, a PNG image of hexagonal points in the region.

Region 12 is the H-shaped region:

• cvt_p12.txt, a text file containing the CVT points.
• cvt_p12.png, a PNG image of the points and the region's boundary.
• cvt_p12_boundary.png, a PNG image of the region's boundary.
• cvt_p12_boundary_fixed.png, a PNG image of the region's boundary with fixed points.
• cvt_p12_fixed_del.png, a PNG image of the Delaunay mesh, using fixed points.
• cvt_p12_hex.png, a PNG image of hexagonal points in the region.

Region 13 is the fork:

• cvt_p13.txt, a text file containing the CVT points.
• cvt_p13.png, a PNG image of the points and the region's boundary.
• cvt_p13_boundary.png, a PNG image of the region's boundary.
• cvt_p13_fixed_del.png, a PNG image of the Delaunay mesh, using fixed points.
• cvt_p13_hex.png, a PNG image of hexagonal points in the region.

Region 14 is Lake Alpha, with Beta Island:

• cvt_p14.txt, a text file containing the CVT points.
• cvt_p14.png, a PNG image of the points and the region's boundary.
• cvt_p14_boundary.png, a PNG image of the region's boundary.
• cvt_p14_boundary_fixed.png, a PNG image of the region's boundary with fixed points.
• cvt_p14_fixed_del.png, a PNG image of the Delaunay mesh, using fixed points.
• cvt_p14_hex.png, a PNG image of hexagonal points in the region.

List of Routines:

• MAIN is the main program for CVT_TRIANGULATION.
• TEST01 uses CVT techniques on a given test problem.
• FIND_CLOSEST finds the closest point to each sample.
• CVT_WRITE writes a CVT dataset to a file.

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