The TRIANGULATE procedure constructs a Delaunay triangulation of a planar set of points. Delaunay triangulations are very useful for the interpolation, analysis, and visual display of irregularly-gridded data. In most applications, after the irregularly gridded data points have been triangulated, the function TRIGRID is invoked to interpolate surface values to a regular grid.

Since Delaunay triangulations have the property that the circumcircle of any triangle in the triangulation contains no other vertices in its interior, interpolated values are only computed from nearby points.

TRIANGULATE can, optionally, return the adjacency list that describes, for each node, the adjacent nodes in the Delaunay triangulation. With this list, the Voronoi polygon (the polygon described by the set of points which are closer to that node than to any other node) can be computed for each node. This polygon contains the area influenced by its associated node. Tiling of the region in this manner is also called Dirichlet, Wigner-Seithz, or Thiessen tessellation.

The grid returned by the TRIGRID function can be input to various routines such as SURFACE, TV, and CONTOUR. See the description of TRIGRID for an example.

TRIANGULATE and TRIDGRID can also be used to perform gridding and interpolation over the surface of a sphere. The interpolation is C 1 continuous, meaning that the result is continuous over both the function value and its first derivative. This feature is ideal for interpolating an irregularly-sampled dataset over part or all of the surface of the earth (or other (spherical) celestial bodies). Extrapolation outside the convex hull of sample points is also supported. To perform spherical gridding, you must include the FVALUE and SPHERE keywords described below. The spherical gridding technique used in IDL is based on the paper "Interpolation of Data on the Surface of a Sphere", R. Renka, Oak Ridge National Laboratory Report ORNL/CSD-108 , 1982.

Calling Sequence

TRIANGULATE, X, Y, Triangles [, B]



An array that contains the X coordinates of the points to be triangulated.


An array that contains the Y coordinates of the points to be triangulated. Parameters X and Y must have the same number of elements.


A named variable that, on exit, contains the list of triangles in the Delaunay triangulation of the points specified by X and Y . Triangles is a longword array dimensioned (3, Number-of-Triangles), where Triangles[0, i] , Triangles[1, i] , and Triangles[2, i] contain the indices of the vertices of the i -th triangle (i.e., X[Tr[*, i]] and Y[Triangles[*, i]] are the X and Y coordinates of the vertices of the i- th triangle).


An optional, named variable that, upon return, contains a list of the indices of the boundary points in counterclockwise order.



Set this keyword to a named variable in which the adjacency list for each of the N nodes (xy point) is returned. The list has the following form:

Each element i, i £ 0 < N , contains the starting index of the connectivity list for node i within the list array. To obtain the adjacency list for node i, extract the list elements from LIST[ i ] to LIST[ i +1]-1.

The adjacency list is ordered in the counter-clockwise direction. The first item on the list of boundary nodes is the subscript of the node itself. For interior nodes, the list contains the subscripts of the adjacent nodes in counter-clockwise order.

For example, the call:


returns the adjacency list in the variable LIST. The subscripts of the nodes adjacent to X[i] and Y[i] are contained in the array:

LIST[LIST[i] : LIST[i+1]-1]


Set this keyword to indicate that the X and Y arguments contain longitude and latitude coordinates specified in degrees. This keyword is only effective if the SPHERE keyword is also set. If DEGREES is not set, X and Y are assumed to be specified in radians when a spherical triangulation is performed.


Set this keyword to a named variable that contains sample values for each longitude/latitude point in a spherical triangulation. On output, the elements of FVALUE are rearranged to correspond to the new ordering of X and Y (as described in the SPHERE keyword, below). This reordered array can be passed to TRIGRID to complete the interpolation.


Set this keyword to a named variable to return a (2, n ) list of the indices of duplicated points. That is, for each i ,

X[REPEATS(0, i )] = X[REPEATS(1, i )]


Y[REPEATS(0, i )) = Y(REPEATS(1, i )]


Set this keyword to a named variable in which the results from a spherical triangulation are returned. This result is a structure that can be passed to TRIGRID to perform spherical gridding. The structure contains the 3D Cartesian locations sample points and the adjacency list that describes the triangulation.

When spherical triangulation is performed, X and Y are interpreted as longitude and latitude, in either degrees or radians (see the DEGREE keyword, above). Also, the order of the elements within the X and Y parameters is rearranged (see the FVALUE keyword, above).


For a examples using the TRIANGULATE routine, see the TRIGRID function.

See Also