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.
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.
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