geometry: Mesh Generation and Surface Tessellation

Kai Habel, Raoul Grasman, Robert B. Gramacy, Pavlo Mozharovskyi, David C. SterrattOpenalex Unknown 2005 · DOI · OpenAlex

Abstract

The geometry package makes the 'Qhull' library available in R, providing a robust suite for computing convex hulls, Delaunay triangulations, Voronoi diagrams, and more across $N$ dimensions. While Qhull primarily focuses on convex geometry, the package extends its utility with R functions for mesh generation of non-convex objects and constrained triangulations, bridging a critical gap for R users in spatial statistics and physical modeling.

Introduction

In computational geometry, partitioning space or defining the envelope of a point cloud is fundamental to fields like spatial statistics and fluid dynamics. While the C++ Qhull library serves as the industry standard for these operations, R users previously lacked a high-dimensional interface comparable to those in MATLAB or Octave. The geometry package addresses this by providing a high-performance bridge to Qhull, alongside specialized iterative solvers like distmesh for complex, non-convex regions.

Core Methodologies

Qhull Integration and the Quickhull Algorithm

At its core, the package utilizes the Quickhull algorithm to compute convex hulls and tessellations. Unlike many geometric libraries restricted to 2D or 3D, geometry scales to $N$ dimensions, enabling multi-parameter optimization and high-dimensional data analysis.

The DistMesh Algorithm

For non-convex domains where standard Delaunay triangulations fail, the package implements distmesh. This approach treats mesh edges as bars in a truss structure, using a force-displacement relaxation scheme to "push" nodes into an optimal distribution that respects complex boundaries.

Coordinate Transformations and Interpolation

A significant feature of the package is its support for rigorous mathematical transformations between Cartesian, Polar, Spherical, and Barycentric coordinates. Barycentric coordinates are particularly vital for interpolating data across triangular or tetrahedral meshes.

Input parameters for barycentric to Cartesian conversion, showing the $M \times (N+1)$ matrix representation of barycentric coordinates.

The package defines specific matrix structures for these operations. For instance, converting between coordinate systems requires a reference simplex $X$ and a matrix of points. The dimensionality of these matrices reflects the mathematical properties of the coordinate systems involved.

Input parameters for Cartesian to barycentric conversion, showing the $M \times N$ matrix representation of Cartesian points.

Key Insights and Performance

The package achieves feature parity with MATLAB/Octave, facilitating easier code porting for researchers. By leveraging Rcpp, it maintains the computational speed of compiled C++ while offering the interactive flexibility of R. Integration with the rgl package further allows for real-time, interactive 3D visualization of complex tetrahedral meshes.

Limitations and Future Work

Currently, native support for constrained Delaunay triangulations is limited, though distmesh provides a functional workaround. Future development aims to port the $N$-dimensional distmesh implementation into pure C++ to enhance performance for large-scale problems. Additionally, functions like halfspacen remain under active development to improve robustness in edge cases.

Summary updated

Abstract

Makes the 'Qhull' library &lt;<a href="http://www.qhull.org" target="_top">http://www.qhull.org</a>&gt; available in R, in a similar manner as in Octave and MATLAB. Qhull computes convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams. It runs in 2D, 3D, 4D, and higher dimensions. It implements the Quickhull algorithm for computing the convex hull. Qhull does not support constrained Delaunay triangulations, or mesh generation of non-convex objects, but the package does include some R functions that allow for this.
BibTeX
@inproceedings{habel2005geometry,
  author = {Kai Habel and Raoul Grasman and Robert B. Gramacy and Pavlo Mozharovskyi and David C. Sterratt},
  title = {{geometry: Mesh Generation and Surface Tessellation}},
  booktitle = {Openalex Unknown},
  year = {2005},
  doi = {10.32614/cran.package.geometry},
}
Figure