TRIANGULATION_CORNER
Handle triangulation corners.

TRIANGULATION_CORNER is a FORTRAN90 program which tries to correct situations in which a triangulation includes corner triangles, that is, triangles which have two sides on boundary.

Especially in finite element settings, such a triangle is considered undesirable. Especially in the case when a linear (order 3) finite element is involved, the function approximation in the interior of the triangle will be entirely determined by boundary data. If, for instance, the solution is constrained to be zero on the boundary, then the finite element function will be zero throughout the interior of the corner triangle.

Presumably, the triangle has a neighbor triangle on the one non-boundary side. It is generally possible and reasonable to replace these two triangles but another two which fill the same quadrilateral, but which are separated by the other diagonal of the quadrilateral.

The initial situation at the corner is suggest by the following diagram:

          |/  |/
          A---C--
          |\  |\
          | \ |
          |  \|
          B---D--

By rearranging the corner triangle and its neighbor, we have the more satisfactory triangulation:

          |/  |/
          A---C--
          |  /|\
          | / |
          |/  |
          B---D--

Usage:

triangulation_corner prefix

where prefix is the common filename prefix:

prefix_nodes.txt contains the node coordinates,
prefix_elements.txt contains the element definitions.
prefix_corner_nodes.txt will contain the revised node coordinates,
prefix_corner_elements.txt will contain the revised element definitions.

Licensing:

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

Languages:

TRIANGULATION_CORNER is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

TRIANGULATION, a FORTRAN90 library which performs 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_DELAUNAY_DISCREPANCY, a FORTRAN90 program which measures the amount by which a triangulation fails the local Delaunay test;

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

TRIANGULATION_HISTOGRAM, a FORTRAN90 program which computes histograms of data over a triangulation.

TRIANGULATION_L2Q, a FORTRAN90 program which reads information about a 3-node (linear) triangulation and creates data defining a corresponding 6-node (quadratic) triangulation;

TRIANGULATION_MASK, a FORTRAN90 program which reads a triangulation and calls a user-supplied routine to consider each triangle for deletion;

TRIANGULATION_ORDER3, a data directory which describes TRIANGULATION_ORDER3 files, description of a linear triangulation of a set of 2D points, using a pair of files to list the node coordinates and the 3 nodes that make up each triangle;

TRIANGULATION_ORDER6, a data directory which describes TRIANGULATION_ORDER6 files, a description of a quadratic triangulation of a set of 2D points, using a pair of files to list the node coordinates and the 6 nodes that make up each triangle.

TRIANGULATION_ORIENT, a FORTRAN90 program which ensures that the triangles in an order 3 or order 6 triangulation have positive orientation;

TRIANGULATION_PLOT, a FORTRAN90 program which makes a PostScript image of a triangulation of points.

TRIANGULATION_QUAD, a FORTRAN90 program which estimates the integral of a function over a triangulated region.

TRIANGULATION_REFINE, a FORTRAN90 program which can refine a triangulation.

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:

Joseph ORourke,
Computational Geometry,
Second Edition,
Cambridge, 1998,
ISBN: 0521649765,
LC: QA448.D38.

Source Code:

triangulation_corner.f90, the source code.

Examples and Tests:

P03 is the square with a hole. The initial mesh has 1 corner triangle.

p03_nodes.txt the mesh nodes of the problem.
p03_elements.txt the mesh triangles of the problem.
p03.png a PNG image of the initial mesh.
p02_corner_elements.txt the triangle file after corner triangles have been repaired.
p02_corner.png a PNG image of the repaired mesh.

P05 is the horn. The initial mesh has 4 corner triangles.

p05_nodes.txt the mesh nodes of the problem.
p05_elements.txt the mesh triangles of the problem.
p05.png a PNG image of the initial mesh.
p05_corner_elements.txt the triangle file after corner triangles have been repaired.
p05_corner.png a PNG image of the repaired mesh.

P08 is the holey pie slice. The initial mesh has 2 corner triangles.

p08_nodes.txt the mesh nodes of the problem.
p08_elements.txt the mesh triangles of the problem.
p08.png, a PNG image of the initial mesh.
p08_corner_elements.txt the triangle file after corner triangles have been repaired.
p08_corner.png a PNG image of the repaired mesh.

P09 is Jeff Borggaard's square with two hexagonal holes. The initial mesh has 3 corner triangles.

p09_nodes.txt the mesh nodes of the problem.
p09_elements.txt the mesh triangles of the problem.
p09.png a PNG image of the initial mesh.
p09_corner_elements.txt the triangle file after corner triangles have been repaired.
p09_corner.png a PNG image of the repaired mesh.

P10 is the unit square. The initial mesh has 4 corner triangles.

p10_nodes.txt the mesh nodes of the problem.
p10_elements.txt the mesh triangles of the problem.
p10.png a PNG image of the initial mesh.
p10_corner_elements.txt the triangle file after corner triangles have been repaired.
p10_corner.png a PNG image of the repaired mesh.

P11 is the L-shaped region. The initial mesh has 4 corner triangles.

p11_nodes.txt the mesh nodes of the problem.
p11_elements.txt the mesh triangles of the problem.
p11.png a PNG image of the initial mesh.
p11_corner_elements.txt the triangle file after corner triangles have been repaired.
p11_corner.png a PNG image of the repaired mesh.

Q11 is the L-shaped region, but with quadratric (6 node) triangles. The initial mesh has 4 corner triangles. Because we are using quadratic triangles, when we merge two triangles and swap the diagonal, the midside node on the common diagonal will no longer lie on a line, midway between the two vertices. TRIANGULATION_CORNER assumes this is undesirable, and recomputes the coordinates of such midside nodes, and outputs a modified node coordinate file as well as the new triangle file.

q11_nodes.txt the mesh nodes of the problem.
q11_elements.txt the mesh triangles of the problem.
q11.png a PNG image of the initial mesh.
q11_nodes.corner.txt the node coordinate file after corner triangles have been repaired, which, for quadratric triangles, requires adjusting some midside nodes.
q11_corner_elements.txt the triangle file after corner triangles have been repaired.
q11_corner.png a PNG image of the repaired mesh.

P12 is the John Shadid's H-shaped region. The initial mesh has 7 corner triangles.

p12_nodes.txt the mesh nodes of the problem.
p12_elements.txt the mesh triangles of the problem.
p12.png a PNG image of the initial mesh.
p12_corner_elements.txt the triangle file after corner triangles have been repaired.
p12_corner.png a PNG image of the repaired mesh.

P13 is the Sandia fork. The initial mesh has 6 corner triangles.

p13_nodes.txt the mesh nodes of the problem.
p13_elements.txt the mesh triangles of the problem.
p13.png a PNG image of the initial mesh.
p13_corner_elements.txt the triangle file after corner triangles have been repaired.
p13_corner.png a PNG image of the repaired mesh.

P14 is Marcus Garvie's Lake Alpha, with Beta Island. The initial mesh has 5 corner triangles. (Must be small!)

p14_nodes.txt the mesh nodes of the problem.
p14_elements.txt the mesh triangles of the problem.
p14.png a PNG image of the initial mesh.
p14_corner_elements.txt the triangle file after corner triangles have been repaired.
p14_corner.png a PNG image of the repaired mesh.

P15 is Sangbum Kim's forward step region. The initial mesh has 6 corner triangles.

p15_nodes.txt the mesh nodes of the problem.
p15_elements.txt the mesh triangles of the problem.
p15.png a PNG image of the initial mesh.
p15_corner_elements.txt the triangle file after corner triangles have been repaired.
p15_corner.png a PNG image of the repaired mesh.

P16 is Kevin Pond's elbow, a quarter of a circular annulus. The initial mesh has 1 corner triangle.

p16_nodes.txt the mesh nodes of the problem.
p16_elements.txt the mesh triangles of the problem.
p16.png a PNG image of the initial mesh.
p16_corner_elements.txt the triangle file after corner triangles have been repaired.
p16_corner.png a PNG image of the repaired mesh.

P17 is the rectangular channel with a Reuleaux triangle obstacle. The initial mesh has 4 corner triangles.

p17_nodes.txt the mesh nodes of the problem.
p17_elements.txt the mesh triangles of the problem.
p17.png a PNG image of the initial mesh.
p17_corner_elements.txt the triangle file after corner triangles have been repaired.
p17_corner.png a PNG image of the repaired mesh.

List of Routines:

MAIN is the main program for TRIANGULATION_CORNER.
CH_CAP capitalizes a single character.
CH_EQI is a case insensitive comparison of two characters for equality.
CH_TO_DIGIT returns the integer ( kind = 4 ) value of a base 10 digit.
DTABLE_CLOSE_WRITE closes a file used to write a DTABLE.
DTABLE_DATA_READ reads data from a double precision table file.
DTABLE_DATA_WRITE writes DTABLE data to a file.
DTABLE_HEADER_READ reads the header from a double precision table file.
DTABLE_HEADER_WRITE writes the header to a DTABLE file.
DTABLE_OPEN_WRITE opens a file to write a DTABLE.
DTABLE_WRITE writes a DTABLE to a file.
FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
FILE_NAME_EXT_GET determines the "extension" of a file name.
FILE_NAME_EXT_SWAP replaces the current "extension" of a file name.
FILE_ROW_COUNT counts the number of row records in a file.
GET_UNIT returns a free FORTRAN unit number.
I4_MODP returns the nonnegative remainder of I4 division.
I4_WRAP forces an I4 to lie between given limits by wrapping.
I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
I4ROW_COMPARE compares two rows of an I4ROW.
I4ROW_SORT_A ascending sorts the rows of an I4ROW.
I4ROW_SWAP swaps two rows of an I4ROW.
ITABLE_DATA_READ reads data from an integer ( kind = 4 ) table file.
ITABLE_DATA_WRITE writes data to an integer ( kind = 4 ) table file.
ITABLE_HEADER_READ reads the header from an integer ( kind = 4 ) table file.
ITABLE_HEADER_WRITE writes the header to an integer ( kind = 4 ) table file.
ITABLE_WRITE writes an integer ( kind = 4 ) table file.
R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
S_INDEX_LAST_C finds the LAST occurrence of a given character.
S_TO_I4 reads an I4 from a string.
S_TO_I4VEC reads an I4VEC from a string.
S_TO_R8 reads an R8 from a string.
S_TO_R8VEC reads an R8VEC from a string.
S_WORD_COUNT counts the number of "words" in a string.
SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
TIMESTAMP prints the current YMDHMS date as a time stamp.
TRIANGLE_AREA_2D computes the area of a triangle in 2D.
TRIANGULATION_ORDER3_NEIGHBOR_TRIANGLES determines triangle neighbors.
TRIANGULATION_ORDER6_NEIGHBOR_TRIANGLES determines triangle neighbors.

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

Last revised on 30 December 2010.

TRIANGULATION_CORNER Handle triangulation corners.