Algorithm 624: Triangulation and Interpolation at Arbitrarily Distributed Points in the Plane

Abstract

This algorithm is a 1966 American National Standard FORTRAN implementation of the methods discussed in [1] and The software consists of a set of triangulation modules (which have application in problems other than interpolation) and a set of interpolation modules that require the triangulation routines. The triangulation software constructs a Thiessen triangulatiofi of a set of N nodes (x,, y,), i = 1 ..... N, arbitrarily distributed in the x-y plane. Only 7N storage locations are required to represent the triangulation and the software provides the capability of updating the data structure with the addition of a new node. Given data values z, associated with the nodes, the interpolation problem is to construct a C 1 function F such that F(x,, y,) --z, for i = 1 ..... N.