const double crus[], Integer sdcrus, const double rate[], Integer ncomp, const Integer nlcomp[], const Integer lcomp[], Integer nvmax, Integer nedmx, Integer *nvb, double coor[], Integer *nedge, Integer edge[], Integer itrace, const char *outfile, Nag_Comm *comm, NagError *fail)

The function may be called by the names: d06bac, nag_mesh_dim2_gen_boundary or nag_mesh2d_bound.

3 Description

Given a closed connected subdomain

Ω

ℝ^{2}

, whose boundary

\partial Ω

is divided by characteristic points into

m

distinct line segments, d06bac generates a boundary mesh on

\partial Ω

. Each line segment may be a straight line, a curve defined by the equation

f (x, y) = 0

, or a polygonal curve defined by a set of given boundary mesh points.

This function is primarily designed for use with either d06aac (a simple incremental method) or d06abc (Delaunay–Voronoi method) or d06acc (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 function 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

\partial Ω

into lines).

Constraint:

nlines \geq 1

2: $coorch [2 \times nlines]$ – const double Input

Note: the

(i, j)

th element of the matrix is stored in

coorch [(j - 1) \times 2 + i - 1]

On entry:

coorch [(i - 1) \times 2]

contains the

x

coordinate of the

i

th characteristic point, for

i = 1, 2, \dots, nlines

; while

coorch [(i - 1) \times 2 + 1]

contains the corresponding

y

coordinate.

3: $lined [4 \times nlines]$ – const Integer Input

Note: the

(i, j)

th element of the matrix is stored in

lined [(j - 1) \times 4 + i - 1]

On entry: the description of the lines that define the boundary domain. The line

i

, for

i = 1, 2, \dots, m

, is defined as follows:

$lined [(i - 1) \times 4]$

The number of points on the line, including two end points.

$lined [(i - 1) \times 4 + 1]$

The first end point of the line. If

lined [(i - 1) \times 4 + 1] = j

, the coordinates of the first end point are those stored in

coorch [(j - 1) \times 2], coorch [(j - 1) \times 2 + 1]

$lined [(i - 1) \times 4 + 2]$

The second end point of the line. If

lined [(i - 1) \times 4 + 2] = k

, the coordinates of the second end point are those stored in

coorch [(k - 1) \times 2], coorch [(k - 1) \times 2 + 1]

$lined [(i - 1) \times 4 + 3]$

This defines the type of line segment connecting the end points. Additional information is conveyed by the numerical value of

lined [(i - 1) \times 4 + 3]

as follows:

(i) $lined [(i - 1) \times 4 + 3] > 0$ , the line is described in fbnd with $lined [(i - 1) \times 4 + 3]$ as the index. In this case, the line must be described in the trigonometric (anticlockwise) direction;
(ii) $lined [(i - 1) \times 4 + 3] = 0$ , the line is a straight line;
(iii)if $lined [(i - 1) \times 4 + 3] < 0$ , say (i.e., $lined [(i - 1) \times 4 + 3] = - p$ for some index $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 - 1) \times 2 + z], crus [(p - 1) \times 2 + z], crus [p \times 2 + z], \dots, crus [(p + r - 4) \times 2 + z], coorch [(k - 1) \times 2 + z]$ , where $z \in \{0, 1\}$ , $r = lined [(i - 1) \times 4]$ , $j = lined [(i - 1) \times 4 + 1]$ and $k = lined [(i - 1) \times 4 + 2]$ .

Constraints:

$2 \leq lined [(i - 1) \times 4]$ ;
$1 \leq lined [(i - 1) \times 4 + 1] \leq nlines$ ;
$1 \leq lined [(i - 1) \times 4 + 2] \leq nlines$ ;
$lined [(i - 1) \times 4 + 1] \neq lined [(i - 1) \times 4 + 2]$ , for $i = 1, 2, \dots, nlines$ .

For each line described by fbnd (lines with

lined [(i - 1) \times 4 + 3] > 0

, for

i = 1, 2, \dots, nlines

) the two end points (

lined [(i - 1) \times 4 + 1]

and

lined [(i - 1) \times 4 + 2]

) lie on the curve defined by index

lined [(i - 1) \times 4 + 3]

in fbnd, i.e.,

fbnd (lined [(i - 1) \times 4 + 3], coorch [(lined [(i - 1) \times 4 + 1] - 1) \times 2], coorch [(lined [(i - 1) \times 4 + 1] - 1) \times 2 + 1], comm) = 0;

fbnd (lined [(i - 1) \times 4 + 3], coorch [(lined [(i - 1) \times 4 + 2] - 1) \times 2], coorch [(lined [(i - 1) \times 4 + 2] - 1) \times 2 + 1], comm) = 0

, for

i = 1, 2, \dots, nlines

For all lines described as polygonal arcs (lines with

lined [(i - 1) \times 4 + 3] < 0

, for

i = 1, 2, \dots, nlines

) the sets of intermediate points (i.e.,

[- lined [(i - 1) \times 4 + 3] : - lined [(i - 1) \times 4 + 3] + lined [(i - 1) \times 4] - 3]

for all

i

such that

lined [(i - 1) \times 4 + 3] < 0

) are not overlapping. This can be expressed as:

- lined [(i - 1) \times 4 + 3] + lined [(i - 1) \times 4] - 3 = \sum_{\{i, lined [(i - 1) \times 4 + 3] < 0\}} \{lined [(i - 1) \times 4] - 2\}

- lined [(i - 1) \times 4 + 3] + lined [(i - 1) \times 4] - 2 = - lined [(j - 1) \times 4 + 3],

for a

j

such that

j = 1, 2, \dots, nlines

j \neq i

and

lined [(j - 1) \times 4 + 3] < 0

4: $fbnd$ – function, supplied by the user External Function

fbnd must be supplied to calculate the value of the function which describes the curve

\{(x, y) \in ℝ^{2}; such that ​ f (x, y) = 0\}

on segments of the boundary for which

lined [(i - 1) \times 4 + 3] > 0

. If there are no boundaries for which

lined [(i - 1) \times 4 + 3] > 0

fbnd will never be referenced by d06bac, in which case fbnd may be NULLFN.

The specification of fbnd is:

double

fbnd (Integer i, double x, double y, Nag_Comm *comm)

1: $i$ – Integer Input

On entry:

lined [(i - 1) \times 4 + 3]

, the reference index of the line (portion of the contour)

i

described.

2: $x$ – double Input

3: $y$ – double Input

On entry: the values of

x

and

y

at which

f (x, y)

is to be evaluated.

4: $comm$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to fbnd.

user – double *
iuser – Integer *
p – Pointer: The type Pointer will be void *. Before calling d06bac you may allocate memory and initialize these pointers with various quantities for use by fbnd when called from d06bac (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

Note: fbnd should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by d06bac. If your code inadvertently does return any NaNs or infinities, d06bac is likely to produce unexpected results.

5: $crus [2 \times sdcrus]$ – const double Input

Note: the

(i, j)

th element of the matrix is stored in

crus [(j - 1) \times 2 + i - 1]

On entry: the coordinates of the intermediate points for polygonal arc lines. For a line

i

defined as a polygonal arc (i.e.,

lined [(i - 1) \times 4 + 3] < 0

), if

p = - lined [(i - 1) \times 4 + 3]

crus [(k - 1) \times 2]

, for

k = p, \dots, p + lined [(i - 1) \times 4] - 3

, must contain the

x

coordinate of the consecutive intermediate points for this line. Similarly

crus [(k - 1) \times 2 + 1]

, for

k = p, \dots, p + lined [(i - 1) \times 4] - 3

, must contain the corresponding

y

coordinate.

6: $sdcrus$ – Integer Input

On entry: the half dimension of the array crus as declared in the function from which d06bac is called.

Constraint:

sdcrus \geq \sum_{\{i, lined [(i - 1) \times 4 + 3] < 0\}} \{lined [(i - 1) \times 4] - 2\}

7: $rate [nlines]$ – const double Input

On entry:

rate [i - 1]

is the geometric progression ratio between the points to be generated on the line

i

, for

i = 1, 2, \dots, m

and

lined [(i - 1) \times 4 + 3] \geq 0

lined [(i - 1) \times 4 + 3] < 0

rate [i - 1]

is not referenced.

Constraint: if

lined [(i - 1) \times 4 + 3] \geq 0

rate [i - 1] > 0.0

, for

i = 1, 2, \dots, nlines

8: $ncomp$ – Integer Input

On entry:

n

, the number of separately connected components of the boundary.

Constraint:

ncomp \geq 1

9: $nlcomp [ncomp]$ – const Integer Input

On entry:

|nlcomp [k - 1]|

is the number of line segments in component

k

of the contour. The line

i

of component

k

runs in the direction

lined [(i - 1) \times 4 + 1]

lined [(i - 1) \times 4 + 2]

nlcomp [k - 1] > 0

, and in the opposite direction otherwise; for

k = 1, 2, \dots, n

Constraints:

$1 \leq |nlcomp [k - 1]| \leq nlines$ , for $k = 1, 2, \dots, ncomp$ ;
$\sum_{k = 1}^{n} |nlcomp [k - 1]| = nlines$ .

10: $lcomp [nlines]$ – const Integer Input

On entry: lcomp must contain the list of line numbers for the each component of the boundary. Specifically, the line numbers for the

k

th component of the boundary, for

k = 1, 2, \dots, ncomp

, must be in elements

l 1 - 1

l 2 - 1

of lcomp, where

l 2 = \sum_{i = 1}^{k} |nlcomp [i - 1]|

and

l 1 = l 2 + 1 - |nlcomp [k - 1]|

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:

nvmax \geq nlines

12: $nedmx$ – Integer Input

On entry: the maximum number of boundary edges in the boundary mesh to be generated.

Constraint:

nedmx \geq 1

13: $nvb$ – Integer * Output

On exit: the total number of boundary mesh vertices generated.

14: $coor [2 \times nvmax]$ – double Output

Note: the

(i, j)

th element of the matrix is stored in

coor [(j - 1) \times 2 + i - 1]

On exit:

coor [(i - 1) \times 2]

will contain the

x

coordinate of the

i

th boundary mesh vertex generated, for

i = 1, 2, \dots, nvb

; while

coor [(i - 1) \times 2 + 1]

will contain the corresponding

y

coordinate.

15: $nedge$ – Integer * Output

On exit: the total number of boundary edges in the boundary mesh.

16: $edge [3 \times nedmx]$ – Integer Output

Note: the

(i, j)

th element of the matrix is stored in

edge [(j - 1) \times 3 + i - 1]

On exit: the specification of the boundary edges.

edge [(j - 1) \times 3]

and

edge [(j - 1) \times 3 + 1]

will contain the vertex numbers of the two end points of the

j

th boundary edge.

edge [(j - 1) \times 3 + 2]

is a reference number for the

j

th boundary edge and

$edge [(j - 1) \times 3 + 2] = lined [(i - 1) \times 4 + 3]$ , where $i$ and $j$ are such that the $j$ th edges is part of the $i$ th line of the boundary and $lined [(i - 1) \times 4 + 3] \geq 0$ ;
$edge [(j - 1) \times 3 + 2] = 100 + |lined [(i - 1) \times 4 + 3]|$ , where $i$ and $j$ are such that the $j$ th edges is part of the $i$ th line of the boundary and $lined [(i - 1) \times 4 + 3] < 0$ .

Note that the edge vertices are numbered from

1

to nvb.

17: $itrace$ – Integer Input

On entry: the level of trace information required from d06bac.

$itrace = 0$ or $itrace < - 1$: No output is generated.
$itrace = 1$: Output from the boundary mesh generator is printed. 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 function, calling either d06aac, d06abc or d06acc.
$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: $outfile$ – const char * Input

On entry: the name of a file to which diagnostic output will be directed. If outfile is NULL the diagnostic output will be directed to standard output.

19: $comm$ – Nag_Comm *

The NAG communication argument (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

20: $fail$ – NagError * Input/Output

The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_INT: On entry, $ncomp = 〈value〉$ .
Constraint: $ncomp \geq 1$ .

On entry, $nedmx = 〈value〉$ .
Constraint: $nedmx \geq 1$ .

On entry, $nlines = 〈value〉$ .
Constraint: $nlines \geq 1$ .
NE_INT_2: On entry, $nvmax = 〈value〉$ and $nlines = 〈value〉$ .
Constraint: $nvmax \geq nlines$ .

On entry, $sdcrus = 〈value〉$ and $nusmin = 〈value〉$ .
Constraint: $sdcrus \geq nusmin$ .

On entry, the line list for the separate connected component of the boundary is badly set: $lcomp [l - 1] = 〈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〉$ .
NE_INT_3: On entry, the absolute number of line segments in the $k$ th component of the contour should be less than or equal to nlines and greater than $0$ . $k = 〈value〉$ , $nlcomp [k - 1] = 〈value〉$ and $nlines = 〈value〉$ .

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〉$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_MESH_ERROR: 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.

An error has occurred during the generation of the boundary mesh. It appears that nedmx is not large enough: $nedmx = 〈value〉$ .

An error has occurred during the generation of the boundary mesh. It appears that nvmax is not large enough: $nvmax = 〈value〉$ .

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〉$ , $f (x, 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〉$ , $f (x, y) = 〈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.
NE_NO_LICENCE: Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_NOT_CLOSE_FILE: Cannot close file $〈value〉$ .
NE_NOT_WRITE_FILE: Cannot open file $〈value〉$ for writing.

7 Accuracy

Not applicable.

8 Parallelism and Performance

d06bac is not threaded in any implementation.

9 Further Comments

The boundary mesh generation technique in this function 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 function can be built up, following the requirements stated in Section 5:

the characteristic and the user-supplied intermediate points:
- nlines, sdcrus, coorch and crus;
the characteristic lines:
- lined, fbnd, rate;
finally the assembly of lines into the connected components of the boundary:
- ncomp, and
- nlcomp, lcomp.

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.

Interfaces: FL CL AD

NAG CL Interface Introduction

D06 (Mesh) Chapter Contents

D06 (Mesh) Chapter Introduction

d06ba: FL CL AD

NAG CL Interfaced06bac (dim2_​gen_​boundary)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG CL Interface
d06bac (dim2_gen_boundary)