Meshes: 3-D Delaunay tetrahedralisation, 3-D Voronoi cells, Ruppert refinement

Delaunay3D: Bowyer-Watson insertion into a super-tetrahedron; tetrahedra whose circumspheres contain the new point are removed and the cavity is re-triangulated from its boundary faces. Returns sorted 1-based index rows and the circumcentres. Voronoi3D: the dual; cell vertices are circumcentres of the incident tetrahedra, hull points have unbounded cells (volume Inf), and a bounded cell has volume sum_j A_ij |x_i - x_j| / 6 over its faces. RuppertRefine: splits encroached convex hull segments at midpoints and inserts circumcentres of skinny triangles (circumradius to shortest edge above 1 / (2 sin(min_angle))) until every angle is at least min_angle degrees or max_points is reached.

Usage

Delaunay3D(points)

Voronoi3D(points)

RuppertRefine(points, min_angle = 20, max_points = 500)

Arguments

points: Matrix of points (n x 3, or n x 2 for RuppertRefine).
min_angle: Target minimum angle in degrees (at most about 20.7).
max_points: Maximum number of vertices.

Value

A list.

References

Bowyer, A. (1981). Computing Dirichlet tessellations. Computer J. 24, 162-166. Watson, D. F. (1981). Computer J. 24, 167-172. Okabe, A., Boots, B., Sugihara, K. and Chiu, S. N. (2000). Spatial Tessellations, 2nd ed. Ruppert, J. (1995). A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J. Algorithms 18, 548-585. Shewchuk, J. R. (2002). Computational Geometry 22, 21-74.

Examples

Delaunay3D(rbind(c(0, 0, 0), c(1, 0, 0), c(0, 1, 0), c(0, 0, 1), c(1, 1, 1.2)))$tetrahedra
#>      [,1] [,2] [,3] [,4]
#> [1,]    1    2    3    4
#> [2,]    2    3    4    5
RuppertRefine(rbind(c(0, 0), c(4, 0), c(4, 1), c(0, 1)))$min_angle
#> [1] 26.56505