Delaunay triangulation
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")
x |
vector containing x coordinates of the data. If |
y |
vector containing y coordinates of the data. Can be omitted if
|
duplicate |
flag indicating how to handle duplicate elements. Possible values are:
|
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)).
an object of class "triSht", see triSht.
This function is meant as a replacement for
tri.mesh from package tripack.
Please note that the underlying algorithm changed from Renka's method
to Sinclair's sweep hull method. Delaunay triangulations are unique if
no four or more points exist which share the same
circumcircle. Otherwise several solutions are available and different
algorithms will give different results. This especially holds for
regular grids, where in the case of rectangular gridded points each
grid cell can be triangulated in two different ways.
The arguments are backward compatible, but the returned object
is not compatible with package tripack (it
provides a tri object type)! But you
can apply methods with same names to the object returned in package
interp which is of type triSht, so you can reuse
your old code but you cannot reuse your old saved workspace.
Albrecht Gebhardt <albrecht.gebhardt@aau.at>, Roger Bivand <roger.bivand@nhh.no>
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.
## use Frankes datasets: data(franke) tr1 <- tri.mesh(franke$ds3$x, franke$ds3$y) tr1 tr2 <- tri.mesh(franke$ds2) summary(tr2)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.