This subroutine creates a Delaunay triangulation of a set of N arbitrarily distributed points in the plane referred to as nodes. The Delaunay triangulation is defined as a set of triangles with the following five properties:
1) The triangle vertices are nodes.
2) No triangle contains a node other than its vertices.
3) The interiors of the triangles are pairwise disjoint.
4) The union of triangles is the convex hull of the set of nodes (the smallest convex set which contains the nodes).
5) The interior of the circumcircle of each triangle contains no node.
The first four properties define a triangulation, and the last property results in a triangulation which is as close as possible to equiangular in a certain sense and which is uniquely defined unless four or more nodes lie on a common circle. This property makes the triangulation wellsuited for solving closest point problems and for trianglebased interpolation.
The triangulation can be generalized to a constrained
Delaunay triangulation by a call to add.constraint
.
This allows for userspecified boundaries defining a nonconvex
and/or multiply connected region.
The operation count for constructing the triangulation is close to O(N) if the nodes are presorted on X or Y components. Also, since the algorithm proceeds by adding nodes incrementally, the triangulation may be updated with the addition (or deletion) of a node very efficiently. The adjacency information representing the triangulation is stored as a linked list requiring approximately 13N storage locations.
1 2 
x 
vector containing x coordinates of the data. If 
y 
vector containing y coordinates of the data. 
duplicate 
flag indicating how to handle duplicate elements.
Possible values are: 
jitter 
Jitter of amount of Note that the jitter is not generated randomly unless

jitter.iter 
number of iterations to retry with jitter, amount
will be increased in each iteration by 
jitter.random 
logical, see 
An object of class "tri"
R. J. Renka (1996). Algorithm 751: TRIPACK: a constrained twodimensional Delaunay triangulation package. ACM Transactions on Mathematical Software. 22, 18.
tri
, print.tri
, plot.tri
,
summary.tri
, triangles
,
convex.hull
, neighbours
,
add.constraint
.
1 2 3 
Questions? Problems? Suggestions? Tweet to @rdrrHQ or email at ian@mutexlabs.com.
Please suggest features or report bugs with the GitHub issue tracker.
All documentation is copyright its authors; we didn't write any of that.