Delaunay triangulation by Bowyer-Watson insertion

Each point in turn removes the triangles whose circumcircle contains it and re-links the cavity boundary to it (Bowyer 1981; Watson 1981). Coordinates are centred and scaled before insertion and the enclosing super-triangle is 1000 times the extent of the points. Per triangle: area, circumcentre, circumradius R, angles, the radius-edge ratio \(R / l_{min}\) (Shewchuk 2002) and the shape quality \(4\sqrt{3} A / \sum l^2\). The empty-circle property is checked directly and the triangles' total area is compared with the convex hull's.

Usage

DelaunayTriangulation(points)

Arguments

points

Distinct points (n x 2), n >= 3, not all collinear.

Value

List with triangles (1-based, counter-clockwise), edges, neighbours, adjacency, areas, circumcentres, circumradii, angles, min_angle, radius_edge, quality, empty_circle_violations, hull_area_gap.

References

Bowyer, A. (1981). Computing Dirichlet tessellations. Computer Journal 24, 162-166.

Watson, D. F. (1981). Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Computer Journal 24, 167-172.

Shewchuk, J. R. (2002). Delaunay refinement algorithms for triangular mesh generation. Computational Geometry 22, 21-74.

Examples

DelaunayTriangulation(rbind(c(0, 0), c(1, 0), c(0, 1), c(1, 1), c(0.5, 0.4)))$triangles
#>      [,1] [,2] [,3]
#> [1,]    1    2    5
#> [2,]    2    4    5
#> [3,]    3    1    5
#> [4,]    4    3    5