CHANGES IN VERSION 0.5.2 - Released 2025/02/08 BUG FIX * Issue #75: More sanitiser issues https://github.com/davidcsterratt/geometry/issues/76 This update resolves another issue with memory sanitisation observed when compiling in an UBSAN environment. Thanks to Brian Ripley for running the tests and reporting the error, and Tomas Kalibera for suggesting and testing the fix. CHANGES IN VERSION 0.5.1 - Released 2025/01/09 BUG FIX * Issue #75: Sanitiser issues https://github.com/davidcsterratt/geometry/issues/75 This update resolves issues with memory sanitisation observed when compiling in an UBSAN environment. Thanks to Brian Ripley for running the tests and reporting the error, and Tomas Kalibera for providing the fix. CHANGES IN VERSION 0.5.0 - Released 2024/08/31 CODE IMPROVEMENTS * Issue #37: Incorporate Qhull 8.0.2 https://github.com/davidcsterratt/geometry/issues/37 This update of Qhull resolves or addresses a number of issues (#11, #12) relating to points spanning a small distance compared to their mean distance to the origin MINOR API CHANGE * Issue #12: QH6227 impossible to triangulate a dataset far from the origin https://github.com/davidcsterratt/geometry/issues/12 This particular error was fixed by the fix for #37, but some points were still missing from the triangulation, when the points are far from the origin. Delaunayn now throws a warning about points missing from the triangulation, and suggests passing options to deluanayn that may help, or centering the input data before passing it to delaunayn. Thanks to Jean-Romain the orignal report, and C. B. Barber for extensive advice on Qhull. BUG FIXES * Fix for Issue #71: noRemap CRAN chack https://github.com/davidcsterratt/geometry/issues/71 Thanks to the CRAN maintainers for reporting this and Jean-Romain Roussel for providing the fix. * Fix for Issue #11: Wrong triangulation for a specific dataset https://github.com/davidcsterratt/geometry/issues/11 Thanks to Jean-Romain the report and C. B. Barber for help debugging * Fix for Issues #57 and #46: tsearch fails on points far from the origin https://github.com/davidcsterratt/geometry/issues/57 https://github.com/davidcsterratt/geometry/issues/46 Thanks to Wayne Jones for the report and Jean-Romain for the fix * Issue #58: convhulln() receives QH6271 qhull precision error https://github.com/davidcsterratt/geometry/issues/58 convhulln() now issues advice about options to avoid this error. Thanks to GitHub user Huangmp1996 for the report CHANGES IN VERSION 0.4.7 - Released 2023/02/03 BUG FIXES * Fix for Issue #67: Compiled code should not call sprintf() https://github.com/davidcsterratt/geometry/issues/67 Thanks to the CRAN maintainers for reporting this. Update uses snprintf() function. * PR #64: Replace rgl.* with *3d https://github.com/davidcsterratt/geometry/pull/64 Thanks to Duncan Murdoch for replacing rgl.* functions with *3d functions * Issue #60: Negative neighbour IDs reported by delaunayn https://github.com/davidcsterratt/geometry/issues/60 Provide documentation to explain that the Qhull "Fn" option returns negative IDs. API CHANGE * Issue #29: Make behaviour of convhulln() and delaunayn() more consistent https://github.com/davidcsterratt/geometry/issues/29 Issue message to indicate full option to delaunayn is dprecated NEW FEATURE * Issue #29: Make behaviour of convhulln() and delaunayn() more consistent https://github.com/davidcsterratt/geometry/issues/29 plot.delaunayn() to plot triangulations CHANGES IN VERSION 0.4.6.1 - Released 2022/07/04 BUG FIXES * Fix for Issue #66: Replace the tripack package with the interp package https://github.com/davidcsterratt/geometry/issues/66 The Thanks to the CRAN maintainers for replacing references to the suggested tripack package with interp CHANGES IN VERSION 0.4.6 - Released 2022/04/18 BUG FIXES * PR #49: Update tests for testthat v3 compatibility https://github.com/davidcsterratt/geometry/pull/49 Thanks to Hugo Gruson for providing the pull request * PR #50: Reorder documentation lines https://github.com/davidcsterratt/geometry/pull/50 Thanks to Hugo Gruson for providing the pull request * PR #54: Fix typo https://github.com/davidcsterratt/geometry/pull/54 Thanks to Hugh Gruson for providing the pull request OTHER CHANGES * Fix for Issue #61: Legacy macros need replaced https://github.com/davidcsterratt/geometry/issues/61 Thanks to the Brian Ripley and the CRAN team for the alert CHANGES IN VERSION 0.4.5 - Released 2019/12/02 BUG FIX * Fix for Issue #47: Install failure with gcc 10 https://github.com/davidcsterratt/geometry/issues/47 Thanks to Brian Ripley for pointing this out CHANGES IN VERSION 0.4.4 - Released 2019/08/27 BUG FIX * Fix for Issue #45: LTO error https://github.com/davidcsterratt/retistruct/issues/45 Thanks to Brian Ripley for pointing this out and providing the fix CHANGES IN VERSION 0.4.3 - Released 2019/08/21 BUG FIXES * Fix for Issue #39: tsearchn() returns NA for some points within triangle https://github.com/davidcsterratt/geometry/issues/39 tsearchn() failed (=return NA) for some points that lie within the triangulation. Thanks to Jan Lause (https://github.com/jlause) for reporting the bug and Jean-Romain Roussel for providing the fix. * Fix for Issue #40: memory misuse in src/Rtsearchn.c https://github.com/davidcsterratt/geometry/issues/40 In src/Rtsearchn.c 'idmap' was allocated with max_facet_id elements but then a value to idmap[max_facet_id] was assigned, which was one element beyond the end of that allocation, potentially clobbering the memory allocation system. Thanks to Bill Dunlap (https://github.com/BillDunlap) for reporting this, and the suggested fix. * Fix for Issue #44: R_tmpnam()/free() causes crash in TERR https://github.com/davidcsterratt/geometry/issues/44 Because TERR (https://docs.tibco.com/products/tibco-enterprise-runtime-for-r) is not compiled with gcc (it uses either the Intel or Microsoft C++ compiler) on Windows, calling free() in a package's DLL for memory allocated with malloc() in TERR's own DLL causes a crash. The R API function R_tmpnam() causes this problem in the geometry package. Thanks to Bill Dunlap (https://github.com/BillDunlap) for reporting this, and the suggested fix. ENHANCEMENT * Fix for Issue #42: Improve error reporting from Qhull https://github.com/davidcsterratt/geometry/issues/42 Full error from Qhull is now returned, rather than just the first two lines. CHANGES IN VERSION 0.4.2 - Released 2019/07/05 BUG FIX * Fix for Issue #35: intersectn() reports zero volume for some overlapping 4D hulls https://github.com/davidcsterratt/geometry/issues/35 intersectn() failed on a particular example. Modifying the scale option given to lpSolve::lp in feasible.point() has fixed this problem. feasible.point() also now returns the lpSolve::lp() error message when it fails, rather than failing silently as before. Thanks to Maxime Logez for reporting the bug and Sam Buttrey, lpSolve maintainer, for insights into lpSolve. CHANGES IN VERSION 0.4.1 - Released 2019/03/27 BUG FIXES * Fix for Issue #34: intersectn() fails when overlapping region is not in positive quadrant https://github.com/davidcsterratt/geometry/issues/34 intersectn() would return no intersecting hull for input hulls whose overlapping region did not overlap with the postive quadrant (i.e. the region where all coordinates are non-negative). Thanks to Maxime Logez for reporting the bug. * Fix for Issue #33: nonsensical results from intersectn() in 4D https://github.com/davidcsterratt/geometry/issues/33 intersectn() gave demonstrably wrong results in some cases. This was Because of some heuristic (non-Qhull) code in halfspacen which was designed to get round cases in which Qhull fails with options "Tv" because the hull is very narrow. The solution is to remove the heuristic method, and also to fix Issue #34 (above). Before Issue #34 was fixed, it was found that adding the "QJ" option could also help, and this is now suggested in the error message about narrow hulls. Thanks to Maxime Logez for reporting the bug and supplying a reproducible example, now included in tests. CHANGES IN VERSION 0.4.0 - Released 2019/02/18 LICENSE CHANGES * Following requests by the CRAN maintainers and disucssion on the r-package-devel email list, the entire package is now released under GPL (>= 3). https://github.com/davidcsterratt/geometry/issues/27 API CHANGES * Default options to delaunayn have been changed https://github.com/davidcsterratt/geometry/issues/4 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(). https://github.com/davidcsterratt/geometry/issues/29 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 https://github.com/davidcsterratt/geometry/issues/29 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 https://github.com/davidcsterratt/geometry/issues/15 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 https://github.com/davidcsterratt/geometry/issues/16 Setting drop=FALSE guarantees that the output of extprod3d() is an array rather than a vector, even when presented with two vectors. NEW FUNCTIONS * New function inhulln() to test if points are in a hull https://github.com/davidcsterratt/geometry/issues/1 * New function halfspacen() to compute intersection points of halfspaces about an interior point https://github.com/davidcsterratt/geometry/issues/25 * New function intersectn() to compute intersection of convex hulls of two sets of points https://github.com/davidcsterratt/geometry/issues/26 * Functions cart2sph, sph2cart, cart2pol, pol2cart ported from Octave https://github.com/davidcsterratt/geometry/issues/14 NEW FEATURES * convhulln() can produce non-triangulated output https://github.com/davidcsterratt/geometry/issues/22 Thanks to Pavlo Mozharovskyi for pushing code to achive this * delaunayn() and convhulln() throw Qhull error messages when Qhull fails https://github.com/davidcsterratt/geometry/issues/28 BUG FIXES * Fix for Issue #6072: distmesh2d - convergence problem (https://r-forge.r-project.org/tracker/?func=detail&atid=4552&aid=6072&group_id=1149) 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 https://github.com/davidcsterratt/geometry/issues/30 This is a change in response to the way R deals with inst/doc, which broke the included Qhull docs. CODE IMPROVEMENTS * The 2D tsearch C code has been replaced by a much more efficient QuadTree algorithm written in C++ by Jean-Romain Roussel. The speedup with uniformly distribued mesh points and search points is of the order of 40x. Many thanks to Jean-Romain for the contribution. https://github.com/davidcsterratt/geometry/issues/9 https://github.com/davidcsterratt/geometry/pull/8 * The new reentrant Qhull library (current version v7.2.1) is used, as a precursor to allowing Qhull objects to be returned and operated on https://github.com/davidcsterratt/geometry/issues/3 * convhulln() now returns a pointer to the qhull object representing the hull. https://github.com/davidcsterratt/geometry/issues/2 This is used in the inhull() implementation * delaunayn() now returns a pointer to the qhull object representing the triangulation https://github.com/davidcsterratt/geometry/issues/7 * tsearchn() can take an delaunay object, which should give fast performance https://github.com/davidcsterratt/geometry/issues/6 NOTE: This feature is experimental and has only been tested on 3D triangulations * Test added for polyarea() Thanks to Toby Hocking for suggesting adding one CHANGES IN VERSION 0.3-6 - Released 2015/09/04 CODE IMPROVEMENTS * As per CRAN policies, the title in the DESCRIPTION file is now in title case. BUG FIXES * Fix for Issue #5738: segfault when run from directory lacking write permission (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=5738&group_id=1149&atid=4552) 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 Authors@R 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 API CHANGES * 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 (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1993&group_id=1149&atid=4552). 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. FEATURES * delaunayn() with the "full" option also returns the areas of facets. This is a byproduct of the API change above. BUG FIXES * Fix for Issue #2789: inline functions min/max generate linker error (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=2789&group_id=1149&atid=4552) 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 (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=5738&group_id=1149&atid=4552) An error is now thrown, rather than a segfault. The underlying problem still needs to be dealth with. DOCUMENTATION IMPROVEMENTS * 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. CODE IMPROVEMENTS * 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 BUG FIXES * Fix for Issue #5406: Compilation flags in Makevars (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=5406&group_id=1149&atid=4552) Thanks to Kurt Hornik and the CRAN maintainers for alerting me to the problem. CHANGES IN VERSION 0.3-3 - Released 2013/04/18 BUG FIXES * 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 (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1993&group_id=1149&atid=4552) 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 (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1993&group_id=1149&atid=4552) 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 (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=2007&group_id=1149&atid=4552) * 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 BUG FIXES * Fix for Issue #1968: convhulln crash with T0 option (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1968&group_id=1149&atid=4552) 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 (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1983&group_id=1149&atid=4552) 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 BUG FIXES * Fix for Issue #1964: R crashes when using convhulln/delaunayn (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1964&group_id=1149&atid=4552). Thanks to Thomas Kirschstein, Oskar Knapik and Paolo Piras for reporting this. CHANGES IN VERSION 0.3-0 - Released 2012/04/17 NEW FEATURES * 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. BUG FIXES * Fix for Issue #1578: convhulln crashes when running 2 instances of R in the same directory: output to qhull_out.txt removed (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1578&group_id=1149&atid=4552). Thanks to Francois Rousset and Bernd Bischl for reporting this. * Fix for Issue #1923: Compilation on Windows 64 doesn't work (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1923&group_id=1149&atid=4552) * Fix for Issue #1924: Silent operation is not supported (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1924&group_id=1149&atid=4552) Thanks to Raphael Leblois for reporting this. * Fix for Issue #1930: delaunayn should always return a matrix (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1930&group_id=1149&atid=4552) * Fix for Issue #1915: geometry segfaults during tests (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1915&group_id=1149&atid=4552) * Fix for Issue #1947: convhulln crash when Qhull error reported (https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1947&group_id=1149&atid=4552). Thanks to Petr Savicky for reporting this. OTHER CHANGES * Updated to qhull version 2011.2. * The default qhull option "QJ" for delaunayn() has been replaced by "Qt". One or other option is always provided to the qhull code (see https://r-forge.r-project.org/tracker/index.php?func=detail&aid=1915&group_id=1149&atid=4552). * Documentation improvements. * Added some tests. CHANGES IN VERSION 0.2-0 - Released 2011/09/09 NEW FEATURES * 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. NEW MAINTAINER * David Sterratt has taken over from Bobby Gramacy. Thank-you to Bobby for his work on the package.