This subroutine provides for creation of a constrained
Delaunay triangulation which, in some sense, covers an
arbitrary connected region R rather than the convex hull
of the nodes. This is achieved simply by forcing the
presence of certain adjacencies (triangulation arcs) corresponding
to constraint curves. The union of triangles
coincides with the convex hull of the nodes, but triangles
in R can be distinguished from those outside of R. The
only modification required to generalize the definition of
the Delaunay triangulation is replacement of property 5
(refer to tri.mesh by the following:
5') If a node is contained in the interior of the circumcircle
of a triangle, then every interior point
of the triangle is separated from the node by a
constraint arc.
In order to be explicit, we make the following definitions.
A constraint region is the open interior of a
simple closed positively oriented polygonal curve defined
by an ordered sequence of three or more distinct nodes
(constraint nodes) P(1),P(2),...,P(K), such that P(I) is
adjacent to P(I+1) for I = 1,...,K with P(K+1) = P(1).
Thus, the constraint region is on the left (and may have
nonfinite area) as the sequence of constraint nodes is
traversed in the specified order. The constraint regions
must not contain nodes and must not overlap. The region
R is the convex hull of the nodes with constraint regions
excluded.
Note that the terms boundary node and boundary arc are
reserved for nodes and arcs on the boundary of the convex
hull of the nodes.
The algorithm is as follows: given a triangulation
which includes one or more sets of constraint nodes, the
corresponding adjacencies (constraint arcs) are forced to
be present (Fortran subroutine EDGE). Any additional new arcs
required are chosen to be locally optimal (satisfy the
modified circumcircle property).