Qhull 2019.1
Qhull 2019.1 contains bug fixes and improvements to logging, error reporting, and merging.
-
Fixed fifty bugs, including initialization bugs and memory corruption bugs in qh_readpoints and qh_option.
-
Qhull compiles as 32-bit or 64-bit code. As 64-bit code, Qhull's 4-D data structures increase by 50% and reduce the effectiveness of cache memory. This will slow down Qhull for large data sets.
-
For programmers using qh_findbestfacet to locate a Delaunay triangle:
qh_findbestfacet may return an adjacent triangle [F. Drielsma]
-
New option 'TAn' stops Qhull after adding n points.
-
New option 'Tf' flushes qh_fprintf for debugging segfaults.
-
New options '--help', '-?', or '--' display a short help message. Under Git for Windows or MSYS2, 'qhull' waits for stdin.
-
Option 'TP-1' turns on tracing after qh_buildhull and qh_postmerge. It traces qh_check_maxout, qh_prepare_output, qh_triangulate, and qh_voronoi_center
-
Options 'TI' and 'TO' do not require a space before the filename. traces qh_check_maxout, qh_prepare_output, qh_triangulate, and qh_voronoi_center
-
An unknown Qhull option is an error. It was a warning. Override with option 'Qw'.
-
Short or long input to Qhull is an error. It was a warning. Override with option 'Qa'.
-
Documentation encourages the use of joggled input. Joggled input is less precise than facet merging, but it cannot incur merge errors for highly degenerate input.
-
Documentation refers to 'dupridge' instead of 'duplicate ridge'. A dupridge is an erroneous ridge between four or more facets.
-
CMake exports QhullTargets for config.cmake.in and find_package [tamasmeszaros]
-
The C++ interface, QhullFacet and QhullVertex, includes new methods hasNext() and hasPrevious().
-
Test scripts qtest.sh and q_benchmark help with logging and optimizing Qhull, particularly for intermittent errors and bad cases for Qhull.
Please convert to reentrant Qhull (libqhull_r). A new shell script, eg/make-qhull_qh.sh, recreates libqhull code from libqhull_r code. A directory-diff is a test that the conversion was correct.
An experimental option, 'Q14', merges pinched vertices. Pinched vertices are nearly adjacent vertices (ca. 1.0E-13 apart on the unit cube). They are far enough apart to avoid geometric errors, but not far enough apart to avoid topological errors. An example of a topological error is four facets that share the same ridge; a ridge should only have two neighboring facets. Qhull 2015.2 merges facets to repair these errors, but it may fail, especially for multiple pinched vertices.
The N_PINCHED section of q_benchmark
tests pinched vertices with option 'Q14'.
Qhull continues to report errors for difficult cases. Some of these inputs always fail with Qhull 2015.2.
However, other inputs almost always succeed with Qhull 2015.2. It addition, normal inputs for
Qhull 2019.1 with 'Q14' are somewhat slower than for Qhull 2015.2.
The q_benchmark tests of N_PINCHED reveal the interaction between geometric precision errors and topological errors. In Euclidean space with precise arithmetic, the mathematics of convex hulls prevent topological errors. With imprecision, topological errors become possible. Qhull handles precision and topological errors with facet and vertex merging. With repeated merges, precision errors and topological errors eventually become too severe and prevent further processing. For a further discussion of known issues see Limitations of merged facets.
These problems are unlikely to occur in practice. Most of the troublesome inputs consist of many points approximately 1.0e-13 (scaled to the unit cube) from either nearby points or hyperplanes. Such inputs lead to many merges that eventually fail. Points substantially closer or further apart are OK. A future version of Qhull will include per-vertex joggle. Per-vertex joggle can prevent precision errors, just like Qhull's joggle option 'QJ'.