The Skeleton.

The skeleton data structure is often the easiest data structure for the user to specify by hand, especially if the domain has complicated geometry, symmetry, or internal interfaces. In the skeleton data structure, the domain #tex2html_wrap_inline4166# is viewed as the union of NTR simply connected subregions #tex2html_wrap_inline4172#, #tex2html_wrap_inline4174#. The regions need not be convex, and the case NTR=1 is not excluded. A shared boundary between two subregions (an internal interface) will be respected by the triangulation process in TRIGEN; that is, the interface will be represented as one or more triangle edges in the triangulation. The boundary of each #tex2html_wrap_inline4180# should be a simple closed curve that does not intersect itself. Thus, for example, if #tex2html_wrap_inline4182# has a hole, adding a single cut between the outer boundary and the hole will not be adequate. At least two subregions will be required in this case. Having decomposed the domain into NTR subregions, we decompose the boundaries of the subregions into NBR edges #tex2html_wrap_inline4190#, #tex2html_wrap_inline4192#. Each edge has two endpoints #tex2html_wrap_inline4194#, #tex2html_wrap_inline4196#, and if it is a curved edge, it will have a circle center #tex2html_wrap_inline4198#. All curved edges are approximated by a circular arc as in the triangulation data structures . Curved edges must subtend less than #tex2html_wrap_inline4200# of arc. Globally, the vertices are labeled #tex2html_wrap_inline4202#, #tex2html_wrap_inline4204# and the circle centers are labeled #tex2html_wrap_inline4208#, #tex2html_wrap_inline4210#. The intersection of any two edges should be at most one common endpoint. As an example, we consider the square region with a hole illustrated in Figure~#datastructfigure2#327>. In this example, we decompose the region into 2 subregions (NTR=2), using 10 vertices (NVR=10), 12 edges (NBR=12), and 1 circle center (NCR=1) as shown.

#figure328#
Figure: Clockwise, from upper left: example domain decomposed into two subregions; vertex numbers; midpoint numbers; edge numbers.

Global numbering of the subregions, edges, vertices and midpoints is arbitrary. Each vertex #tex2html_wrap_inline4222#, #tex2html_wrap_inline4224#, is defined by its x and y coordinates, specified in the arrays VX and VY, in a fashion analogous to the triangulation. The VX and VY arrays for this example are shown in Table~#datastructtable2#339>. Each circle center #tex2html_wrap_inline4242#, #tex2html_wrap_inline4244#, is defined by its x and y coordinates, stored in the arrays XM and YM, as in the triangulation. The XM and YM arrays for this example are shown in Table~#datastructtable2#343>. In a fashion similar to the triangulation, an edge #tex2html_wrap_inline4262# is defined by five integer parameters - two (global) vertex numbers, a (global) circle center index if required, an edge type, and a label. Edge data is entered in the IBNDRY array in a fashion analogous to the triangulation. However, there is no constraint on the ordering of the vertices in IBNDRY(1,I) and IBNDRY(2,I). Descendents of Dirichlet, natural, and linked edges are included in the output IBNDRY array when #tex2html_wrap_inline4274# is triangulated using TRIGEN. Descendents of internal edges are retained only if they separate regions with different labels. Decendent edges retain the label of the original edge. In our example, we will assign Dirichlet boundary conditions to the left and right sides and the bottom of the domain, and natural boundary conditions elsewhere. The IBNDRY array then has the form given in Table~#datastructtable2#345>.

I 12345678910
VX(I) -2-202200-101
VY(I) 2-2-2-22210-10
XM(I)0
YM(I)0
Table: Skeleton data structures.
<#352#>The VX, VY, XM and YM arrays. NVR=10 and NCR=1.<#352#>
I 1 2 3 4 5 6 7 8 9 10 11 12
IBNDRY(1,I) 6 1 2 3 4 5 6 7 8 9 7 9
IBNDRY(2,I) 1 2 3 4 5 6 7 8 9 10 10 3
IBNDRY(3,I) 0 0 0 0 0 0 0 1 1 1 1 0
IBNDRY(4,I) 1 2 2 2 2 1 0 1 1 1 1 0
IBNDRY(5,I) 2 1 3 3 1 2 0 4 4 4 4 0
<#358#>The IBNDRY array. NBR=12.<#358#>

<#1022#><#843#>
I 1 2
ITNODE(1,I) 1 4
ITNODE(2,I) 2 5
ITNODE(3,I) 0 1
ITNODE(4,I) 1 2
I 1 2
ITNODE(1,I) 1 5
ITNODE(2,I) 2 6
ITNODE(3,I) 0 -1
ITNODE(4,I) 1 2
<#843#><#1022#>
<#368#>The ITNODE array for mapping by rotation (left) and by reflection (right). NTR=2.<#368#>

A subregion #tex2html_wrap_inline4344#, #tex2html_wrap_inline4346#, is defined by an ordered sequence of edges (at least three) that form its boundary. The sequence is ordered such that the boundary of #tex2html_wrap_inline4348# is traversed in a counterclockwise direction (thus providing notions of ``inside'' and ``outside''). Each edge in the sequence shares exactly one endpoint with the edge that precedes it and the edge that follows it in the sequence; the first and last edges in the sequence also share one endpoint. A particular edge can appear only once in the sequence. The array ITNODE is used to define the subregions. Column I of ITNODE corresponds to the region #tex2html_wrap_inline4358#. The first entry is a global vertex number for one of the vertices on the boundary of #tex2html_wrap_inline4360#. Unless #tex2html_wrap_inline4362# (see below) the choice of vertex is arbitrary. The second entry, ITNODE(2,I), is the global edge number of the first edge in a counterclockwise traversal of #tex2html_wrap_inline4366#, beginning at vertex #tex2html_wrap_inline4368#, where K=ITNODE(1,I). ITNODE(3,I) is used to specify certain symmetries the user may wish to impose on the triangulation. Two subregions are congruent if one can be mapped onto the other using an affine transformation consisting of a translation, an orthogonal rotation, and perhaps a simple reflection. If this mapping also induces one-to-one correspondences between the edges, vertices, and circle centers used to define the regions, then the user can specify that the two regions be triangulated in a similar fashion. ITNODE(3,I)=0 specifies that #tex2html_wrap_inline4378# can be triangulated independently of other regions. ITNODE(3,I)=J, 0;SPMlt;J;SPMlt;I, specifies that #tex2html_wrap_inline4384# can be mapped onto #tex2html_wrap_inline4386# using just a translation and rotation. ITNODE(3,I)=-J, 0;SPMlt;J;SPMlt;I, specifies that #tex2html_wrap_inline4392# can be mapped onto #tex2html_wrap_inline4394# using a translation, rotation, and a reflection. If #tex2html_wrap_inline4396#, then ITNODE(1,I) must correspond to the vertex on #tex2html_wrap_inline4400# which is mapped to the vertex corresponding to ITNODE(1,J) on #tex2html_wrap_inline4404#. If #tex2html_wrap_inline4406#, TRIGEN will map the triangulation generated for #tex2html_wrap_inline4410# onto #tex2html_wrap_inline4412#, insuring the desired symmetry properties of the overall triangulation. Note that this is not a symmetric relation; ITNODE(3,I)=J does not mean ITNODE(3,J)=I. In particular, if #tex2html_wrap_inline4418#, TRIGEN will return in an error condition. In our example, #tex2html_wrap_inline4422# can be mapped onto #tex2html_wrap_inline4424# either by rotation or reflection. We can insure the triangulation for #tex2html_wrap_inline4426# will be similar to that for #tex2html_wrap_inline4428#, either under rotation or reflection. The overall triangulations may be different in the two cases. (We could insure greater symmetry in the triangulation by decomposing #tex2html_wrap_inline4430# into 4 or 8 congruent regions instead of 2 and then setting ITNODE(3,I) appropriately.) ITNODE arrays for the two situations are illustrated in Table~#datastructtable2#404>. ITNODE(4,I) is a label for the region; all the triangles created in #tex2html_wrap_inline4438# will inherit its label. We provide several utility subroutines to aid in the creation of the skeleton data structures. Subroutine DVEDGE is called using the statement:
<#409#>

Call DVEDGE( NTR, NVR, NBR, MAXV, MAXB, VX, VY,

XM, YM, IBNDRY, ITNODE, LIST, IFLAG ) <#409#>
This routine takes as input a skeleton data structure defined in NTR, NVR, NBR, VX, VY, XM, YM, IBNDRY, and ITNODE, and divides curved edges as necessary to insure that all curved edges subtend less than #tex2html_wrap_inline4464# of arc. New edges and vertices are added as necessary, and the relevant skeleton parameters updated. Subroutine DVEDGE requires integer workspace array LIST of length NBR. Storage errors detected by DVEDGE are reported in the integer IFLAG as described in Table~#datastructtable4#410>. Subroutine MKITND is called using the statement:
<#413#>

Call MKITND( NVR, NBR, NTR, VX, VY, XM, YM,

ITNODE, IBNDRY, LIST, IFLAG ) <#413#>
This subroutine can be used to compute all entries of the ITNODE array, given the remaining arrays in the skeleton data structure (VX, VY, XM, YM, and IBNDRY) and the parameters NVR and NBR. The regions are labeled with ITNODE(4,I)=I for #tex2html_wrap_inline4500#, although these labels can subsequently be reset by the user. Subroutine MKITND does not look for congruent regions (ITNODE(3,I)=0 for #tex2html_wrap_inline4506#). Subroutine MKITND requires an intger workspace array LIST of length #tex2html_wrap_inline4512#. Skeleton data structure errors are returned in the integer IFLAG as described in Table~#datastructtable4#414>. Subroutine FNDSYM is called using the statement:
<#417#>

Call FNDSYM( NTR, NVR, NBR, VX, VY, XM, YM,

IBNDRY, JB, ITNODE, LIST, IFLAG ) <#417#>
This routine takes as input a complete skeleton data structure in NTR, NVR, NBR, VX, VY, XM, YM, IBNDRY and ITNODE, and finds congruent regions. The values of ITNODE(3,I) (and possibly ITNODE(1,I) and ITNODE(2,I)) are reset as necessary. If two regions are congruent but the congruence is not unique, as in our example, an arbitrary choice is made from among the possibilities. Subroutine FNDSYM requires integer workspace arrays JB of length #tex2html_wrap_inline4550# and LIST of length #tex2html_wrap_inline4554#. Skeleton data structure errors are returned in the integer IFLAG as described in Table~#datastructtable4#418>. Several other routines in the package check skeleton data structures for common errors in the data. If found, such errors are reported by setting the parameter IFLAG as described in Table~#datastructtable4#419>.