NAG FL Interface
d06baf (dim2_​gen_​boundary)

1 Purpose

d06baf generates a boundary mesh on a closed connected subdomain Ω of 2.

2 Specification

Fortran Interface
Integer, Intent (In) :: nlines, lined(4,nlines), sdcrus, ncomp, nlcomp(ncomp), lcomp(nlines), nvmax, nedmx, itrace, lrwork, liwork
Integer, Intent (Inout) :: iuser(*), ifail
Integer, Intent (Out) :: nvb, nedge, edge(3,nedmx), iwork(liwork)
Real (Kind=nag_wp), External :: fbnd
Real (Kind=nag_wp), Intent (In) :: coorch(2,nlines), crus(2,sdcrus), rate(nlines)
Real (Kind=nag_wp), Intent (Inout) :: ruser(*)
Real (Kind=nag_wp), Intent (Out) :: coor(2,nvmax), rwork(lrwork)
C Header Interface
#include <nag.h>
void  d06baf_ (const Integer *nlines, const double coorch[], const Integer lined[],
double (NAG_CALL *fbnd)(const Integer *i, const double *x, const double *y, double ruser[], Integer iuser[]),
const double crus[], const Integer *sdcrus, const double rate[], const Integer *ncomp, const Integer nlcomp[], const Integer lcomp[], const Integer *nvmax, const Integer *nedmx, Integer *nvb, double coor[], Integer *nedge, Integer edge[], const Integer *itrace, Integer iuser[], double ruser[], double rwork[], const Integer *lrwork, Integer iwork[], const Integer *liwork, Integer *ifail)
The routine may be called by the names d06baf or nagf_mesh_dim2_gen_boundary.

3 Description

Given a closed connected subdomain Ω of 2, whose boundary Ω is divided by characteristic points into m distinct line segments, d06baf generates a boundary mesh on Ω. Each line segment may be a straight line, a curve defined by the equation fx,y=0, or a polygonal curve defined by a set of given boundary mesh points.
This routine is primarily designed for use with either d06aaf (a simple incremental method) or d06abf (Delaunay–Voronoi method) or d06acf (Advancing Front method) to triangulate the interior of the domain Ω. For more details about the boundary and interior mesh generation, consult the D06 Chapter Introduction as well as George and Borouchaki (1998).
This routine is derived from material in the MODULEF package from INRIA (Institut National de Recherche en Informatique et Automatique).

4 References

George P L and Borouchaki H (1998) Delaunay Triangulation and Meshing: Application to Finite Elements Editions HERMES, Paris

5 Arguments

1: nlines Integer Input
On entry: m, the number of lines that define the boundary of the closed connected subdomain (this equals the number of characteristic points which separate the entire boundary Ω into lines).
Constraint: nlines1.
2: coorch2nlines Real (Kind=nag_wp) array Input
On entry: coorch1i contains the x coordinate of the ith characteristic point, for i=1,2,,nlines; while coorch2i contains the corresponding y coordinate.
3: lined4nlines Integer array Input
On entry: the description of the lines that define the boundary domain. The line i, for i=1,2,,m, is defined as follows:
lined1i
The number of points on the line, including two end points.
lined2i
The first end point of the line. If lined2i=j, the coordinates of the first end point are those stored in coorch:j.
lined3i
The second end point of the line. If lined3i=k, the coordinates of the second end point are those stored in coorch:k.
lined4i
This defines the type of line segment connecting the end points. Additional information is conveyed by the numerical value of lined4i as follows:
  1. (i)lined4i>0, the line is described in fbnd with lined4i as the index. In this case, the line must be described in the trigonometric (anticlockwise) direction;
  2. (ii)lined4i=0, the line is a straight line;
  3. (iii)if lined4i<0, say (-p), then the line is a polygonal arc joining the end points and interior points specified in crus. In this case the line contains the points whose coordinates are stored in coorch:j , crus:p , crus:p+1 ,, crus:p+r-3 , coorch:k , where z1,2, r=lined1i, j=lined2i and k=lined3i.
Constraints:
  • 2lined1i;
  • 1lined2inlines;
  • 1lined3inlines;
  • lined2ilined3i, for i=1,2,,nlines.
For each line described by fbnd (lines with lined4i > 0 , for i=1,2,,nlines) the two end points ( lined2i and lined3i ) lie on the curve defined by index lined4i in fbnd, i.e.,
fbndlined4i,coorch1lined2i,coorch2lined2i,ruser,iuser = 0 ;
fbndlined4i,coorch1lined3i,coorch2lined3i,ruser,iuser = 0 , for i=1,2,,nlines.
For all lines described as polygonal arcs (lines with lined4i < 0 , for i=1,2,,nlines) the sets of intermediate points (i.e., -lined4i : -lined4i + lined1i - 3 for all i such that lined4i<0) are not overlapping. This can be expressed as:
-lined4i + lined1i - 3 = i,lined4i<0 lined1i - 2  
or
-lined4i + lined1i - 2 = -lined4j ,  
for a j such that j=1,2,,nlines, ji and lined4j<0.
4: fbnd real (Kind=nag_wp) Function, supplied by the user. External Procedure
fbnd must be supplied to calculate the value of the function which describes the curve x,y 2; such that ​f x,y=0 on segments of the boundary for which lined4i>0. If there are no boundaries for which lined4i>0 fbnd will never be referenced by d06baf and fbnd may be the dummy function d06bad. (d06bad is included in the NAG Library.)
The specification of fbnd is:
Fortran Interface
Function fbnd ( i, x, y, ruser, iuser)
Real (Kind=nag_wp) :: fbnd
Integer, Intent (In) :: i
Integer, Intent (Inout) :: iuser(*)
Real (Kind=nag_wp), Intent (In) :: x, y
Real (Kind=nag_wp), Intent (Inout) :: ruser(*)
C Header Interface
double  fbnd_ (const Integer *i, const double *x, const double *y, double ruser[], Integer iuser[])
1: i Integer Input
On entry: lined4i, the reference index of the line (portion of the contour) i described.
2: x Real (Kind=nag_wp) Input
3: y Real (Kind=nag_wp) Input
On entry: the values of x and y at which fx,y is to be evaluated.
4: ruser* Real (Kind=nag_wp) array User Workspace
5: iuser* Integer array User Workspace
fbnd is called with the arguments ruser and iuser as supplied to d06baf. You should use the arrays ruser and iuser to supply information to fbnd.
fbnd must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which d06baf is called. Arguments denoted as Input must not be changed by this procedure.
Note: fbnd should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d06baf. If your code inadvertently does return any NaNs or infinities, d06baf is likely to produce unexpected results.
5: crus2sdcrus Real (Kind=nag_wp) array Input
On entry: the coordinates of the intermediate points for polygonal arc lines. For a line i defined as a polygonal arc (i.e., lined4i<0), if p=-lined4i, crus1k, for k=p,,p+lined1i-3, must contain the x coordinate of the consecutive intermediate points for this line. Similarly crus2k, for k=p,,p+lined1i-3, must contain the corresponding y coordinate.
6: sdcrus Integer Input
On entry: the second dimension of the array crus as declared in the (sub)program from which d06baf is called.
Constraint: sdcrusi,lined4i<0lined1i-2.
7: ratenlines Real (Kind=nag_wp) array Input
On entry: ratei is the geometric progression ratio between the points to be generated on the line i, for i=1,2,,m and lined4i0.
If lined4i<0, ratei is not referenced.
Constraint: if lined4i0, ratei>0.0, for i=1,2,,nlines.
8: ncomp Integer Input
On entry: n, the number of separately connected components of the boundary.
Constraint: ncomp1.
9: nlcompncomp Integer array Input
On entry: nlcompk is the number of line segments in component k of the contour. The line i of component k runs in the direction lined2i to lined3i if nlcompk>0, and in the opposite direction otherwise; for k=1,2,,n.
Constraints:
  • 1nlcompknlines, for k=1,2,,ncomp;
  • k =1 n nlcompk =nlines .
10: lcompnlines Integer array Input
On entry: lcomp must contain the list of line numbers for the each component of the boundary. Specifically, the line numbers for the kth component of the boundary, for k=1,2,,ncomp, must be in elements l1-1 to l2-1 of lcomp, where l2 = i=1 k nlcompi and l1=l2+1-nlcompk.
Constraint: lcomp must hold a valid permutation of the integers 1,nlines.
11: nvmax Integer Input
On entry: the maximum number of the boundary mesh vertices to be generated.
Constraint: nvmaxnlines.
12: nedmx Integer Input
On entry: the maximum number of boundary edges in the boundary mesh to be generated.
Constraint: nedmx1.
13: nvb Integer Output
On exit: the total number of boundary mesh vertices generated.
14: coor2nvmax Real (Kind=nag_wp) array Output
On exit: coor1i will contain the x coordinate of the ith boundary mesh vertex generated, for i=1,2,,nvb; while coor2i will contain the corresponding y coordinate.
15: nedge Integer Output
On exit: the total number of boundary edges in the boundary mesh.
16: edge3nedmx Integer array Output
On exit: the specification of the boundary edges. edge1j and edge2j will contain the vertex numbers of the two end points of the jth boundary edge. edge3j is a reference number for the jth boundary edge and
  • edge3j=lined4i, where i and j are such that the jth edges is part of the ith line of the boundary and lined4i0;
  • edge3j=100+lined4i, where i and j are such that the jth edges is part of the ith line of the boundary and lined4i<0.
17: itrace Integer Input
On entry: the level of trace information required from d06baf.
itrace=0 or itrace<-1
No output is generated.
itrace=1
Output from the boundary mesh generator is printed on the current advisory message unit (see x04abf). This output contains the input information of each line and each connected component of the boundary.
itrace=-1
An analysis of the output boundary mesh is printed on the current advisory message unit. This analysis includes the orientation (clockwise or anticlockwise) of each connected component of the boundary. This information could be of interest to you, especially if an interior meshing is carried out using the output of this routine, calling either d06aaf, d06abf or d06acf.
itrace>1
The output is similar to that produced when itrace=1, but the coordinates of the generated vertices on the boundary are also output.
You are advised to set itrace=0, unless you are experienced with finite element mesh generation.
18: iuser* Integer array User Workspace
19: ruser* Real (Kind=nag_wp) array User Workspace
iuser and ruser are not used by d06baf, but are passed directly to fbnd and may be used to pass information to this routine.
20: rworklrwork Real (Kind=nag_wp) array Workspace
21: lrwork Integer Input
On entry: the dimension of the array rwork as declared in the (sub)program from which d06baf is called.
Constraint: lrwork2×nlines+sdcrus+2×maxi=1,2,,mlined1i×nlines.
22: iworkliwork Integer array Workspace
23: liwork Integer Input
On entry: the dimension of the array iwork as declared in the (sub)program from which d06baf is called.
Constraint: liworki,lined4i<0 lined1i-2+8×nlines+nvmax+3×nedmx+2×sdcrus.
24: ifail Integer Input/Output
On entry: ifail must be set to 0, -1 or 1 to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of 0 causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of -1 means that an error message is printed while a value of 1 means that it is not.
If halting is not appropriate, the value -1 or 1 is recommended. If message printing is undesirable, then the value 1 is recommended. Otherwise, the value 0 is recommended. When the value -1 or 1 is used it is essential to test the value of ifail on exit.
On exit: ifail=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry ifail=0 or -1, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
ifail=1
On entry, end point 1, with index K, does not lie on the curve representing line I with index J: K=value, I=value, J=value, fx,y=value.
On entry, end point 2, with index K, does not lie on the curve representing line I with index J: K=value, I=value, J=value, fx,y=value.
On entry, liwork=value and LIWKMN=value.
Constraint: liworkLIWKMN.
On entry, lrwork=value and LRWKMN=value.
Constraint: lrworkLRWKMN.
On entry, ncomp=value.
Constraint: ncomp1.
On entry, nedmx=value.
Constraint: nedmx1.
On entry, nlines=value.
Constraint: nlines1.
On entry, nvmax=value and nlines=value.
Constraint: nvmaxnlines.
On entry, sdcrus=value and nusmin=value.
Constraint: sdcrusnusmin.
On entry, the absolute number of line segments in the kth component of the contour should be less than or equal to nlines and greater than 0. k=value, nlcompk=value and nlines=value.
On entry, the geometric progression ratio between the points to be generated on line value is value. It should be greater than 0 unless the line segment is defined by user-supplied points.
On entry, the index of the first end point of line value is value. It should be greater than or equal to 1 and less than or equal to nlines=value.
On entry, the index of the second end point of line value is value. It should be greater than or equal to 1 and less than or equal to nlines=value.
On entry, the indices of the extremities of line value are both equal to value.
On entry, the line list for the separate connected component of the boundary is badly set: lcompl=value and l=value. It should be less than or equal to nlines and greater than or equal to 1.
On entry, the number of points on line value is value. It should be greater than or equal to 2.
On entry, there is a correlation problem between the user-supplied coordinates and the specification of the polygonal arc representing line I=value with the index in crus=value.
On entry, the sum of absolute values of all numbers of line segments is different from nlines. The sum of all the elements of nlcomp=value. nlines=value.
ifail=2
An error has occurred during the generation of the boundary mesh. It appears that nedmx is not large enough: nedmx=value.
ifail=3
An error has occurred during the generation of the boundary mesh. It appears that nvmax is not large enough: nvmax=value.
ifail=4
An error has occurred during the generation of the boundary mesh. Check the definition of each line (the argument lined) and each connected component of the boundary (the arguments nlcomp, and lcomp, as well as the coordinates of the characteristic points. Setting itrace>0 may provide more details.
ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
ifail=-399
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
ifail=-999
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

Not applicable.

8 Parallelism and Performance

d06baf is not threaded in any implementation.

9 Further Comments

The boundary mesh generation technique in this routine has a ‘tree’ structure. The boundary should be partitioned into geometrically simple segments (straight lines or curves) delimited by characteristic points. Then, the lines should be assembled into connected components of the boundary domain.
Using this strategy, the inputs to that routine can be built up, following the requirements stated in Section 5:
The example below details the use of this strategy.

10 Example

The NAG logo is taken as an example of a geometry with holes. The boundary has been partitioned in 40 lines characteristic points; including 4 for the exterior boundary and 36 for the logo itself. All line geometry specifications have been considered, see the description of lined, including 4 lines defined as polygonal arc, 4 defined by fbnd and all the others are straight lines.

10.1 Program Text

Program Text (d06bafe.f90)

10.2 Program Data

Program Data (d06bafe.d)

10.3 Program Results

Program Results (d06bafe.r)
GnuplotProduced by GNUPLOT 4.6 patchlevel 3 Example Program Boundary Mesh of the NAG Logo with 259 Nodes and 259 Edges gnuplot_plot_1
GnuplotProduced by GNUPLOT 4.6 patchlevel 3 Final Mesh Built Using the Delaunay-Voronoi Method gnuplot_plot_1
GnuplotProduced by GNUPLOT 4.6 patchlevel 3 Final Mesh Built Using the Advancing Front Method gnuplot_plot_1