TEST_TRIANGULATION
Mesh Generation Test Regions

TEST_TRIANGULATION is a FORTRAN90 library which sets up a number of triangulation test problems.

As far as possible, a uniform and abstract approach has been used. For each test region, a number of routines are provided, via which it is possible for the user to determine many things about the region. Often, just one or two routines would be needed for a particular purpose. The names of the routines, and their purposes are:

The test problems include:

  1. The unit circle;
  2. The unit circle with a circular hole;
  3. A square with a circular hole;
  4. A hexagon with a hexagonal hole;
  5. The horn;
  6. The superellipse with a superelliptical hole;
  7. The bicycle seat;
  8. The slice of pie with a circular hole and triangular notch;
  9. Jeff Borggaard's square with two hexagonal holes;
  10. The unit square;
  11. The L-shaped region;
  12. John Shadid's H-shaped region;
  13. The Sandia fork;
  14. Marcus Garvie's Lake Alpha, with Beta Island;
  15. Sangbum Kim's forward step;

Licensing:

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

Languages:

TEST_TRIANGULATION is available in a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

CVT_TRIANGULATION, a FORTRAN90 program which uses routines from the TEST_TRIANGULATION library to create a CVT-based triangularization.

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.

TABLE_IO, a FORTRAN90 library which is used to write some of the output files.

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 directory which describes the format for triangulations of order 3.

TRIANGULATION ORDER6, a directory which describes the format for triangulations of order 6.

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. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
    Computational Geometry,
    Springer, 2000,
    ISBN: 3-540-65620-0.
  2. Barry Joe,
    GEOMPACK - a software package for the generation of meshes using geometric algorithms,
    Advances in Engineering Software,
    Volume 13, 1991, pages 325-331.
  3. Joseph ORourke,
    Computational Geometry,
    Second Edition,
    Cambridge, 1998,
    ISBN: 0521649765,
    LC: QA448.D38.
  4. Per-Olof Persson, Gilbert Strang,
    A Simple Mesh Generator in MATLAB,
    SIAM Review,
    Volume 46, Number 2, June 2004, pages 329-345.

Source Code:

Examples and Tests:

TEST_TRIANGULATION_PRB carries out some simple tasks with the sample problems.

One of the routines in TEST_TRIANGULATION_PRB calls the appropriate routines to determine the boundary of each region, and creates an Encapsulated PostScript image.

One of the routines in TEST_TRIANGULATION_PRB creates an EPS image of 200 sample points in each region.

One of the routines in TEST_TRIANGULATION_PRB calls the appropriate routine to create a POLY file, which can be displayed by the SHOWME program, or used as the start of a triangulation process involving TRIANGLE.

Simple changes to TEST_TRIANGULATION_PRB can be made so that a file is created containing pairs of sample points and nearest points on the boundary. If the file lists these pairs followed by a blank line, then the PLOT_POINTS can be used, with the "DASH" option, to illustrate the results.

One of the routines in TEST_TRIANGULATION_PRB creates a set of points on a hexagonal grid, contained in a given region. This dataset is written to a file.

List of Routines:

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

Last revised on 23 October 2006.