Creating a Skeleton from a Triangulation.

 

When , subroutine TRIGEN generates a skeleton data set from a triangulation. This skeleton can then be used to generate a new triangulation of (using TRIGEN with IADAPT=5), providing what amounts to a static rezoning capability. This might be useful in situations where it is important or desirable to have grid lines in the mesh aligned with contour lines of a given function. Generating such a skeleton by hand might be cumbersome, or even impossible a priori if the function in question depends on the solution u. If IADAPT=6, the solution is used to define the contour lines. If IADAPT=-6, the alternate function QXY is used. TRIGEN evaluates QXY at each vertex of each element in the mesh. QXY will generally be multivalued at the vertices, because of discontinuities in . Therefore, TRIGEN computes a weighted average of QXY at each vertex; the weights are proportional to the area of each element containing the vertex. The resulting grid function is then interpreted as a continuous piecewise linear polynomial.

NRGN  equally spaced contour lines for the function specified by IADAPT are used as subregion boundaries. The value of NRGN has a significant impact on new triangulations later produced by TRIGEN. Larger values of NRGN generally result in the creation of more subregions. Since the length scales of the subregions are used in determining the length scales of the resulting triangles, triangulating a skeleton with thin subregions will result in many small triangles. Using fewer contours will generally result in larger length scales and potentially fewer triangles in the resulting mesh.

Contour spacing is also controlled to some extent through the parameter HMIN , which must satisfy . This parameter controls minimum contour spacing by (approximately) insuring the contours are at least apart. This requirement may effectively reduce the value of NRGN in conflicting situations.

At a conceptual level, the problem of creating a skeleton is similar to the problem of drawing a contour map in TRIPLT.   However, in TRIPLT, except for the global problem of ordering the triangles for a surface plot, all the calculations proceed on an element-by-element basis, with the calculation for one element not interacting in any significant algorithmic way with the calculation for any other element. Here there are significant interactions on a global level, requiring a data structure that can contain the entire contour map.

Thus we develop a data structure in which is partitioned into polygonal subregions. The boundary of a given subregion consists of portions of triangle edges and contour lines. The contours of a piecewise linear polynomial are straight lines in each element, with continuity between elements. Initially, each subregion is contained within a single triangle of the mesh, and has 3-5 sides, depending on the orientation and number of specified contour lines that appear in the element.

These subregions could, by themselves, be developed into a skeleton. However, such a data set would have many more subregions and vertices than necessary. Thus TRIGEN performs transformations on the list of regions, aimed at reducing both the number of subregions, and the number of vertices required to define them.

One basic step is to merge two subregions that share a common boundary into one larger subregion, thus eliminating all the internal edges and vertices along the common boundary. TRIGEN attempts to merge smaller subregions to form larger ones, generally respecting the following guidelines:

• Subregions with different labels cannot be merged. The labels are those originally provided by the user in ITNODE.
• If the common boundary is a contour edge, then the subregions cannot be merged.
• If the common boundary is not contiguous, then the subregions cannot be merged, as this would create a non-simply connected subregion.

The second guideline may be violated for exceptionally small subregions, which can occur frequently in the initial decomposition. If retained, they would cause many small triangles to be created by TRIGEN. Generally, if a subregion has an area A satisfying , then TRIGEN will try to merge it with a larger subregion, even if it must violate the second guideline to do so . Generally, TRIGEN tries to create the largest subregions possible within its constraints.

A vertex is said to have degree k if it has k incident polygon edges. A path is a sequence of connected degree two vertices, generally terminated at each end by a vertex of degree greater than two. TRIGEN eliminates unnecessary vertices, adhering to the following guidelines:

• A vertex is a candidate for deletion only if it has degree two. This means that the vertex is an internal vertex shared by only two subregions, or a boundary vertex contained in only one subregion.
• A boundary vertex cannot be removed if the two boundary edges it separates have different boundary condition types or different labels. The labels are those originally provided by the user in IBNDRY.
• A vertex is removed only if it is (approximately) collinear with the vertices on the path containing the given vertex, or if it is a redundant vertex on a circular arc approximation of the path.

The data reduction transformations described above maintain a data set corresponding to a valid skeleton. Thus, after the transformations are completed, the remaining subregions and vertices are used to generate the appropriate skeleton data structures.