tri.mesh: Create a delaunay triangulation

In tripack: Triangulation of Irregularly Spaced Data

Create a delaunay triangulation

Description

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 well-suited for solving closest point problems and for triangle-based interpolation.

The triangulation can be generalized to a constrained Delaunay triangulation by a call to add.constraint. This allows for user-specified 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.

Usage

tri.mesh(x, y = NULL, duplicate = "error",
         jitter = 10^-12, jitter.iter = 6, jitter.random = FALSE)

Arguments

x	vector containing x coordinates of the data. If y is missing x should contain two elements $x and $y.
y	vector containing y coordinates of the data.
duplicate	flag indicating how to handle duplicate elements. Possible values are: "error" – default, "strip" – remove all duplicate points, "remove" – leave one point of duplicate points.
jitter	Jitter of amount of diff(range(XX))*jitter (XX=x or y) will be added to coordinates if collinear points are detected. Afterwards interpolation will be tried once again. Note that the jitter is not generated randomly unless jitter.random is set to TRUE. This ensures reproducable results. interp of package akima uses the same jitter mechanism. That means you can plot the triangulation on top of the interpolation and see the same triangulation as used for interpolation, see examples for interp.
jitter.iter	number of iterations to retry with jitter, amount will be increased in each iteration by iter^1.5
jitter.random	logical, see jitter, defaults to FALSE

Value

An object of class "tri"

Note

There is re-implementation of this function available in package interp under the same name with the same arguments. But the return value is of a different class. So returned objects from this function can not be used by functions of same name in package interp. But code written to use functions from this package can be reused with the new package unless a constrained triangulation is wanted. This is the only thing missing in the new implementation.

References

R. J. Renka (1996). Algorithm 751: TRIPACK: a constrained two-dimensional Delaunay triangulation package. ACM Transactions on Mathematical Software. 22, 1-8.

See Also

tri, print.tri, plot.tri, summary.tri, triangles, convex.hull, neighbours, add.constraint.

Examples

data(tritest)
tritest.tr<-tri.mesh(tritest$x,tritest$y)
tritest.tr

tripack documentation built on Oct. 21, 2024, 5:07 p.m.