TRIANGULATION_CORNER
Handle triangulation corners.


TRIANGULATION_CORNER is a MATLAB 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:

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:

CVT_TRIANGULATION, a FORTRAN90 program which constructs a CVT triangulation for certain regions.

DISTMESH, a MATLAB library which carries out Persson and Strang's method of mesh generation;

HEX_GRID_TRIANGULATE, a FORTRAN90 program which computes points on a hexagonal grid inside a number of test regions.

TABLE_DELAUNAY, a FORTRAN90 program which reads a file of point coordinates in the TABLE format and writes out the Delaunay triangulation.

TEST_TRIANGULATION, a MATLAB library which defines a number of test regions to be triangulated.

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

TRIANGULATION, a MATLAB library which performs various operations on order 3 ("linear") or order 6 ("quadratic") triangulations.

TRIANGULATION_BOUNDARY_EDGES, a MATLAB program which reads data defining a triangulation, determines which edges lie on the boundary, organizes them into connected components, and writes this information to a file.

TRIANGULATION_BOUNDARY_NODES, a MATLAB 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 MATLAB 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 MATLAB program which computes histograms of data over a triangulation.

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

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

TRIANGULATION_ORDER3, a data directory of examples of 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 of examples of 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 MATLAB program which ensures that the triangles in an order 3 or order 6 triangulation have positive orientation;

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

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

TRIANGULATION_REFINE, a MATLAB program which can refine a triangulation.

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

Reference:

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

Source Code:

Examples and Tests:

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

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

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

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

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

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

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.

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

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

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

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

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

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

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


Last revised on 03 October 2009.