Mesh Generation and Surface Tessellation

Makes the 'Qhull' library <> 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.


CHANGES IN VERSION 0.4.0 - Released 2019/02/18



  • Default options to delaunayn have been changed The Qc and Qz or Qx options have been added as defaults, making the default options "Qbb Qc Qt Qz" for 3 dimensions or less and "Qbb Qc Qt Qx" for 4 or more dimensions. This brings the R implementation into line with Octave, and very similar to matlab and scipy.spatial.Delaunayn .

  • New argument "output.options" for convhulln() and delaunayn(). Qhull options which affect output should be put in this string, e.g. delaunayn(ps, output.options="Fn Fa")

  • The "full" option to delaunayn() is deprecated Use output.options=TRUE instead. In geometry 0.4.0 using "full" does not give a message or warning; this will happen in future versions

  • distmesh2d() has a plot option The new plot option (TRUE by default) allows plotting to during mesh generation to be suspended, which is useful for running tests. The use of cat() has been replaced by message(), meaning messages can be supressed, for example during tests.

  • extprod3d() has a "drop" option Setting drop=FALSE guarantees that the output of extprod3d() is an array rather than a vector, even when presented with two vectors.




  • Fix for Issue #6072: distmesh2d - convergence problem ( Some parts of the original Matlab implementation of distmesh2d were omitted during the translation to R. The effect is not obvious on some problems, except for long convergence times due to excessive iterations - some do not converge at all. Graham Griffiths made changes to the code which appears to have fixed the problem as example problems now appear to run significantly faster - even faster than those I have run using Matlab. Graham's example code is now included in a test. Thanks to Graham Griffiths for reporting this problem and supplying the fix.

  • Fix for Issue #30: Move qhull docs to vignettes This is a change in response to the way R deals with inst/doc, which broke the included Qhull docs.


CHANGES IN VERSION 0.3-6 - Released 2015/09/04


  • As per CRAN policies, the title in the DESCRIPTION file is now in title case.


  • Fix for Issue #5738: segfault when run from directory lacking write permission ( Using "." as a temporary directory can cause problems if it is not writeable. Now the geometry package uses tempdir(), which R should guarantee to exist. Thanks to Laura Riggi for reporting this problem.

  • Put Robert B. Gramacy back in the author list, after he was accidentally omitted when changing to the [email protected] format on 2014/10/29 (version 0.3-5). Thanks to Robert B. Gramacy for reporting this, and apologies for the error.

CHANGES IN VERSION 0.3-5 - Released 2014/11/06


  • The default Qhull option to the delaunayn() function is now "Qt" rather than "QJ" and degenerate (zero-area) simplices are removed from the triangulation, so that all simplicies are non-degenerate. This is a follow-up to issue #2009: delaunayn can return degenerate simplicies by default ( Thanks to Rolf Turner for alerting me to the issue.

  • delaunayn() now throws an error if the number of points is less than the number of dimensions + 1.


  • delaunayn() with the "full" option also returns the areas of facets. This is a byproduct of the API change above.


  • Fix for Issue #2789: inline functions min/max generate linker error ( Thanks to Bernd Bischl for reporting the problem and suggesting the fix.

  • Partial Fix for Issue #5738: segfault when run from directory lacking write permission ( An error is now thrown, rather than a segfault. The underlying problem still needs to be dealth with.


  • The meanings of "area" and "vol" in the convhulln return value have been clarified. Thanks to Michael Cole for raising the issue.

  • The documentation of "cart2bary" and "bary2cart" has been corrected and improved. Thanks to Francisco Mendoza Torres for raising the issue.

  • HTML documentation has been for validation errors with HTML tidy. Thanks to Kurt Hornik and the CRAN maintainers for alerting me to the problem.


  • Tests are now all done using the testthat framework.

  • There is now a test to make sure output to file works. Thanks to Brian Ripley for identifying the problem while testing the pacakge for CRAN.

CHANGES IN VERSION 0.3-4 - Released 2014/03/04


  • Fix for Issue #5406: Compilation flags in Makevars ( Thanks to Kurt Hornik and the CRAN maintainers for alerting me to the problem.

CHANGES IN VERSION 0.3-3 - Released 2013/04/18


  • The License has been changed to GPL (>= 3) + file LICENSE and the LICENSE file made clearer. Thanks to Kurt Hornik and the CRAN maintainers for alerting me to the problem and helping with a solution.

  • Fix for Issue #1993: Error in solve.default in tsearchn ( Thanks to Bill Denny for reporting this and suggesting a way forward with a fix. Thanks to John Drake for alerting me to the recurrence of the problem and Jon Clayden on the R-devel list for pointing out the correct way of testing for ill-conditioned matrices.

  • Fix for Issue #2009: delaunayn can return degenerate simplicies by default ( This is a follow-on of #1993, so thanks to Bill Denny for highlighting the issue.

  • Fix for Issue #2007: Qt option given to Qhull (

  • The use of the multicore package in tests has been replaced by use of the parallel package. Thanks to Kurk Hornik for pointing this out.

  • Removed non-API call to R_TempDir. Thanks to Kurk Hornik for pointing this out.

CHANGES IN VERSION 0.3-2 - Released 2012/05/12


  • Fix for Issue #1968: convhulln crash with T0 option ( Thanks to Thomas Kirschstein, Oskar Knapik and Uwe Ligges for reporting this and to Duncan Murdoch for help on the r-devel mailing list.

  • Fix for Issue #1983: NA in an input to delaunayn crashes R ( Thanks to Bill Denny for reporting this and suggestiong a way forward with a fix.

CHANGES IN VERSION 0.3-1 - Released 2012/05/01


  • Fix for Issue #1964: R crashes when using convhulln/delaunayn ( Thanks to Thomas Kirschstein, Oskar Knapik and Paolo Piras for reporting this.

CHANGES IN VERSION 0.3-0 - Released 2012/04/17


  • New function dot() to compute dot product. Syntax is shared with Octave dot() function.

  • New function polyarea() to compute area of polygons. Syntax is shared with Octave polyarea() function.


  • Fix for Issue #1578: convhulln crashes when running 2 instances of R in the same directory: output to qhull_out.txt removed ( Thanks to Francois Rousset and Bernd Bischl for reporting this.

  • Fix for Issue #1923: Compilation on Windows 64 doesn't work (

  • Fix for Issue #1924: Silent operation is not supported ( Thanks to Raphael Leblois for reporting this.

  • Fix for Issue #1930: delaunayn should always return a matrix (

  • Fix for Issue #1915: geometry segfaults during tests (

  • Fix for Issue #1947: convhulln crash when Qhull error reported ( Thanks to Petr Savicky for reporting this.


CHANGES IN VERSION 0.2-0 - Released 2011/09/09


  • The tsearch and tsearchn functions have been ported from Octave. These functions have the same syntax as the Octave versions, though it also possible to get tsearch to output barycentric coordinates. tsearch only works for 2D simplexes (i.e. triangles), but is fast because it is written in C. By default, tsearchn uses the fast tsearch function when presented with 2D data.


  • David Sterratt has taken over from Bobby Gramacy. Thank-you to Bobby for his work on the package.

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.


0.4.5 by David C. Sterratt, 2 years ago

Report a bug at

Browse source code at

Authors: Jean-Romain Roussel [cph, ctb] (wrote tsearch function with QuadTrees) , C. B. Barber [cph] , Kai Habel [cph, aut] , Raoul Grasman [cph, aut] , Robert B. Gramacy [cph, aut] , Pavlo Mozharovskyi [cph, aut] , David C. Sterratt [cph, aut, cre]

Documentation:   PDF Manual  

Task views: Multivariate Statistics

GPL (>= 3) license

Imports magic, Rcpp, lpSolve, linprog

Suggests spelling, testthat, rgl, R.matlab, tripack

Linking to Rcpp, RcppProgress

Imported by Arothron, BAT, ClaimsProblems, DepthProc, DiceView, EthSEQ, EvolutionaryGames, GWSDAT, MBHdesign, Momocs, MultBiplotR, OptimaRegion, ProjectionBasedClustering, RoundAndRound, STEPCAM, TCIU, Umatrix, VoxR, archiDART, bayesGAM, betapart, blackbox, cati, chebpol, curvHDR, dispRity, fundiversity, gMOIP, hypervolume, iSDM, lidR, mFD, minimaxdesign, morphomap, mrfDepth, mvGPS, pavo, pdfCluster, quadmesh, rForest, rLiDAR, retistruct, tmle.npvi, treetop, ucie.

Depended on by CoopGame, EDFIR, FD, Maeswrap, RadOnc, alphashape3d, caRamel, contoureR, ddalpha, fdaPDE, gensphere, modQR, mvmesh, nonparaeff.

Suggested by DatabionicSwarm, MoEClust, RTriangle, WeightedROC, ks, mclust, phylin, ptinpoly, stm, uniformly.

See at CRAN