Algorithm 751: TRIPACK: a constrained two-dimensional Delaunay triangulation package

ABSTRACT

TRIPACK is a Fortran 77 software package that employs an incremental algorithm to construct a constrained Delaunay traingulation 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 triangles are distinguishable from those in the remainder of the triangulation. This effectively allows for a nonconvex or multiply connected triangulation (the complement of the union of constraint regions) while retaining the efficiency of searching and updating a convex triangulation. The package provides a wide range of capabilities including an efficient means of updating the triangulation with nodal additions or deletions. For N nodes, the storage requirement is 13N integer storage locations in addition to the 2N nodal coordinates.

REFERENCES

• 1: CLINE, A. K. AND RENKA, R.J. 1984. A storage-efficient method for construction of a Thiessen triangulation. Rocky Mount. J. Math. 14, 1 (Winter), 119-139.
• 2: A. K. Cline , R. J. Renka, A constrained two-dimensional triangulation and the solution of closest node problems in the presence of barriers, SIAM Journal on Numerical Analysis, v.27 n.5, p.1305-1321, Oct. 1990 [doi>10.1137/0727074]
• 3: DELAUNAY, B. 1934. Sur la sph re vide. Bull. Acad. Sci. USSR(Vll), Classe Sci. Mat. Nat. 793-800.
• 4: LAWSOn, C.L. 1977. Software for C~ surface interpolation. In Mathematical Software III, J. R. Rice, Ed. Academic Press, New York, 161-194.
• 5: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms

Keywords:
constrained Delaunay triangulation, interpolation