TRIANGULATION (ORDER 6)
Pairs of Files Defining a Triangulation

These are some examples of TRIANGULATION data of order 6; defining a triangulation requires two files:

• the node file lists the coordinates of a set of points.
• the triangle file lists sets of six node indices, which are the vertices and side nodes.

The six node triangulation, sometimes called a quadratic triangulation, includes the extra three nodes to allow for a higher degree of approximation when a finite element method is used. When listing the six nodes for a given triangle, the first three items are the vertices, in counterclockwise order. The fourth item is the side node between nodes 1 and 2, the fifth the side node between nodes 2 and 3, and the sixth the side node between nodes 3 and 1.

The point sets are distinguished by the values of the following parameters:

• M, the spatial dimension;
• N, the number of points;

At the moment, no facility is provided for allowing the specification of constrained edges, or the existence of holes in the region, both of which are of some interest.

Related Data and Programs:

FEM is a format used to store a finite element model. It includes a node and element file, as well as a node data file. The node and triangle files described here are an example of the first two of these files.

MESH_BANDWIDTH is an interactive executable FORTRAN90 program which returns the geometric bandwidth associated with a mesh of elements of any order and in a space of arbitrary dimension.

TABLE is a format used for both the node and triangle files.

TRIANGULATION (ORDER 3) is a related format for a linear triangulation in which each triangle is defined by 3 nodes.

TRIANGULATION_PLOT is a graphics program which can create Encapsulated PostScript images of the data files.

Example of a node file:

As a simple example, suppose we had the following set of points:

        11 12 13 14 15

         6  7  8  9 10

         1  2  3  4  5
      

        #  Node file for simple example.
        #
        0.0  0.0
        1.0  0.0
        2.0  0.0
        3.0  0.0
        4.0  0.0
        0.0  1.0
        1.0  1.0
        2.0  1.0
        3.0  1.0
        4.0  1.0
        0.0  2.0
        1.0  2.0
        2.0  2.0
        3.0  2.0
        4.0  2.0
      

Example of a triangle file:

An order 6 triangulation of these nodes is:

        11-12-13-14-15
         |\    |\    |
         | \   | \   |
         6  7  8  9 10
         |   \ |   \ |
         |    \|    \|
         1--2--3--4--5
      

        #  Triangle file for simple example.
        #
         1  3 11  2  7  6
        13 11  3 12  7  8
         3  5 13  4  9  8
        15 13  5 14  9 10
      

Programs to create a set of nodes to fill a given region:

A node file can come from anywhere. In most cases, you generate this data by observation or the characteristics of a particular problem or set of data you are working on.

• DISTMESH can take a description of a region, and fill it with grid points (and provide an order 3 triangulation of those points).
• TRIANGLE can take a description of a region, and fill it with grid points (and provide an order 3 triangulation of those points).

Programs to generate a set of nodes:

• CVT_DATASET, available in a C++ version, a FORTRAN90 version, and a MATLAB version, produces a TABLE file of N points in M dimensions, as a centroidal Voronoi tessellation.
• CVT_MOD_DATASET produces a TABLE file of N points in M dimensions, as a centroidal Voronoi tessellation on a unit hypercube with modular arithmetic.
• FAURE_DATASET produces a TABLE file of N points in M dimensions, from a Faure sequence.
• GRID_DATASET produces a TABLE file of N points in M dimensions, as a regular grid.
• HALTON_DATASET, available in a C++ version and a FORTRAN90 version, and a MATLAB version, produces a TABLE file of N points in M dimensions, from a Halton sequence.
• HAMMERSLEY_DATASET, available in a C++ version and a FORTRAN90 version, and a MATLAB version, produces a TABLE file of N points in M dimensions, from a Hammersley sequence.
• IHS_DATASET produces a TABLE file of N points in M dimensions, from an Improved Hypercube Sampling pointset.
• LATIN_CENTER_DATASET produces a TABLE file of N points in M dimensions, from a Latin hypercube pointset with centering.
• LATIN_EDGE_DATASET produces a TABLE file of N points in M dimensions, from a Latin hypercube pointset with edge "centering".
• LATIN_RANDOM_DATASET produces a TABLE file of N points in M dimensions, from a Latin hypercube pointset with random "centering".
• LCVT_DATASET produces a TABLE file of N points in M dimensions, containing a Latin hypercube dataset derived from a centroidal Voronoi tessellation.
• NIEDERREITER2_DATASET produces a TABLE file of N points in M dimensions, from a Niederreiter sequence base 2.
• RANDOM_DATA is a FORTRAN90 program which can produce a set of points that are randomly sampled from a given 2D or 3D geometric shape.
• RBOX is a C++ program which will produce a random sample of points according to a given distribution, and over a given geometric shape. The resulting output file is ALMOST a TABLE file (you just need to delete the two initial records that list the spatial dimension and number of points.)
• RSITES is a C++ program which will produce a set of N points in M dimensional space, with the user allowed to specify the SEED to be passed to the C++ RAND routine. Point coordinates are integers between 0 and 999999.
• SOBOL_DATASET produces a TABLE file of N points in M dimensions, from a Sobol sequence.
• UNIFORM_DATASET, available in a C++ version or a FORTRAN90 version, or a MATLAB version, produces a TABLE file of N points in M dimensions, containing a uniform pseudorandom sequence.

Programs to create a triangulation from a set of nodes:

Once you have generated a node file, it is possible to generate a triangulation of the nodes. Programs and routines to create a triangulation include

• The GEOMETRY library includes the routine DTRIS2 which can generate a triangulation. GEOMETRY is available in a C++ version, a FORTRAN90 version and a a MATLAB version
• The GEOMPACK library includes the routine DTRIS2 which can generate a triangulation. GEOMPACK is available in a C++ version, a FORTRAN90 version and a a MATLAB version
• TABLE_DELAUNAY is an interactive FORTRAN90 program which reads a node file, triangulates it, and writes out an order 3 triangulation file.
• TRIANGLE is a C program which can compute an order 3 triangulation of a set of points.

Programs to display a triangulation:

• TRIANGULATION_DISPLAY_OPEN_GL is an executable C++ program which reads files defining a triangulation and displays an image using Open GL.
• TRIANGULATION_PLOT is an interactive program which reads a node file and a triangle file, and creates an EPS image of the triangulation. It is available in a FORTRAN90 version and a MATLAB version,

Programs to manipulate a triangulated dataset:

• TRIANGULATION_ORIENT is an executable FORTRAN90 program that reads data defining a triangulation, makes sure that every triangle has positive orientation, and if not, writes a corrected triangle file.
• TRIANGULATION_QL, an interactive FORTRAN90 program which reads a node file and an order 6 triangulation file, computes the midside nodes of the triangles and forms a linear (order 3) triangulation.
• TRIANGULATION_RCM, an interactive FORTRAN90 program which reads a node file and a triangulation file and uses the reverse Cuthill McKee algorithm to renumber the nodes and reduce the bandwidth of the adjacency matrix.
• TRIANGULATION_REFINE, an interactive FORTRAN90 program which reads a node file and a triangle file, and creates a refined triangulation, with 4 times as many triangles.
• TRIANGULATION_TRIANGLE_NEIGHBORS, an interactive FORTRAN90 program which reads a node file and a triangle file, computes the three neighboring triangles of each triangle, and writes them to a file.

Sample Files:

CAVITY_ORDER6 is a square region 1 unit high and 1 unit long, containing 8,185 nodes, and 4000 triangles. (Data supplied by Hyung-Chun Lee).

• cavity_order6_nodes.txt, the coordinates of 65 nodes;
• cavity_order6_triangles.txt, the 6-node triangulation of the data.
• cavity_order6.png, a PNG image of the triangulation.
• cavity_order6.tneighbor.txt, the neighboring triangles of each triangle, computed by TRIANGULATION_TRIANGLE_NEIGHBORS.

CHANNEL_ORDER6 is a rectangular region 1 unit high and 3 units long. The region was created by refinement, and the ordering of the nodes and elements is somewhat irregular.

• channel_order6_nodes.txt, the coordinates of 65 nodes;
• channel_order6_triangles.txt, the 6-node triangulation of the data.
• channel_order6.png, a PNG image of the triangulation.
• channel_order6.tneighbor.txt, the neighboring triangles of each triangle, computed by TRIANGULATION_TRIANGLE_NEIGHBORS.

CHANNEL2 is a rectangular region 1 unit high and 3 units long. This is the same region as CHANNEL, but the data has been set by hand, so the numbering is more regular. In particular, the "mesh bandwidth" of this region should be significantly less that for CHANNEL.

• channel2.65.nodes.txt, the coordinates of 65 nodes;
• channel2.65.triangles6.txt, the 6-node triangulation of the data.
• channel2.65.triangles6.png, a PNG image of the triangulation.
• channel2.65.triangles6.tneighbor.txt, the neighboring triangles of each triangle, computed by TRIANGULATION_TRIANGLE_NEIGHBORS.

ELL_ORDER6 is an L shaped region.

• ell_order6_nodes.txt contains the coordinates of 21 points.
• ell_order6_triangles.txt contains a triangulation of the points into 6 triangles;
• ell_order6.png is a PNG image of the triangulation.
• ell_order6.tneighbor.txt, the neighboring triangles of each triangle, computed by TRIANGULATION_TRIANGLE_NEIGHBORS.

HEX_JEFF_ORDER6 is a region with a double hexagonal hole, which was meshed by an advancing front code. (Data supplied by Jeff Borggaard).

• hex_jeff_order6_nodes.txt contains the coordinates of 21 points.
• hex_jeff_order6_triangles.txt contains a triangulation of the points into 6 triangles;
• hex_jeff_order6.png is a PNG image of the triangulation.
• hex_jeff_order6.tneighbor.txt, the neighboring triangles of each triangle, computed by TRIANGULATION_TRIANGLE_NEIGHBORS.

HOUSE_ORDER6 is a child's image of a house.

• house_order6_nodes.txt, the coordinates of 5 nodes;
• house_order6_triangles.txt, a triangulation of the nodes;
• house_order6.png, a PNG image of the triangulation;

IRREG_ORDER6 is an irregular boxy region surrounding a hole.

• irreg_order6_nodes.txt, the coordinates of 37 nodes;
• irreg_order6_triangles.txt, a triangulation of 10 triangles
• irreg_order6.png, a PNG image of the triangulation;

SMALL_ORDER6 is a square with a 5 by 5 grid of nodes, creating 8 elements of 6-node triangles.

• small_order6_nodes.txt, the coordinates of the 25 nodes;
• small_order6_triangles.txt, the 6-node triangulation of the data.
• small_order6.png, a PNG image of the triangulation.
• small_order6.tneighbor.txt, the neighboring triangles of each triangle, computed by TRIANGULATION_TRIANGLE_NEIGHBORS.

TRIANGLE_ORDER6 is a single order 6 triangle.

• triangle_order6_nodes.txt, the coordinates of the 6 nodes;
• triangle_order6_triangles.txt, the 6-node triangulation of the data.
• triangle_order6.png, a PNG image of the triangulation.

You can go up one level to the DATA page.