# triangulate¶

Delaunay triangulation or Voronoi partitioning and gridding of Cartesian data

## Synopsis¶

**gmt triangulate** [ *table* ]
[ **-A** ]
[ **-C***slpfile* ]
[ **-D****x**|**y** ]
[ **-E***empty* ]
[ **-G***outgrid* ]
[ **-I***increment* ]
[ **-J***parameters* ]
[ **-L***indexfile*[**+b**] ]
[ **-M** ]
[ **-N** ]
[ **-Q**[**n**] ]
[ **-R***region* ]
[ **-S**[*first*][**+z**[**a**|**l**|**m**|**p**|**u**]] ]
[ **-T** ]
[ **-V**[*level*] ]
[ **-Z** ]
[ **-b**binary ]
[ **-d**nodata[**+c***col*] ]
[ **-e**regexp ]
[ **-f**flags ]
[ **-h**headers ]
[ **-i**flags ]
[ **-qi**flags ]
[ **-r**reg ]
[ **-s**flags ]
[ **-w**flags ]
[ **-:**[**i**|**o**] ]
[ **--PAR**=*value* ]

**Note:** No space is allowed between the option flag and the associated arguments.

## Description¶

**triangulate** reads one or more ASCII [or binary] files (or standard
input) containing *x, y*[*, z*] and performs Delaunay triangulation, i.e., it
finds how the points should be connected to give the most equilateral
triangulation possible. If a map projection (give **-R** and **-J**) is
chosen then it is applied before the triangulation is calculated. By
default, the output is triplets of point id numbers that make up each
triangle and is written to standard output. The id numbers refer to the
points position (line number, starting at 0 for the first line) in the
input file. As an option, you may choose to create a multiple segment
file that can be piped through plot to draw the triangulation
network. If **-G** **-I** are set a grid will be calculated based on the
surface defined by the planar triangles. The actual algorithm used in
the triangulation is either that of *Watson* [1982] or *Shewchuk* [1996] [Default]
(if installed; type **gmt get GMT_TRIANGULATE** to see which method is
selected). This choice is made during the GMT installation. Furthermore,
if the Shewchuk algorithm is installed then you can also perform the
calculation of Voronoi polygons and optionally grid your data via the
natural nearest neighbor algorithm. Some Linux users may find their distribution
does not provide Shewchuk due to it not being released under a GNU License.
**Note**: For geographic data with
global or very large extent you should consider sphtriangulate
instead since **triangulate** is a Cartesian or small-geographic area operator
and is unaware of periodic or polar boundary conditions.

## Required Arguments¶

*table*One or more ASCII (or binary, see

**-bi**[*ncols*][*type*]) data table file(s) holding a number of data columns. If no tables are given then we read from standard input.

## Optional Arguments¶

**-A**Compute the area of the Cartesian triangles and append the areas in the output segment headers [no areas calculated]. Requires

**-S**and is not compatible with**-Q**.

**-C***slpfile*Read a slope grid (in degrees) and compute the propagated uncertainty in the bathymetry using the CURVE algorithm [

*Zambo et al.*, 2016]. Requires the**-G**option to specify the output grid. Note that the*slpgrid*sets the domain for the output grid so**-R**,**-I**, [**-r**reg] are not required. Cannot be used in conjunction with**-D**,**-F**,**-M**,**-N**,**-Q**,**-S**and**-T**.

**-Dx**|**y**Take either the

*x*- or*y*-derivatives of surface represented by the planar facets (only used when**-G**is set).

**-E***empty*Set the value assigned to empty nodes when

**-G**is set [NaN].

**-G***outgrid*[=*ID*][**+d***divisor*][**+n***invalid*][**+o***offset*|**a**][**+s***scale*|**a**][:*driver*[*dataType*][**+c***options*]]

Use triangulation to grid the data onto an even grid (specified with

-Rand-I). Append the name of the output grid file. The interpolation is performed in the original coordinates, so if your triangles are close to the poles you are better off projecting all data to a local coordinate system before usingtriangulate(this is true of all gridding routines) or instead selectsphtriangulate. For natural nearest neighbor gridding you must add-Qn. Optionally, append =IDfor writing a specific file format (See full description). The following modifiers are supported:

+d- Divide data values by givendivisor[Default is 1].

+n- Replace data values matchinginvalidwith a NaN.

+o- Offset data values by the givenoffset, or appendafor automatic range offset to preserve precision for integer grids [Default is 0].

+s- Scale data values by the givenscale, or appendafor automatic scaling to preserve precision for integer grids [Default is 1].

Note: Any offset is added before any scaling.+saalso sets+oa(unless overridden). To write specific formats via GDAL, use =gdand supplydriver(and optionallydataType) and/or one or more concatenated GDAL-cooptions using+c. See the “Writing grids and images” cookbook section for more details.

**-I***x_inc*[**+e**|**n**][/*y_inc*[**+e**|**n**]]Set the grid spacing as

*x_inc*[and optionally*y_inc*].**Geographical (degrees) coordinates**: Optionally, append an increment unit. Choose among:**m**to indicate arc minutes**s**to indicate arc seconds**e**(meter),**f**(foot),**k**(km),**M**(mile),**n**(nautical mile) or**u**(US survey foot), in which case the increment will be converted to the equivalent degrees longitude at the middle latitude of the region (the conversion depends on PROJ_ELLIPSOID). If*y_inc*is not given or given but set to 0 it will be reset equal to*x_inc*; otherwise it will be converted to degrees latitude.

**All coordinates**: The following modifiers are supported:**+e**to slightly adjust the max*x*(*east*) or*y*(*north*) to fit exactly the given increment if needed [Default is to slightly adjust the increment to fit the given domain].**+n**to define the*number of nodes*rather than the increment, in which case the increment is recalculated from the number of nodes, the*registration*(see GMT File Formats), and the domain.**Note**: If**-R***grdfile*is used then the grid spacing and the registration have already been initialized; use**-I**and**-R**to override these values.

**-J***parameters*Specify the projection. (See full description) (See cookbook summary) (See projections table).

**-L***indexfile*[**+b**]Give name of file with previously computed Delaunay information. Each record must contain triplets of node numbers for a triangle in the input

*table*[Default computes these using Delaunay triangulation]. If the*indexfile*is binary and can be read the same way as the binary input*table*then you can append**+b**to spead up the reading [Default reads nodes as ASCII].

**-M**Output triangulation network as multiple line segments separated by a segment header record.

**-N**Used in conjunction with

**-G**to also write the triplets of the ids of all the Delaunay vertices [Default only writes the grid].

**-Q**[**n**]Output the edges of the Voronoi cells instead [Default is Delaunay triangle edges]. Requires

**-R**and is only available if linked with the*Shewchuk*[1996] library. Note that**-Z**is ignored on output. Optionally, append directive**n**for combining the edges into closed Voronoi polygons.

**-R***xmin*/*xmax*/*ymin*/*ymax*[**+r**][**+u***unit*]Specify the region of interest. (See full description) (See cookbook information).

**-S**[*first*][**+z**[**a**|**l**|**m**|**p**|**u**]]Output triangles as polygon segments separated by a segment header record which contains node numbers

*a-b-c*and**-Z***polynumber*. Optionally, append*first*, where*first*is an integer, to report the polygon numbers by counting from*first*[Default starts at zero]. Incompatible with**-Q**. Alternatively, use modifier**+z**to instead request that**-Z***zvalue*is placed in the segment headers, where*zvalue*is the mean of the three nodes’*z*values. Append**l**(lowest value),**m**(median),**p**(mode) or**u**(upper value) to select another representative*zvalue*[Default is**a**for mean].**Note**: Modifier**+z**implies**-Z**.

**-T**Output edges or polygons even if gridding has been selected with the

**-G**option [Default will not output the triangulation or Voronoi polygons is gridding is selected].

**-V**[*level*]Select verbosity level [

**w**]. (See full description) (See cookbook information).

**-Z**Controls whether we read (

*x,y*) or (*x,y,z*) data and if*z*should be output when**-M**or**-S**(without**+z**) are used [Read (*x,y*) only].

**-bi***record*[**+b**|**l**] (more …)Select native binary format for primary table input. [Default is 2 input columns].

**-bo***record*[**+b**|**l**] (more …)Select native binary format for table output. [Default is same as input]. Node ids are stored as double triplets.

**-d**[**i**|**o**][**+c***col*]*nodata*(more …)Replace input columns that equal

*nodata*with NaN and do the reverse on output.

**-e**[**~**]*“pattern”*|**-e**[**~**]/*regexp*/[**i**] (more …)Only accept data records that match the given pattern.

**-f**[**i**|**o**]*colinfo*(more …)Specify data types of input and/or output columns.

**-h**[**i**|**o**][*n*][**+c**][**+d**][**+m***segheader*][**+r***remark*][**+t***title*] (more …)Skip or produce header record(s).

**-i***cols*[**+l**][**+d***divisor*][**+s***scale*|**d**|**k**][**+o***offset*][,*…*][,**t**[*word*]] (more …)Select input columns and transformations (0 is first column,

**t**is trailing text, append*word*to read one word only).

**-qi**[~]*rows*|*limits*[**+c***col*][**+a**|**t**|**s**] (more …)Select input rows or data limit(s) [default is all rows].

**-s**[*cols*][**+a**][**+r**] (more …)Set handling of NaN records for output.

**-wy**|**a**|**w**|**d**|**h**|**m**|**s**|**c***period*[/*phase*][**+c***col*] (more …)Convert an input coordinate to a cyclical coordinate.

**-:**[**i**|**o**] (more …)Swap 1st and 2nd column on input and/or output.

**-^**or just**-**Print a short message about the syntax of the command, then exit (

**Note**: on Windows just use**-**).**-+**or just**+**Print an extensive usage (help) message, including the explanation of any module-specific option (but not the GMT common options), then exit.

**-?**or no argumentsPrint a complete usage (help) message, including the explanation of all options, then exit.

**--PAR**=*value*Temporarily override a GMT default setting; repeatable. See gmt.conf for parameters.

## ASCII Format Precision¶

The ASCII output formats of numerical data are controlled by parameters
in your gmt.conf file. Longitude and latitude are formatted
according to FORMAT_GEO_OUT, absolute time is
under the control of FORMAT_DATE_OUT and
FORMAT_CLOCK_OUT, whereas general floating point values are formatted
according to FORMAT_FLOAT_OUT. Be aware that the format in effect
can lead to loss of precision in ASCII output, which can lead to various
problems downstream. If you find the output is not written with enough
precision, consider switching to binary output (**-bo** if available) or
specify more decimals using the FORMAT_FLOAT_OUT setting.

## Grid Values Precision¶

Regardless of the precision of the input data, GMT programs that create grid files will internally hold the grids in 4-byte floating point arrays. This is done to conserve memory and furthermore most if not all real data can be stored using 4-byte floating point values. Data with higher precision (i.e., double precision values) will lose that precision once GMT operates on the grid or writes out new grids. To limit loss of precision when processing data you should always consider normalizing the data prior to processing.

## Inside/outside Status¶

To determine if a point is inside, outside, or exactly on the boundary of a polygon we need to balance the complexity (and execution time) of the algorithm with the type of data and shape of the polygons. For any Cartesian data we use a non-zero winding algorithm, which is quite fast. For geographic data we will also use this algorithm as long as (1) the polygons do not include a geographic pole, and (2) the longitude extent of the polygons is less than 360. If this is the situation we also carefully adjust the test point longitude for any 360 degree offsets, if appropriate. Otherwise, we employ a full spherical ray-shooting method to determine a points status.

## Examples¶

**Note**: Below are some examples of valid syntax for this module.
The examples that use remote files (file names starting with `@`

)
can be cut and pasted into your terminal for testing.
Other commands requiring input files are just dummy examples of the types
of uses that are common but cannot be run verbatim as written.

To triangulate the points in the file samples.xyz, store the triangle information in a binary file, and make a grid for the given area and spacing, use

```
gmt triangulate samples.xyz -bo -R0/30/0/30 -I2 -Gsurf.nc > samples.ijk
```

To draw the optimal Delaunay triangulation network based on the same file using a 15-cm-wide Mercator map, use

```
gmt triangulate samples.xyz -M -R-100/-90/30/34 -JM15c | gmt plot -R-100/-90/30/34 -JM15c -W0.5p -B1 -pdf network
```

To instead plot the Voronoi cell outlines, try

```
gmt triangulate samples.xyz -M -Q -R-100/-90/30/34 -JM15c | gmt plot -R-100/-90/30/34 -JM15c -W0.5p -B1 -pdf cells
```

To combine the Voronoi outlines into polygons and paint them according to their ID, try

```
gmt triangulate samples.xyz -M -Qn -R-100/-90/30/34 -JM15c | \
gmt plot -R-100/-90/30/34 -JM15c -W0.5p+cf -B1 -Ccolors.cpt -pdf polygons
```

To grid the data using the natural nearest neighbor algorithm, try

```
gmt triangulate samples.xyz -Gnnn.nc -Qn -R-100/-90/30/34 -I0.5
```

## Notes¶

The uncertainty propagation for bathymetric grids requires both horizontal
and vertical uncertainties and these are weighted given the local slope.
See the *Zambo et al.* [2014] and *Zhou and Liu* [2004] references for more details.

## See Also¶

gmt, greenspline, nearneighbor, contour, sphdistance, sphinterpolate, sphtriangulate, surface

## References¶

Shewchuk, J. R., 1996, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, First Workshop on Applied Computational Geometry (Philadelphia, PA), 124-133, ACM, May 1996.

Watson, D. F., 1982, Acord: Automatic contouring of raw data, *Comp. &
Geosci.*, **8**, 97-101.

Zambo, S., Elmore, P. A., Bourgeois, B. S., and Perkins, A. L., 2016, Uncertainty estimation for sparse data gridding algorithms, Proceedings of the U.S. Hydro Conference,National Harbor, MD, 16-19 March 2015.

Zhou, Q., and Liu, X., 2004, Error analysis on grid-based slope and aspect
algorithms, *Photogrammetric Eng. & Remote Sensing*, **70** (8), 957-962.