This function generates a Delaunay triangulation of arbitrarily distributed points in the plane. The resulting object can be printed or plotted, some additional functions can extract details from it like the list of triangles, arcs or the convex hull.
tri.mesh(x, y = NULL, duplicate = "error", jitter = FALSE)an object of class "triSht", see triSht.
vector containing \(x\) coordinates of the data. If y is missing
x should be a list or dataframe with two components x
and y.
vector containing \(y\) coordinates of the data. Can be omitted if
x is a list with two components x and y.
flag indicating how to handle duplicate elements. Possible values are:
"error" -- default,
"strip" -- remove all duplicate points,
"remove" -- leave one point of the duplicate points.
logical, adds some jitter to both coordinates as this can
help in situations with too much colinearity. Default is FALSE.
Some error conditions within C++ code can also lead to enabling this
internally (a warning will be displayed).
Albrecht Gebhardt <albrecht.gebhardt@aau.at>, Roger Bivand <roger.bivand@nhh.no>
This function creates a Delaunay triangulation of a set of 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:
The triangle vertices are nodes.
No triangle contains a node other than its vertices.
The interiors of the triangles are pairwise disjoint.
The union of triangles is the convex hull of the set of nodes (the smallest convex set which contains the nodes).
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.
This triangulation is based on the s-hull algorithm by David Sinclair. It consist of two steps:
Create an initial non-overlapping triangulation from the radially sorted nodes (w.r.t to an arbitrary first node). Starting from a first triangle built from the first node and its nearest neigbours this is done by adding triangles from the next node (in the sense of distance to the first node) to the hull of the actual triangulation visible from this node (sweep hull step).
Apply triange flipping to each pair of triangles sharing a border until condition 5 holds (Cline-Renka test).
This algorithm has complexicity \(O(n*log(n))\).
B. Delaunay, Sur la sphere vide. A la memoire de Georges Voronoi, Bulletin de l'Academie des Sciences de l'URSS. Classe des sciences mathematiques et na, 1934, no. 6, p. 793--800
D. A. Sinclair, S-Hull: A Fast Radial Sweep-Hull Routine for Delaunay Triangulation. https://arxiv.org/pdf/1604.01428.pdf, 2016.
triSht, print.triSht, plot.triSht,
summary.triSht, triangles,
convex.hull, arcs.
## use Frankes datasets:
data(franke)
tr1 <- tri.mesh(franke$ds3$x, franke$ds3$y)
tr1
tr2 <- tri.mesh(franke$ds2)
summary(tr2)
Run the code above in your browser using DataLab