ALGORITHM 751 - TRIPACK - A CONSTRAINED 2-DIMENSIONAL DELAUNAY TRIANGULATION PACKAGE

TRIPACK is a Fortran 77 software package that employs an incremental a lgorithm to construct a constrained Delaunay triangulation of a set of points in the plane (nodes). The triangulation covers the convex hull of the nodes but may include polygonal constraint regions whose trian gles are distinguishable from those in the remainder of the triangulat ion. This effectively allows for a nonconvex or multiply connected tri angulation (the complement of the union of constraint regions) while r etaining the efficiency of searching and updating a convex triangulati on. The package provides a wide range of capabilities including an eff icient means of updating the triangulation with nodal additions or del etions. For N nodes, the storage requirement is 13N integer storage lo cations in addition to the 2N nodal coordinates.